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 <= 200s和t只含有小写字母以及字符'#'进阶：
- 你可以用
O(n)的时间复杂度和O(1)的空间复杂度解决该问题吗？
2、解题思路
问题分析：
- 字符串中的
#表示退格操作，会删除前一个字符。 - 需要模拟文本编辑器的行为，处理退格操作后比较两个字符串是否相同。
- 字符串中的
算法设计：
- 使用栈来模拟文本编辑器的行为：
- 遍历字符串，遇到非
#字符则压入栈中。 - 遇到
#字符则弹出栈顶字符（如果栈不为空）。
- 遍历字符串，遇到非
- 最终比较两个栈中的字符是否相同。
- 使用栈来模拟文本编辑器的行为：
优化：
- 使用双指针可以在不占用额外空间的情况下解决问题，但栈的解法更直观。
3、代码实现
C++
class Solution {
public:
bool backspaceCompare(string s, string t) {
stack<char> s1, s2;
// 处理字符串 s
for (char c : s) {
if (c != '#') {
s1.push(c);
} else if (!s1.empty()) {
s1.pop();
}
}
// 处理字符串 t
for (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<>();
// 处理字符串 s
for (char c : s.toCharArray()) {
if (c != '#') {
s1.push(c);
} else if (!s1.isEmpty()) {
s1.pop();
}
}
// 处理字符串 t
for (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 stack
return 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 <= 1040 <= 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，直接返回0
left = [0] * n # 记录每个位置左侧严格递增的长度
for i in range(1, n):
if arr[i - 1] < arr[i]:
left[i] = left[i - 1] + 1
right = [0] * n # 记录每个位置右侧严格递减的长度
for i in range(n - 2, -1, -1):
if arr[i + 1] < arr[i]:
right[i] = right[i + 1] + 1
ret = 0
for 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 <= 1040 <= hand[i] <= 1091 <= 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 整除，直接返回 false
if (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;
// 如果缺少某张连续的牌，返回 false
if (cnt[num] == 0) {
return false;
}
cnt[num]--; // 用掉一张牌
}
}
return true; // 所有牌都成功分组
}
};
Java
class Solution {
public boolean isNStraightHand(int[] hand, int groupSize) {
int n = hand.length;
// 如果牌的总数不能被 groupSize 整除，直接返回 false
if (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;
// 如果缺少某张连续的牌，返回 false
if (!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 整除，直接返回 False
return False
hand.sort() # 排序
cnt = defaultdict(int)
for num in hand: # 统计每张牌的数量
cnt[num] += 1
for x in hand:
if cnt[x] == 0: # 如果当前牌已经被用完，跳过
continue
for j in range(groupSize): # 检查连续的 groupSize 张牌
num = x + j
if cnt[num] == 0: # 如果缺少某张连续的牌，返回 False
return False
cnt[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.length1 <= n <= 120 <= graph[i].length < ngraph[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] = True
ret = 0
while q:
u, mask, dist = q.popleft()
# 如果所有节点都被访问，返回当前路径长度
if mask == (1 << n) - 1:
ret = dist
break
# 遍历相邻节点
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] = True
return ret
4、复杂度分析
时间复杂度：O(n2 ⋅2n)。
空间复杂度：O(n⋅2n)