Q1、[簡單] 比較含退格的字符串
1、題目描述
給定 s
和 t
兩個字符串,當它們分別被輸入到空白的文本編輯器后,如果兩者相等,返回 true
。#
代表退格字符。
**注意:**如果對空文本輸入退格字符,文本繼續為空。
示例 1:
輸入:s = "ab#c", t = "ad#c" 輸出:true 解釋:s 和 t 都會變成 "ac"。
示例 2:
輸入:s = "ab##", t = "c#d#" 輸出:true 解釋:s 和 t 都會變成 ""。
示例 3:
輸入:s = "a#c", t = "b" 輸出:false 解釋:s 會變成 "c",但 t 仍然是 "b"。
提示:
1 <= s.length, t.length <= 200
s
和t
只含有小寫字母以及字符'#'
進階:
- 你可以用
O(n)
的時間復雜度和O(1)
的空間復雜度解決該問題嗎?
2、解題思路
-
問題分析:
- 字符串中的
#
表示退格操作,會刪除前一個字符。 - 需要模擬文本編輯器的行為,處理退格操作后比較兩個字符串是否相同。
- 字符串中的
-
算法設計:
- 使用棧來模擬文本編輯器的行為:
- 遍歷字符串,遇到非
#
字符則壓入棧中。 - 遇到
#
字符則彈出棧頂字符(如果棧不為空)。
- 遍歷字符串,遇到非
- 最終比較兩個棧中的字符是否相同。
- 使用棧來模擬文本編輯器的行為:
-
優化:
- 使用雙指針可以在不占用額外空間的情況下解決問題,但棧的解法更直觀。
3、代碼實現
C++
class Solution {
public:bool backspaceCompare(string s, string t) {stack<char> s1, s2;// 處理字符串 sfor (char c : s) {if (c != '#') {s1.push(c);} else if (!s1.empty()) {s1.pop();}}// 處理字符串 tfor (char c : t) {if (c != '#') {s2.push(c);} else if (!s2.empty()) {s2.pop();}}// 比較兩個棧if (s1.size() != s2.size()) {return false;}while (!s1.empty()) {if (s1.top() != s2.top()) {return false;}s1.pop();s2.pop();}return true;}
};
Java
class Solution {public boolean backspaceCompare(String s, String t) {Stack<Character> s1 = new Stack<>();Stack<Character> s2 = new Stack<>();// 處理字符串 sfor (char c : s.toCharArray()) {if (c != '#') {s1.push(c);} else if (!s1.isEmpty()) {s1.pop();}}// 處理字符串 tfor (char c : t.toCharArray()) {if (c != '#') {s2.push(c);} else if (!s2.isEmpty()) {s2.pop();}}// 比較兩個棧if (s1.size() != s2.size()) {return false;}while (!s1.isEmpty()) {if (s1.pop() != s2.pop()) {return false;}}return true;}
}
Python
class Solution:def backspaceCompare(self, s: str, t: str) -> bool:def build(s: str) -> list:stack = []for c in s:if c != '#':stack.append(c)elif stack:stack.pop()return stackreturn build(s) == build(t)
4、復雜度分析
-
時間復雜度:
- 處理字符串
s
和t
的時間復雜度均為 O(n),其中n
是字符串的長度。 - 比較兩個棧的時間復雜度為 O(n)。
- 總時間復雜度為 O(n)。
- 處理字符串
-
空間復雜度:
- 使用棧的空間復雜度為 O(n)。
Q2、[中等] 數組中的最長山脈
1、題目描述
把符合下列屬性的數組 arr
稱為 山脈數組 :
arr.length >= 3
- 存在下標 i(
0 < i < arr.length - 1
),滿足arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
給出一個整數數組 arr
,返回最長山脈子數組的長度。如果不存在山脈子數組,返回 0
。
示例 1:
輸入:arr = [2,1,4,7,3,2,5] 輸出:5 解釋:最長的山脈子數組是 [1,4,7,3,2],長度為 5。
示例 2:
輸入:arr = [2,2,2] 輸出:0 解釋:不存在山脈子數組。
提示:
1 <= arr.length <= 104
0 <= arr[i] <= 104
進階:
- 你可以僅用一趟掃描解決此問題嗎?
- 你可以用
O(1)
空間解決此問題嗎?
2、解題思路
-
問題分析:
- 山脈數組必須有一個山峰,該山峰是數組中的最大值。
- 山脈數組的左側必須嚴格遞增,右側必須嚴格遞減。
-
算法設計:
- 使用動態規劃來記錄每個位置左側嚴格遞增的長度和右側嚴格遞減的長度。
- 對于每個位置
i
,如果left[i]
和right[i]
都大于0
,則說明i
是山峰,山脈長度為left[i] + right[i] + 1
。 - 最終返回所有可能的山脈長度中的最大值。
-
優化:
-
使用兩個數組
left
和right
來分別記錄每個位置左側和右側的嚴格遞增/遞減長度。 -
遍歷數組兩次來填充
left
和right
,然后遍歷一次計算最大山脈長度。
-
3、代碼實現
C++
class Solution {
public:int longestMountain(vector<int>& arr) {int n = arr.size();if (n < 3) {return 0; // 如果數組長度小于 3,直接返回 0}vector<int> left(n, 0); // 記錄每個位置左側嚴格遞增的長度for (int i = 1; i < n; ++i) {if (arr[i - 1] < arr[i]) {left[i] = left[i - 1] + 1;}}vector<int> right(n, 0); // 記錄每個位置右側嚴格遞減的長度for (int i = n - 2; i >= 0; --i) {if (arr[i + 1] < arr[i]) {right[i] = right[i + 1] + 1;}}int ret = 0;for (int i = 0; i < n; ++i) {if (left[i] > 0 && right[i] > 0) { // 如果 i 是山峰ret = max(ret, left[i] + right[i] + 1); // 計算山脈長度}}return ret;}
};
class Solution {
public:int longestMountain(vector<int>& arr) {int n = arr.size();int ret = 0;int left = 0;while (left + 2 < n) {int right = left + 1;if (arr[left] < arr[left + 1]) {while (right + 1 < n && arr[right] < arr[right + 1]) {++right;}if (right < n - 1 && arr[right] > arr[right + 1]) {while (right < n - 1 && arr[right] > arr[right + 1]) {++right;}ret = max(ret, right - left + 1);} else {++right;}}left = right;}return ret;}
};
Java
class Solution {public int longestMountain(int[] arr) {int n = arr.length;if (n < 3) {return 0; // 如果數組長度小于3,直接返回0}int[] left = new int[n]; // 記錄每個位置左側嚴格遞增的長度for (int i = 1; i < n; ++i) {if (arr[i - 1] < arr[i]) {left[i] = left[i - 1] + 1;}}int[] right = new int[n]; // 記錄每個位置右側嚴格遞減的長度for (int i = n - 2; i >= 0; --i) {if (arr[i + 1] < arr[i]) {right[i] = right[i + 1] + 1;}}int ret = 0;for (int i = 0; i < n; ++i) {if (left[i] > 0 && right[i] > 0) { // 如果i是山峰ret = Math.max(ret, left[i] + right[i] + 1); // 計算山脈長度}}return ret;}
}
Python
class Solution:def longestMountain(self, arr: List[int]) -> int:n = len(arr)if n < 3:return 0 # 如果數組長度小于3,直接返回0left = [0] * n # 記錄每個位置左側嚴格遞增的長度for i in range(1, n):if arr[i - 1] < arr[i]:left[i] = left[i - 1] + 1right = [0] * n # 記錄每個位置右側嚴格遞減的長度for i in range(n - 2, -1, -1):if arr[i + 1] < arr[i]:right[i] = right[i + 1] + 1ret = 0for i in range(n):if left[i] > 0 and right[i] > 0: # 如果i是山峰ret = max(ret, left[i] + right[i] + 1) # 計算山脈長度return ret
4、復雜度分析
- 時間復雜度:
- 填充
left
和right
數組的時間復雜度為 O(n)。 - 計算最大山脈長度的時間復雜度為 O(n)。
- 總時間復雜度為 O(n)。
- 填充
- 空間復雜度:
- 使用兩個數組
left
和right
,空間復雜度為 O(n)。
- 使用兩個數組
Q3、[中等] 一手順子
1、題目描述
Alice 手中有一把牌,她想要重新排列這些牌,分成若干組,使每一組的牌數都是 groupSize
,并且由 groupSize
張連續的牌組成。
給你一個整數數組 hand
其中 hand[i]
是寫在第 i
張牌上的數值。如果她可能重新排列這些牌,返回 true
;否則,返回 false
。
示例 1:
輸入:hand = [1,2,3,6,2,3,4,7,8], groupSize = 3 輸出:true 解釋:Alice 手中的牌可以被重新排列為 [1,2,3],[2,3,4],[6,7,8]。
示例 2:
輸入:hand = [1,2,3,4,5], groupSize = 4 輸出:false 解釋:Alice 手中的牌無法被重新排列成幾個大小為 4 的組。
提示:
1 <= hand.length <= 104
0 <= hand[i] <= 109
1 <= groupSize <= hand.length
2、解題思路
-
問題分析:
- 需要將牌分成若干組,每組有
groupSize
張連續的牌。 - 如果牌的總數不能被
groupSize
整除,直接返回false
。 - 需要統計每張牌的數量,并按順序分組。
- 需要將牌分成若干組,每組有
-
算法設計:
- 先檢查牌的總數是否能被
groupSize
整除。 - 對牌進行排序,并統計每張牌的數量。
- 遍歷排序后的牌,嘗試將連續的
groupSize
張牌分成一組,如果無法找到連續的牌則返回false
。
- 先檢查牌的總數是否能被
-
優化:
- 使用哈希表統計每張牌的數量,可以快速查詢和更新。
- 排序后可以方便地找到連續的牌。
3、代碼實現
C++
class Solution {
public:bool isNStraightHand(vector<int>& hand, int groupSize) {int n = hand.size();// 如果牌的總數不能被 groupSize 整除,直接返回 falseif (n % groupSize != 0) {return false;}sort(hand.begin(), hand.end()); // 排序unordered_map<int, int> cnt; // 統計每張牌的數量for (auto& num : hand) {cnt[num]++;}for (auto& x : hand) {// 如果當前牌已經被用完,跳過if (cnt[x] == 0) {continue;}// 檢查連續的 groupSize 張牌for (int j = 0; j < groupSize; ++j) {int num = x + j;// 如果缺少某張連續的牌,返回 falseif (cnt[num] == 0) {return false;}cnt[num]--; // 用掉一張牌}}return true; // 所有牌都成功分組}
};
Java
class Solution {public boolean isNStraightHand(int[] hand, int groupSize) {int n = hand.length;// 如果牌的總數不能被 groupSize 整除,直接返回 falseif (n % groupSize != 0) {return false;}Arrays.sort(hand); // 排序Map<Integer, Integer> cnt = new HashMap<>(); // 統計每張牌的數量for (int num : hand) {cnt.put(num, cnt.getOrDefault(num, 0) + 1);}for (int x : hand) {// 如果當前牌已經被用完,跳過if (cnt.get(x) == 0) {continue;}// 檢查連續的 groupSize 張牌for (int j = 0; j < groupSize; ++j) {int num = x + j;// 如果缺少某張連續的牌,返回 falseif (!cnt.containsKey(num) || cnt.get(num) == 0) {return false;}cnt.put(num, cnt.get(num) - 1); // 用掉一張牌}}return true; // 所有牌都成功分組}
}
Python
class Solution:def isNStraightHand(self, hand: List[int], groupSize: int) -> bool:n = len(hand)if n % groupSize != 0: # 如果牌的總數不能被 groupSize 整除,直接返回 Falsereturn Falsehand.sort() # 排序cnt = defaultdict(int)for num in hand: # 統計每張牌的數量cnt[num] += 1for x in hand:if cnt[x] == 0: # 如果當前牌已經被用完,跳過continuefor j in range(groupSize): # 檢查連續的 groupSize 張牌num = x + jif cnt[num] == 0: # 如果缺少某張連續的牌,返回 Falsereturn Falsecnt[num] -= 1 # 用掉一張牌return True # 所有牌都成功分組
4、復雜度分析
-
時間復雜度:
- 排序的時間復雜度為 O(nlogn)。
- 遍歷和分組的時間復雜度為 O(nlogn)。
- 總時間復雜度為 O(nlogn)。
-
空間復雜度:
- 使用哈希表存儲牌的數量,空間復雜度為 O(nlogn)。
Q4、[困難] 訪問所有節點的最短路徑
1、題目描述
存在一個由 n
個節點組成的無向連通圖,圖中的節點按從 0
到 n - 1
編號。
給你一個數組 graph
表示這個圖。其中,graph[i]
是一個列表,由所有與節點 i
直接相連的節點組成。
返回能夠訪問所有節點的最短路徑的長度。你可以在任一節點開始和停止,也可以多次重訪節點,并且可以重用邊。
示例 1:
輸入:graph = [[1,2,3],[0],[0],[0]] 輸出:4 解釋:一種可能的路徑為 [1,0,2,0,3]
示例 2:
輸入:graph = [[1],[0,2,4],[1,3,4],[2],[1,2]] 輸出:4 解釋:一種可能的路徑為 [0,1,4,2,3]
提示:
n == graph.length
1 <= n <= 12
0 <= graph[i].length < n
graph[i]
不包含i
- 如果
graph[a]
包含b
,那么graph[b]
也包含a
- 輸入的圖總是連通圖
2、解題思路
- 問題分析:
- 這是一個典型的**狀態壓縮廣度優先搜索(BFS)**問題。
- 需要記錄訪問過的節點集合,通常用**位掩碼(bitmask)**表示,其中第
i
位為1
表示節點i
已被訪問。 - 使用 BFS 來探索所有可能的路徑,確保找到最短路徑。
- 算法設計:
- 初始化:從每個節點出發,初始化隊列,記錄當前節點、訪問掩碼和路徑長度。
- BFS 遍歷:對于隊列中的每個狀態,嘗試訪問相鄰節點,并更新訪問掩碼。
- 終止條件:當訪問掩碼表示所有節點都被訪問時,返回當前路徑長度。
- 優化:
- 使用
seen
數組避免重復訪問相同的節點和掩碼組合。 - 優先處理路徑長度較短的狀態,確保找到最短路徑
- 使用
3、代碼實現
C++
class Solution {
public:int shortestPathLength(vector<vector<int>>& graph) {int n = graph.size();queue<tuple<int, int, int>> q; // 隊列存儲 (節點, 掩碼, 路徑長度)vector<vector<bool>> seen(n, vector<bool>(1 << n, false)); // 標記是否訪問過// 初始化隊列,從每個節點出發for (int i = 0; i < n; ++i) {q.emplace(i, 1 << i, 0);seen[i][1 << i] = true;}int ret = 0;while (!q.empty()) {auto [u, mask, dist] = q.front();q.pop();// 如果所有節點都被訪問,返回當前路徑長度if (mask == (1 << n) - 1) {ret = dist;break;}// 遍歷相鄰節點for (int v : graph[u]) {int mask_v = mask | (1 << v); // 更新掩碼if (!seen[v][mask_v]) {q.emplace(v, mask_v, dist + 1);seen[v][mask_v] = true;}}}return ret;}
};
Java
class Solution {public int shortestPathLength(int[][] graph) {int n = graph.length;Queue<int[]> q = new ArrayDeque<>(); // 隊列存儲 [節點, 掩碼, 路徑長度]boolean[][] seen = new boolean[n][1 << n]; // 標記是否訪問過// 初始化隊列,從每個節點出發for (int i = 0; i < n; ++i) {q.offer(new int[] { i, 1 << i, 0 });seen[i][1 << i] = true;}int ret = 0;while (!q.isEmpty()) {int[] state = q.poll();int u = state[0], mask = state[1], dist = state[2];// 如果所有節點都被訪問,返回當前路徑長度if (mask == (1 << n) - 1) {ret = dist;break;}// 遍歷相鄰節點for (int v : graph[u]) {int mask_v = mask | (1 << v); // 更新掩碼if (!seen[v][mask_v]) {q.offer(new int[] { v, mask_v, dist + 1 });seen[v][mask_v] = true;}}}return ret;}
}
Python
class Solution:def shortestPathLength(self, graph: List[List[int]]) -> int:n = len(graph)q = deque() # 隊列存儲 (節點, 掩碼, 路徑長度)seen = [[False] * (1 << n) for _ in range(n)] # 標記是否訪問過# 初始化隊列,從每個節點出發for i in range(n):q.append((i, 1 << i, 0))seen[i][1 << i] = Trueret = 0while q:u, mask, dist = q.popleft()# 如果所有節點都被訪問,返回當前路徑長度if mask == (1 << n) - 1:ret = distbreak# 遍歷相鄰節點for v in graph[u]:mask_v = mask | (1 << v) # 更新掩碼if not seen[v][mask_v]:q.append((v, mask_v, dist + 1))seen[v][mask_v] = Truereturn ret
4、復雜度分析
-
時間復雜度:O(n2 ?2n)。
-
空間復雜度:O(n?2n)