LeetCode Hot 100 刷题笔记（Python）
发布于 2025-05-10
|
更新于
2025-12-25
|
字数：29895
作者非精通算法选手，只因为实习/秋招无奈刷题，此文仅作自己的笔记供后续回忆复习。
推荐视频
哈希
题意为：遍历数组元素 x，要在数组中查询是否存在 (target - x)。
使用哈希表可以让查找从 O(n) 变为 O(1)
1
2
3
4
5
6
7
|
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
index = {}
for i, x in enumerate(nums):
if target - x in index:
return [i, index[target - x]]
index[x] = i
|
可以使用哈希表来收集字母异位词，键是相同点，值是字母异位词的列表。
如何判断两个字符串是否是字母异位词有两种常用思路：
-
排序：互为字母异位词的两个字符串排序之后得到的字符串一定是相同的。
1
2
3
4
5
6
|
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = collections.defaultdict(list)
for s in strs:
groups["".join(sorted(s))].append(s)
return list(groups.values())
|
-
计数：互为字母异位词的两个字符串中的相同字母出现的次数一定是相同的。
1
2
3
4
5
6
7
8
9
|
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = collections.defaultdict(list)
for s in strs:
count = [0] * 26
for ch in s:
count[ord(ch) - ord('a')] += 1
groups[tuple(count)].append(s)
return list(groups.values())
|
Python 语法技巧
- 使用
collections.defaultdict() 进行初始化，可以解决当 key 在字典中不存在时抛出错误的问题。
"".join(sorted(s)) 是常用的对字符串排序的写法。count = [0] * 26; count[ord(ch) - ord('a')] += 1 是常用的统计字符串中字母出现次数的写法。- 字典的键必须满足**可哈希（__hash__）、可比较（__eq__）**两个条件，list 属于可变容器，不满足可哈希，因此需要使用
tuple() 把它变为元组才可以作为哈希表的键。
- 对字典可以使用
values() 方法获取其值的集合，但返回的是 dictview（视图），所以需要显式使用 list 进行转换。
朴素想法：考虑枚举数组中的每个元素 x，让它作为序列起点，然后判断 x+1，x+2，…，是否存在，假设最长匹配到了 x+y，那么长度就是 y+1，不断更新长度最大值即可。
怎么优化时间复杂度？
- 判断 x+1 是否存在是一个经典的在数组中寻找指定元素是否存在的问题：可以用哈希表空间换时间。
- 并且由于是连续序列，所以当我们尝试枚举一个元素 x 时，可以判断其前面一个数（x-1）是否在数组中：如果在数组中，那么跳过即可，因为根据思路我们会从 x-1 开始尝试匹配。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
s = set(nums)
ans = 0
for x in s:
if x - 1 in s:
continue
length = 1
while x + length in s:
length += 1
ans = max(ans, length)
return ans
|
Python 语法技巧
- 集合 set 是一个特殊的字典（只存 key，不存 value），其底层实现本质上还是一个哈希表。
总结
当遇到在数组中查找指定元素是否存在的问题时，可以考虑构建哈希表，建表时间复杂度 O(n)，查表时间复杂度 O(1)。
1
2
3
4
5
6
|
# 原数组
nums = [1,2,3,4,5]
# 建表
s = set(nums)
# 查表
(1 in s) == (6 not in s)
|
双指针
- 把数组分为 3 部分，已处理/零/待处理，使用两个指针来进行分割。
- 左指针（left）指向零部分的第一个零，右指针（right）指向待处理的第一个数。
- 右指针不断向右移动，每次右指针指向非零数，则将左右指针对应的数交换，同时左指针右移。每次交换都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。
1
2
3
4
5
6
7
8
|
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
lp = rp = 0
while rp < len(nums):
if nums[rp] != 0:
nums[lp], nums[rp] = nums[rp], nums[lp]
lp += 1
rp += 1
|
题目要求找到容器能盛水的最大容量。容量由两个因素决定：
- 底部长度：即两个指针之间的距离。
- 高度：即两端柱子中较小的那个值。
容量公式：
$$
容量=(右指针−左指针)×min(height[left],height[right])
$$
为什么用双指针？
- 底部长度的最大值一开始就确定了：就是数组的最左端和最右端。
- 随着指针的移动，底部长度只会变小，不会再变大。
- 因此，想要容量变大，就只能依赖高度的提升。
移动哪个指针？
- 容量由短板决定（木桶原理）。
- 如果不改变短板，高度不会提升，容量也不会变大。
- 所以每次都要移动数字较小的那个指针，去尝试找到更高的柱子。
总结算法流程
- 左指针放在最左，右指针放在最右。
- 计算当前容量并更新最大值。
- 移动较小高度的指针。
- 循环直到两个指针相遇。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def maxArea(self, height: List[int]) -> int:
lp, rp = 0, len(height) - 1
ans = 0
while lp < rp:
ans = max(ans, (rp - lp) * min(height[lp], height[rp]))
if height[lp] < height[rp]:
lp += 1
else:
rp -= 1
return ans
|
-
对数组进行排序，这样得到的三元组 (a, b, c) 满足 a ≤ b ≤ c，天然避免了不同排列形式的重复（比如 (b, a, c)、(c, b, a) ）。同时，在枚举外层数 a 时，如果遇到与前一次相同的值，就直接跳过，避免重复解。
-
因为条件是 a+b+c=0，那么在固定 a 的情况下，当 b 变大时，c 只能变小，因此第三重循环实际和第二重循环是并列关系，因为我们的数组已有序，当 b 往右移动时，c 只能往左移，由此引入了双指针解法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = []
for i in range(n):
# 去重，跳过相同的数
if i > 0 and nums[i] == nums[i - 1]:
continue
lp, rp = i + 1, n - 1
while lp < rp:
sum_ = nums[i] + nums[lp] + nums[rp]
if sum_ > 0:
rp -= 1
elif sum_ < 0:
lp += 1
else:
ans.append([nums[i], nums[lp], nums[rp]])
# 去重，跳过相同的数
while lp < rp and nums[lp] == nums[lp + 1]:
lp += 1
# 去重，跳过相同的数
while lp < rp and nums[rp] == nums[rp - 1]:
rp -= 1
lp += 1
rp -= 1
return ans
|
42. 接雨水 [动态规划/双指针/单调栈]
朴素想法：按列进行计算，遍历数组，每次循环计算当前柱子可以接的雨水量。由于是一根柱子，所以宽度就是 1，只需要判断可以接雨水的高度是多少即可。这个高度显然取决于当前柱子左侧最大值和当前柱子右侧最大值中较小的那个，再减去当前柱子的高度，即
$$
water[i] = min(max(height[0.. i-1]), max(height[i+1.. n])) - height[i]。
$$
动态规划
如果已经知道每个位置两边的最大高度，则可以在 O(n) 的时间内得到能接的雨水总量。使用动态规划的方法，可以在 O(n) 的时间内预处理得到每个位置两边的最大高度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
left_max, right_max = [0] * n, [0] * n
# 初始状态
left_max[0] = height[0]
right_max[n - 1] = height[n - 1]
# 预计算最大高度的数组
for i in range(1, n):
left_max[i] = max(height[i], left_max[i - 1])
for i in range(n - 2, -1, -1):
right_max[i] = max(height[i], right_max[i + 1])
# 累加答案
ans = 0
for i in range(n):
ans += min(left_max[i], right_max[i]) - height[i]
return ans
|
双指针
动态规划的做法中，需要维护两个数组 left_max 和 right_max，因此空间复杂度是 O(n)，可以使用双指针方法来把空间复杂度降到 O(1)。优化想法就是，在我们预计算最大高度的数组时，有一次正向遍历和一次反向遍历，可以把两个遍历合在一起，并在遍历的时候就把当前柱子能接的雨水计算出来，而不是得到最大高度数组后再进行一次遍历。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
left_max = right_max = 0
lp, rp = 0, len(height) - 1
while lp < rp:
left_max = max(left_max, height[lp])
right_max = max(right_max, height[rp])
if left_max < right_max:
ans += left_max - height[lp]
lp += 1
else:
ans += right_max - height[rp]
rp -= 1
return ans
|
单调栈
这道题的解法很多，官解中还有一个单调栈（栈底到栈顶递减）的解法：遍历数组进栈，如果此时栈内有两个元素并且当前元素大于栈顶元素，那么就有一个可以接雨水的区域，因为三个元素分别是大-小-大，下称为大左，小，大右（当前遍历到的元素）。那么宽度是大右的索引减去大左的索引再减一，高度是大左和大右中的最小值减去小。这实际上是一种按行处理的方法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
n = len(height)
stack = []
for i, h in enumerate(height):
while stack and h > height[stack[-1]]:
top = stack.pop()
if not stack:
break
left = stack[-1]
currWidth = i - left - 1
currHeight = min(height[left], height[i]) - height[top]
ans += currWidth * currHeight
stack.append(i)
return ans
|
滑动窗口
滑动窗口的一般解法是：枚举右边界，加入到窗口后，不断缩小左边界以满足条件。
本题因为条件是是否重复，所以枚举右边界后，先进行调整，再加入到窗口。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
ans = 0
window = deque()
# 枚举右边界
for c in s:
# 不断缩小左边界
while c in window:
window.popleft()
# 加入到窗口
window.append(c)
ans = max(ans, len(window))
return ans
|
相似题
209. 长度最小的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
left = 0
sum_ = 0
ans = float("inf")
# 枚举右边界
for right in range(len(nums)):
# 加入到窗口
sum_ += nums[right]
# 不断缩小左边界
if sum_ >= target:
while sum_ - nums[left] >= target:
sum_ = sum_ - nums[left]
left += 1
ans = min(ans, right - left + 1)
return ans if ans != float("inf") else 0
|
713. 乘积小于 K 的子数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def numSubarrayProductLessThanK(self, nums: List[int], k: int) -> int:
if k <= 1:
return 0
left = 0
ans = 0
prod = 1
# 枚举右边界
for right in range(len(nums)):
# 加入到窗口
prod *= nums[right]
# 不断缩小左边界
while prod >= k:
prod //= nums[left]
left += 1
ans += right - left + 1
return ans
|
76. 最小覆盖子串
详见“子串”小节
把获取一个子串变为维护一个子串（窗口），并且比对方法不使用排序而是使用计数。
在【49. 字母异位词分组】中有提及，异位词的处理方法有排序和计数两种。使用 Python 写题时，建议自己写计数方法而不是使用 collections.Counter，实测后者更慢。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
s_len, p_len = len(s), len(p)
# 边界情况：当 s 长度比 p 小
if s_len < p_len:
return []
ans = []
s_count = [0] * 26
p_count = [0] * 26
# 初始化窗口
for i in range(p_len):
s_count[ord(s[i]) - ord("a")] += 1
p_count[ord(p[i]) - ord("a")] += 1
# 边界情况：第一个子串就符合要求
if s_count == p_count:
ans.append(0)
# 右进一位，左出一位
for i in range(p_len, s_len):
s_count[ord(s[i]) - ord("a")] += 1
s_count[ord(s[i - p_len]) - ord("a")] -= 1
if s_count == p_count:
ans.append(i - p_len + 1)
return ans
|
总结
滑动窗口的题需要满足单调性，先观察题目找到一个“窗口”，然后使用两个指针表示出来，再开始不断开始滑动，根据条件进行判断。
子串
前缀和模板题
303. 区域和检索 - 数组不可变
首先，Python 中 sum(nums[left : right + 1]) 的写法相当于每次 sumRange() 时都要遍历一次数组，时间复杂度较高。而前缀和总共只需要遍历一次数组。
注意到当 left < right 时，sumRange(left, right) 可以写成如下形式：
$$
sumRange(left,right) = \sum_{k=left}^{right}nums[k] = \sum_{k=0}^{right}nums[k] - \sum_{k=0}^{left-1}nums[k] = sums[right+1] - sums[left]
$$
因此，我们可以把连续子数组的元素和转换成两个前缀和的差。如果可以在初始化的时候计算出数组 nums 在每个下标处的前缀和，即可满足每次调用 sumRange 的时间复杂度都是 O(1)。
1
2
3
4
5
6
7
8
9
10
|
class NumArray:
def __init__(self, nums: List[int]):
sums = [0] * (len(nums) + 1)
for i, x in enumerate(nums):
sums[i + 1] = sums[i] + x
self.sums = sums
def sumRange(self, left: int, right: int) -> int:
return self.sums[right + 1] - self.sums[left]
|
此处 sums 前缀和数组的长度设置为 len(nums) + 1，并把 sums[0] 设置为 0 是为了不需要特殊判断 left == 0 的情况。
假设 i < j，当 nums[i] 到 nums[j-1] 的元素和等于 k 时，用前缀和表示即 sums[j] - sums[i] = k，这个形式和【1. 两数之和】是一样的。两数之和使用哈希表进行优化，本题亦是如此。
我们可以枚举 j，将上式变成 sums[i] = sums[j] -k，我们需要计算有多少个 sums[i] 满足 i < j 且 sums[i] = sums[j] -k。即已知 sums[j] 和 k，统计 sums[0] 到 sums[j-1] 中有多少个数等于 sums[j] - k。
使用哈希表来保存出现过的和为某个值的次数，键是子数组之和，值是出现的次数。这样在我们遍历到 j 时，先计算当前 [0..j] 的总和 pre，然后计算其与目标 k 的差值 pre - k，如果这个差值在之前的数组中出现过，那说明从那个数组的下一个数开始到当前位置的和恰好是 k。注意哈希表的初始状态是 count[0] = 1，表明和为 0 的次数是 1，即一个空的子数组。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
count = collections.defaultdict(int)
count[0] = 1
ans = 0
pre = 0
for x in nums:
pre += x
ans += count[pre - k]
count[pre] += 1
return ans
|
我们可以构造一个单调队列，队列中存储的是数组元素的下标，并且保证队列对应的数值从队首到队尾严格单调递减，即队首为当前窗口的最大值。
- 保持递减性：当遍历到新的元素
nums[i] 时，若其值大于或等于队尾对应的值，则不断弹出队尾元素，直到队列重新满足单调递减。这保证了队首始终是当前窗口的最大值下标。
- 移除过期元素：当窗口右移时，如果队首的下标已经不在当前窗口范围内（即
q[0] <= i - k），就将队首弹出。
由于每个元素最多只会入队和出队各一次，整个算法的时间复杂度是 O(n)，空间复杂度是 O(k)，效率最优。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
ans = []
for i, x in enumerate(nums):
# 先移除过期元素
if q and q[0] <= i - k:
q.popleft()
# 保持队列递减性
while q and nums[q[-1]] <= x:
q.pop()
q.append(i)
# 当形成窗口时，加入答案
if i >= k - 1:
ans.append(nums[q[0]])
return ans
|
滑动窗口
先扩右，当满足条件后尽量缩左
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def minWindow(self, s: str, t: str) -> str:
m = len(s)
t_count = [0] * 128 # ASCII 码范围是 0-127
for c in t:
t_count[ord(c)] += 1
left = 0
ans_left, ans_right = -1, m
# 开始枚举右边界
for right in range(m):
# 加入到窗口中
t_count[ord(s[right])] -= 1
# 满足条件的情况下不断缩小左边界
while all(x <= 0 for x in t_count):
# 缩小左边界之前先尝试更新答案
if right - left < ans_right - ans_left:
ans_left, ans_right = left, right
t_count[ord(s[left])] += 1
left += 1
return s[ans_left : ans_right + 1] if ans_left >= 0 else ""
|
每一次判断是否涵盖时，都需要遍历一次 t_char_count 数组，那么有没有办法再优化呢？
再引入一个变量 diff，用来记录目前子串中有多少种字母出现次数和 t 中不一样。这样判断是否涵盖的条件就变成了 diff == 0，在加入新字符和移除时，相应地加入对 diff 的维护。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def minWindow(self, s: str, t: str) -> str:
m, n = len(s), len(t)
t_char_count = defaultdict(int)
for c in t:
t_char_count[c] += 1
diff = len(t_char_count)
left = 0
ans_left, ans_right = -1, m
for right in range(m):
t_char_count[s[right]] -= 1
if t_char_count[s[right]] == 0:
diff -= 1 # 此类字符已满足
while diff == 0:
if right - left < ans_right - ans_left:
ans_left, ans_right = left, right
if t_char_count[s[left]] == 0:
diff += 1 # 出现了一类不满足的字符
t_char_count[s[left]] += 1
left += 1
return s[ans_left : ans_right + 1] if ans_left >= 0 else ""
|
普通数组
状态转移方程：当前数组子数组位置的最大值要么是之前的加上当前值，要么是当前值自成一个新段。
$$
f(0) = nums[0] \\
f(i) = max\{f(i-1)+nums[i],nums[i]\}
$$
1
2
3
4
5
6
7
8
|
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
f = [0] * n
f[0] = nums[0]
for i in range(1, n):
f[i] = max(f[i - 1] + nums[i], nums[i])
return max(f)
|
这道题还有个分治想法，在此不表。
直接分类讨论不可取，情况太多了容易把人绕晕。可以先对左端点进行排序，这样可以减少讨论的情况。
左端点排序后，只有三种情况：
-
当数组为空时，直接插入。
举例：初始化插入第一个区间
-
当插入区间的左端点大于数组最后一个区间的右端点时，直接插入。
举例：数组最后一个区间是 [2,4]，插入区间是 [5,6]
-
当数组不为空，且插入区间的左端点小于或等于数组最后一个区间的右端点时，进行合并（可以直接修改右边界）。
举例：数组最后一个区间是 [2,4]，插入区间是 [3,6]，合并成 [2,6]。
可以看到排序后，我们无需考虑左端点间的比较情况和数值的修改，因为已经有序。
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
intervals.sort(key=lambda x: x[0])
ans = []
for x in intervals:
if not ans or ans[-1][1] < x[0]:
ans.append(x)
else:
ans[-1][1] = max(ans[-1][1], x[1])
return ans
|
朴素想法：python 的切片用法
1
2
3
4
|
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k %= len(nums)
nums[:] = nums[-k:] + nums[:-k]
|
正常通过，但内存消耗严重。
正解是使用 3 次反转完成，一般化：
设 nums=A+B，其中 A 是 nums 的前 n−k 个数，B 是后 k 个数。要求把 A+B 变成 B+A。
- 把 nums 反转，得到 rev(B)+rev(A)，其中 rev(A) 表示数组 A 反转后的结果。
- 单独反转 rev(B)，因为一个数组反转两次是不变的，所以 rev(rev(B))=B，我们得到了 B。
- 同理单独反转 rev(A)，得到 A。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
def reverse(i: int, j: int) -> None:
while i < j:
nums[i], nums[j] = nums[j], nums[i]
i += 1
j -= 1
n = len(nums)
k %= n
reverse(0, n - 1)
reverse(0, k - 1)
reverse(k, n - 1)
|
但在 Python 实现中，这两种方法在实际内存上没有区别，甚至 3 次反转的方法用时更长。暂未想通，猜测是 python 底层优化或者是不熟悉 python 切片的底层实现。
要求是数组中除了某个值之外其余各元素的乘积，可以分为该元素左侧乘积*该元素右侧乘积，而这两部分乘积可以通过分开的两个循环获得。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(1, n):
left[i] = left[i - 1] * nums[i - 1]
for i in range(n - 2, -1, -1):
right[i] = right[i + 1] * nums[i + 1]
ans = []
for i in range(n):
ans.append(left[i] * right[i])
return ans
|
题目中的进阶要求是：当输出数组不被视为额外空间的情况下，如何把空间复杂度优化到 O(1)。
说实话这个条件与要求感觉是为了出题而出题，意义不是很大，这里也放一个解法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
n = len(nums)
ans = [1] * n # ans 作为输出数组所以不计入空间复杂度计算中
# 计算左侧的乘积
left_product = 1
for i in range(n):
ans[i] = left_product
left_product *= nums[i]
# 计算右侧的乘积
right_product = 1
for i in range(n - 1, -1, -1):
ans[i] *= right_product
right_product *= nums[i]
return ans
|
朴素想法：
- 把数组转成哈希表，最后从 1 开始判断是否在哈希表中。时间复杂度 O(n) 满足要求，但空间复杂度是 O(n) 不满足要求。
- 排序。空间复杂度是 O(1) 满足要求，但时间复杂度是 O(nlogn) 不满足要求。
本题解法是把题中给的数组视为哈希表，这样不需要使用额外的空间，满足 O(1) 的空间复杂度。
观察题目：对于一个长度为 N 的数组，其中没有出现的最小正整数只能在 [1,N+1] 中。
因此整理原来的数组：遍历数组的索引 i，在每个位置上不断交换，直到 nums[i] 要么是非法值（不可能放进 [1..n] 这个索引区间的数，比如负数和大于 n 的数），要么是已经在正确位置。这样处理完之后，就等价于“索引 i 指向的数（即nums[i]）应该为 i+1”。只需要一次扫描就能知道缺失的第一个正数。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# 将每个数字放到它应该在的位置上
for i in range(n):
# 对于合法的 nums[i]，它应该在 nums[i] - 1 这个下标位置
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
# 检查哪个位置的数字不符合 nums[i] = i + 1
for i in range(n):
if nums[i] != i + 1:
return i + 1
# 如果都符合，则缺失的数字是 n + 1
return n + 1
|
注意这里的
1
|
nums[nums[i] - 1], nums[i] = nums[i], nums[nums[i] - 1]
|
不能写成
1
|
nums[i], nums[nums[i] - 1] = nums[nums[i] - 1], nums[i]
|
这是不等价的。
矩阵
正常的思路：使用两个标记数组来保存当前行和列是否存在 0。首先遍历一遍矩阵获得两个标记数组，然后根据标记数组再遍历一遍矩阵进行置零。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
row, col = [False] * m, [False] * n
for i in range(m):
for j in range(n):
if matrix[i][j] == 0:
row[i] = col[j] = True
for i in range(m):
for j in range(n):
if row[i] or col[j]:
matrix[i][j] = 0
|
以上解法的空间复杂度是 O(m+n)，题目还要求对空间复杂度进行优化。
思路是用两个变量先记录第一行和第一列是否要置零（把这些空间释放出来），然后把后续其他行和列的信息直接保存到矩阵第一行和第一列中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
m, n = len(matrix), len(matrix[0])
flag_col0 = any(matrix[i][0] == 0 for i in range(m))
flag_row0 = any(matrix[0][j] == 0 for j in range(n))
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[i][0] = matrix[0][j] = 0
for i in range(1, m):
for j in range(1, n):
if matrix[i][0] == 0 or matrix[0][j] == 0:
matrix[i][j] = 0
if flag_col0:
for i in range(m):
matrix[i][0] = 0
if flag_row0:
for j in range(n):
matrix[0][j] = 0
|
至于题解方法三：使用一个标记变量，个人不太喜欢， 在此不表。
进行模拟，初始位置是矩阵的左上角，初始方向是向右，当路径超出界限或者进入之前访问过的位置时，顺时针旋转，进入下一个方向。
这里的难点在于如何判断旋转时机，有两个方案：
- 使用辅助数组来标记是否访问过，搭配路径是否越界来判断，空间复杂度 O(mn)。
- 使用 4 个变量不断更新矩阵边界，空间复杂度 O(1)。
辅助数组写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
ans = []
visited = [[False] * n for _ in range(m)]
di = [[0, 1], [1, 0], [0, -1], [-1, 0]]
i, j, current_di = 0, 0, 0
for _ in range(m * n):
ans.append(matrix[i][j])
visited[i][j] = True # 标记已访问
next_i, next_j = i + di[current_di][0], j + di[current_di][1]
if 0 <= next_i < m and 0 <= next_j < n and not visited[next_i][next_j]:
i, j = next_i, next_j
else:
current_di = (current_di + 1) % 4
i, j = i + di[current_di][0], j + di[current_di][1]
return ans
|
更新矩阵边界写法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
m, n = len(matrix), len(matrix[0])
top, bottom, left, right = 0, m - 1, 0, n - 1
ans = []
while left <= right and top <= bottom:
# 上边: 左->右
for j in range(left, right + 1):
ans.append(matrix[top][j])
top += 1
if top > bottom:
break
# 右边: 上->下
for i in range(top, bottom + 1):
ans.append(matrix[i][right])
right -= 1
if left > right:
break
# 下边: 右->左
for j in range(right, left - 1, -1):
ans.append(matrix[bottom][j])
bottom -= 1
if top > bottom:
break
# 左边: 下->上
for i in range(bottom, top - 1, -1):
ans.append(matrix[i][left])
left += 1
# 此处可以不用判断，直接继续循环
return ans
|
**观察得：对于矩阵中第 i 行的第 j 个元素，在旋转后，它出现在倒数第 i 列的第 j 个位置。**转换成代码语言：对于矩阵中的元素 matrix[row][col]，在旋转后，它的新位置为 matrix_new[col][n- row - 1]。
1
2
3
4
5
6
7
8
|
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
matrix_new = [[0] * n for _ in range(n)]
for i in range(n):
for j in range(n):
matrix_new[j][n - i - 1] = matrix[i][j]
matrix[:] = matrix_new
|
但题目要求不能使用辅助矩阵，因此还得再观察。
观察得：顺时针旋转 90 度 = 水平翻转 + 主对角线翻转。
水平翻转公式：
$$
matrix[row][col]\xrightarrow{\text{水平翻转}}matrix[n-row-1][col]
$$
主对角线翻转公式：
$$
matrix[row][col]\xrightarrow{\text{主对角线翻转}}matrix[col][row]
$$
联立得到：
$$
\begin{align*}
matrix[row][col]\xrightarrow{\text{水平翻转}}matrix[n-row-1][col] \\
\xrightarrow{\text{主对角线翻转}}matrix[col][n-row-1]
\end{align*}
$$
和上述第一个观察结果一致
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# 水平翻转
for i in range(n // 2):
for j in range(n):
matrix[i][j], matrix[n - i - 1][j] = matrix[n - i - 1][j], matrix[i][j]
# 主对角线翻转
for i in range(n):
for j in range(i):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
|
本题难点在于怎么利用已知的矩阵特性（每行元素从左往右升序，每列元素从上往下升序）来确定一个数据的搜索空间。
解法一：二分查找
因为有序了，所以可以在对一个行查找时使用二分查找，时间复杂度是 O(mlogn)
1
2
3
4
5
6
7
|
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for row in matrix:
i = bisect.bisect_left(row, target)
if i != len(row) and row[i] == target:
return True
return False
|
Python 二分算法库：https://docs.python.org/zh-cn/3.13/library/bisect.html
解法二：Z 字形查找
上述解法只用了一个有序条件，没有利用全。
观察得：矩阵右上角这个位置，同时具有最大值和最小值性质，即在行中最大，在列中最小。如果我们从矩阵的右上角开始构建子矩阵搜索，子矩阵范围是以 matrix 的左下角为左下角，以 (x,y) 为右上角，即行的范围为 [x,m−1]，列的范围为 [0,y]。那么如果：
- matrix[x,y] == target，搜索完成；
- matrix[x,y] > target，那么 y 可以减一，因为 matrix[x,y] 是当前列的最小值，最小值都大于目标值了，那么该列肯定不存在目标值；
- matrix[x,y] < target，那么 x 可以加一，因为 matrix[x,y] 是当前行的最大值，最大值都小于目标值了，那么该行肯定不存在目标值。
如果在搜索过程中超出了矩阵边界，那么说明矩阵中不存在 target。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
x, y = 0, n - 1
while x < m and y > -1:
if matrix[x][y] == target:
return True
elif matrix[x][y] < target:
x += 1
else:
y -= 1
return False
|
链表
比较自然的哈希表想法：遍历一遍 A，把每个节点都加入到集合中，然后遍历 B，如果有节点存在于集合中，那就是两个链表相交的起始节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
hash_map = set()
a = headA
while a != None:
hash_map.add(a)
a = a.next
b = headB
while b != None:
if b in hash_map:
return b
b = b.next
return None
|
思考如何把空间复杂度降到 O(1)：
链表 headA 和 headB 的长度分别是 m 和 n。假设链表 headA 的不相交部分有 a 个节点，链表 headB 的不相交部分有 b 个节点，两个链表相交的部分有 c 个节点，则有 a+c=m，b+c=n。
使用两个指针，指针 pA 指向 A 头节点，指针 pB 指向 B 头节点。每次循环时同时更新指针 pA 和 pB：
- 如果指针 pA 不为空，则将指针 pA 移到下一个节点；如果指针 pB 不为空，则将指针 pB 移到下一个节点。
- 如果指针 pA 为空，则将指针 pA 移到链表 B 的头节点；如果指针 pB 为空，则将指针 pB 移到链表 A 的头节点。
- 当指针 pA 和 pB 指向同一个节点或者都为空时，返回它们指向的节点或者 null。
也就是如果链表 A 和 B 有相交节点时，那么指针 pA 移动了 a+c+b 次，指针 pB 移动了 b+c+a 次后，两个指针会同时到达两个链表相交的节点。
1
2
3
4
5
6
7
|
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
pa, pb = headA, headB
while pa != pb:
pa = pa.next if pa else headB
pb = pb.next if pb else headA
return pa
|
把每个节点的 next 指针改成指向前一个节点（prev）即可。实现上需要全局定义一个 prev 指针，并在循环中临时存储节点原来的 next 指针。
1
2
3
4
5
6
7
8
9
|
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
current, prev = head, None
while current:
old_next = current.next # 暂存原来的 next
current.next = prev # 把 next 改成 prev
prev = current # 维护 prev 的值
current = old_next # 处理下一个节点
return prev
|
还有个递归解法在此不表。
进阶题
92. 反转链表 II
1 -------------> 2 -------------> 3 -------------> 4 -------------> 5
| |
| |
global_prev global_prev.next
(current)
# 使用 global_prev 记录需要反转的链表的前后节点，即
# - global_prev 是反转链表头节点的 prev
# - global_prev.next 是反转链表的尾节点
# 在反转过程中 global_prev 没有被修改，因此其 next 始终是 2 这个节点
# 反转后情况
1 -------------> 4 -------------> 3 -------------> 2 -------------> 5
| | | |
| | | |
global_prev prev global_prev.next current
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def reverseBetween(
self, head: Optional[ListNode], left: int, right: int
) -> Optional[ListNode]:
global_prev = dummy = ListNode(next=head)
# 找到起始位置的 prev
for _ in range(left - 1):
global_prev = global_prev.next
# 起始位置
current = global_prev.next
# 以下和【206.反转链表】一样
prev = None
for _ in range(right - left + 1):
tmp = current.next
current.next = prev
prev = current
current = tmp
# 处理反转链表的前后关系
global_prev.next.next = current
global_prev.next = prev
return dummy.next
|
链表转数组，然后使用双指针判断是否为回文。（Python 中可以直接构造反向列表然后比较）
1
2
3
4
5
6
7
8
|
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
vals = []
current = head
while current:
vals.append(current.val)
current = current.next
return vals == vals[::-1]
|
题目的进阶要求是 O(n) 时间复杂度和 O(1) 空间复杂度，可以采用“找中点 → 反转后半段 → 头尾对比”的方法。
如何找链表的中点？参考 876. 链表的中间结点，采用快慢指针的方法。
这里推荐观看 环形链表II【基础算法精讲 07】，涉及本题以及下两道题目。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution:
# 【876. 链表的中间结点】
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
# 【206. 反转链表】
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
current, prev = head, None
while current:
old_next = current.next
current.next = prev
prev = current
current = old_next
return prev
def isPalindrome(self, head: Optional[ListNode]) -> bool:
# 找到链表中间位置
mid = self.middleNode(head)
# 将链表后半段反转
head2 = self.reverseList(mid)
while head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True
|
最简单的就是遍历所有节点，然后加入到哈希表中，当某节点已在表中，则存在环。
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
s = set()
current = head
while current:
s.add(current)
current = current.next
if current in s:
return True
return False
|
本题进阶是对空间复杂度有要求，这里引入一个算法叫快慢指针。
Floyd 判圈算法（又称龟兔赛跑算法）
假想乌龟和兔子在链表上移动，兔子跑得快，乌龟跑得慢。当乌龟和兔子从链表上的同一个节点开始移动时，如果该链表中没有环，那么兔子将一直处于乌龟的前方；如果该链表中有环，那么兔子和乌龟一定会相遇。因为兔子会先于乌龟进入环，并且一直在环内移动。等到乌龟进入环时，由于兔子的速度快，它一定会在某个时刻与乌龟相遇，即套了乌龟若干圈。
本题中可以用一个快指针表示兔子，一个慢指针表示乌龟。快指针每次走两步，慢指针每次走一步。如果链表里面存在环的话，快慢指针最终一定会相遇。
1
2
3
4
5
6
7
8
9
|
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
return True
return False
|
这题相比上题的区别就是需要返回开始入环的第一个节点。
哈希表
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
s = set()
current = head
while current:
s.add(current)
current = current.next
if current in s:
return current
return None
|
快慢指针
可以先判定是否有环，再找到环的入口。
- 判断是否有环（同上题）
- 找到环的入口：从头结点 head 和第一步中的相遇点 meet 各起一个指针，每次走 1 步。head 和 meet 相遇时，就是环的入口结点。
正确性推导：
设链表头结点到环入口的长度为 a，环入口到相遇点的长度为 b，相遇点到环入口的剩余长度为 c，环的长度 L = b + c 。
那么，当快慢指针第一次相遇时：
-
慢指针走了 a + b
-
快指针走了 a + b+ kL（k ≥ 1）
-
且快指针路程是慢指针的 2 倍：
$$
\begin{align}
2(a+b) &= a + b + kL \\
a &= kL - b \\
a &\equiv -b \pmod{L} \\
又因 \ c &= L - b ≡ -b \pmod{L} \\
所以 \ a &\equiv c \pmod{L}
\end{align}
$$
最后的推导式在数学上含义是：a 和 c 除以 L 的余数相同。
所以从链表头结点出发走 a 步，和从相遇点出发走 c 步，最终会在环的入口处相遇。
这部分建议看视频或其他教程，博主目前也云里雾里的…
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
if slow == fast:
new_slow = head
while new_slow != slow:
new_slow = new_slow.next
slow = slow.next
return new_slow
return None
|
迭代
新构建一个节点，然后根据大小分别将两个链表的节点加入，最后加入剩余的链表元素，返回新节点的 next 指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
current = dummy = ListNode()
while list1 and list2:
if list1.val < list2.val:
current.next = list1
list1 = list1.next
else:
current.next = list2
list2 = list2.next
current = current.next
current.next = list1 if list1 else list2
return dummy.next
|
递归
不断地从两个链表中选出较小者，以此返回作为前一个节点的下一个节点。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
if list1 is None:
return list2
elif list2 is None:
return list1
elif list1.val < list2.val:
list1.next = self.mergeTwoLists(list1.next, list2)
return list1
else:
list2.next = self.mergeTwoLists(list1, list2.next)
return list2
|
模拟：逐位相加
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
current = dummy = ListNode()
carry = 0
while l1 or l2 or carry:
if l1:
carry += l1.val
l1 = l1.next
if l2:
carry += l2.val
l2 = l2.next
current.next = ListNode(carry % 10) # 创建新结点加入链表
current = current.next
carry = carry // 10
return dummy.next
|
简单想法：计算出链表的长度，然后根据 n 得到需要删除的节点的前置节点的位置，使用类似 node.next = node.next.next 进行删除。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
length = 0
current = dummy = ListNode(next=head)
# 计算长度
while head:
length += 1
head = head.next
# 定位
for _ in range(length - n):
current = current.next
# 删除
current.next = current.next.next
return dummy.next
|
这里因为要遍历（从前往后），同时又要找倒数第 n 个（从后往前），因此也可以使用栈，利用其前进后出的特性。在弹出 n 个结点后栈顶元素就是需要删除的节点的前置节点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
current = dummy = ListNode(next=head)
stack = []
# 循环入栈
while current:
stack.append(current)
current = current.next
# 弹出 n 个结点
for _ in range(n):
stack.pop()
# 获取栈顶结点（需要删除的节点的前置节点）
prev = stack[-1]
# 删除
prev.next = prev.next.next
return dummy.next
|
还可以使用双指针方法达到 O(1) 的空间复杂度：
假设初始时左指针指向头结点，右指针指向正数第 n 个结点。然后两个指针一起移动，当右指针指向最后一个结点时，左指针此时正好指向倒数第 n 个结点。
但考虑到我们需要删除倒数第 n 个结点（需要其前置结点），所以需要在头结点前插入一个哨兵结点来解决。修改初始状态，左指针指向哨兵结点，右指针指向原来链表的正数第 n 个结点。这样当右指针指向最后一个结点时，左指针正好指向倒数第 n 个结点的前置结点。
移动前图示：
dummy -------> 1 -------> 2 -------> 3 -------> *4 -------> 5
| |
| |
left right
移动后图示：
dummy -------> 1 -------> 2 -------> 3 -------> *4 -------> 5
| |
| |
left right
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
left = right = dummy = ListNode(next=head)
# 让右指针指向原来链表的正数第 n 个结点
for _ in range(n):
right = right.next
# 两个指针一起移动直至右指针指向最后一个结点
while right.next:
left = left.next
right = right.next
# 左指针的下一个节点就是倒数第 n 个节点
left.next = left.next.next
return dummy.next
|
直接模拟做交换即可，以 head = [1,2,3,4] 为例。
dummy -------> 1 -------> 2 -------> 3 -------> 4
| | |
| | |
prev first second
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
prev = dummy = ListNode(next=head)
while prev.next and prev.next.next:
# 取出两个待交换的节点
first = prev.next
second = first.next
# 交换
prev.next, first.next, second.next = second, second.next, first
# 更新 prev 到下一对的前置节点
prev = first
return dummy.next
|
和上题也是模拟慢慢做，对链表进行分组，对每组先进行翻转，然后处理前后链表的连接关系。
以 head = [1,2,3,4,5], k = 2 为例，先确定 kth 和 group_next 的位置
dummy -------> 1 -------> 2 -------> 3 -------> 4 -------> 5
| | |
| | |
group_prev kth group_next
开始反转 [group_prev.next, kth] 闭区间
group_prev.next kth group_next
| | |
| | |
dummy -------> 1 -------> 2 -------> 3 -------> 4 -------> 5
| |
| |
current prev
反转后结果
group_prev.next group_next
| |
| |
dummy 2 -------> 1 -------> 3 -------> 4 -------> 5
| | ↑ |
| | | |
group_prev prev | current
| |
|-----------------------|
接回到原链表中
prev group_prev.next
| | |
| | |
dummy 2 -------> 1 -------> 3 -------> 4 -------> 5
| | |
| | |
group_prev new_head new_tail
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
group_prev = dummy = ListNode(next=head)
while True:
# 1. 找到本组的第 k 个节点
kth = group_prev
for _ in range(k):
kth = kth.next
if not kth:
return dummy.next # 不足 k 个，直接结束
group_next = kth.next # 反转段的后继
# 2. 反转 [group_prev.next, kth] 闭区间
# 相较于 [206. 反转链表]，这里的 prev 初始值是 group_next 而非 None
current, prev = group_prev.next, group_next
while current != group_next: # 直到跨过 kth
old_next = current.next # 暂存原来的 next
current.next = prev # 把 next 改成 prev
prev = current # 维护 prev 的值
current = old_next # 处理下一个节点
# 3. 接回：prev 是新头，group_prev.next 原来是旧头=>变成新尾
new_head, new_tail = prev, group_prev.next
group_prev.next = new_head
group_prev = new_tail # 更新下一组的前置节点
|
本题是复制一个带有 random 指针的链表。其中的关键难点在于不仅要复制链表节点，还需要复制 random 指针，这个指针可能指向链表中的任意节点，而不仅仅是下一个节点。因此，我们需要通过某种方式确保每个原节点都有一个对应的拷贝节点，并且拷贝节点的 random 指针正确指向另一个拷贝节点。
使用一个哈希表 mp 来保存原链表节点和拷贝节点之间的映射关系。逐个遍历原链表，每遍历到一个节点，判断该节点是否已经复制过，如果没有就创建一个新的拷贝节点并存入哈希表。这种按需创建的写法可以保证 random 指针指向的正确性。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
mp = {} # 原节点 -> 拷贝节点
def get(node):
if not node:
return None
if node not in mp:
mp[node] = Node(node.val)
return mp[node]
cur = head
while cur:
copy = get(cur)
copy.next = get(cur.next)
copy.random = get(cur.random)
cur = cur.next
return mp[head]
|
本题还有一种空间复杂度为 O(1) 的办法，可以看看题解，在此不表。
前置题：147. 对链表进行插入排序，时间复杂度是 O(n²)
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def insertionSortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
while head:
prev = dummy
# 寻找合适的插入位置
while prev.next and prev.next.val < head.val:
prev = prev.next
# 把当前数 head 插入到 prev 和 prev.next 之间
# 这里在插入的同时更新了 head，这样在写法上可以不用临时变量
prev.next, head.next, head = head, prev.next, head.next
return dummy.next
|
本题再使用插入排序时会显示超时，因此本题是需要一个时间复杂度为 O(nlogn) 的排序算法。其中有，归并排序、堆排序、快速排序。题解采用归并排序，并且使用自底向上的归并排序达到了 O(1) 的空间复杂度。
但写法比较复杂，可以自行参考题解，以下是链表转数组进行快排再转回链表的解法
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
vals = []
while head:
vals.append(head.val)
head = head.next
vals.sort()
current = dummy = ListNode()
for v in vals:
current.next = ListNode(v)
current = current.next
return dummy.next
|
基于【21. 合并两个有序链表】这道题，这里是把两个有序链表扩展成了 k 个有序列表，那也可以每次找到所有链表头节点中的最小值然后加入到新链表中。
可以把所有链表的头节点加入到最小堆中，然后不断弹出堆中的最小节点 min_head，如果 min_head.next 不为空，则把它加入到堆中，作为新的该链表的头节点。最后不断循环直到堆为空。
Python 堆队列（heapq）参考：https://docs.python.org/zh-cn/3.13/library/heapq.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
ListNode.__lt__ = lambda a, b: a.val < b.val # 重载比较运算符
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
current = dummy = ListNode()
heads = [head for head in lists if head] # 把每个链表的头节点都加入到列表中
heapq.heapify(heads) # 建堆
while heads:
head = heapq.heappop(heads) # 找到最小的头节点
if head.next:
heapq.heappush(heads, head.next) # 往堆中加入其后继节点
current.next = head # 合并到结果链表中
current = current.next
return dummy.next
|
- 使用双向链表来维护缓存中项的使用顺序。双向链表中的头部表示最近使用的项，尾部表示最久未使用的项。当一个项被访问（通过
get 或 put 操作）时，我们将它移动到链表头部，表示它是最近使用的。当缓存达到容量限制时，我们删除链表尾部的节点（即最久未使用的项）。
- 使用哈希表来存储缓存的键值对。哈希表的 key 是缓存项的
key，value 是对应的 ListNode。通过哈希表，可以在 O(1) 时间内找到任意 key 对应的节点（ListNode），并将该节点移动到链表头部。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
class ListNode:
def __init__(self, key: int = 0, value: int = 0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = {}
# 在头尾节点使用两个哨兵节点简化操作
self.head = ListNode()
self.tail = ListNode()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key in self.cache:
node = self.cache[key]
self.move_to_head(node)
return node.value
else:
return -1
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.value = value
self.move_to_head(node)
else:
node = ListNode(key, value)
if len(self.cache) == self.capacity:
self.del_tail()
self.add_to_head(node)
self.cache[key] = node
def add_to_head(self, node: ListNode):
"""把节点添加到头部"""
head_next = self.head.next
# 1. 修改 head 的 next
self.head.next = node
# 2. 修改 node 的 prev 和 next
node.prev = self.head
node.next = head_next
# 3. 修改原 head.next 的 prev
head_next.prev = node
def move_to_head(self, node: ListNode):
"""将节点移动到头部"""
# 先将节点从链表中移除
node.prev.next = node.next
node.next.prev = node.prev
# 然后重新插入到头部
self.add_to_head(node)
def del_tail(self):
"""删除尾部节点"""
tail_node = self.tail.prev
self.tail.prev = tail_node.prev
tail_node.prev.next = self.tail
del self.cache[tail_node.key]
|
总结
-
对于需要构建新链表的题目（或者处理有时候输出为 None 的题目），可以先创建一个前置节点 dummy（又称哨兵节点），根据情况判断是否需要把它的 next 设为题中链表的头节点，再创建 dummy 的一个副本 current，后续算法修改时只操作 current 变量，这样可以在返回时使用保持不变的 dummy 来返回原链表的头节点。
1
2
3
4
5
6
|
current = dummy = ListNode(next=head)
...
current.next = ...
current = current.next
...
return dummy.next
|
-
链表题如果想不清楚，可以在纸上多画图，标记出各个变量以及 prev/next 关系。
二叉树
递归写法：
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root: Optional[TreeNode]):
if not root:
return
dfs(root.left)
ans.append(root.val)
dfs(root.right)
ans = []
dfs(root)
return ans
|
显式栈写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = []
current = root
while current or stack:
# 先将所有左子节点入栈
while current:
stack.append(current)
current = current.left
# 弹出栈顶元素，将其值加入结果列表
current = stack.pop()
ans.append(current.val)
# 处理右子树
current = current.right
return ans
|
补充
144. 二叉树的前序遍历
递归写法：
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def preorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root: Optional[TreeNode]):
if not root:
return
ans.append(root.val)
dfs(root.left)
dfs(root.right)
ans = []
dfs(root)
return ans
|
显式栈写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
ans = []
stack = []
current = root
while stack or current:
while current:
ans.append(current.val)
stack.append(current)
current = current.left
current = stack.pop()
current = current.right
return ans
|
145. 二叉树的后序遍历
递归写法：
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
def dfs(root: Optional[TreeNode]):
if not root:
return
dfs(root.left)
dfs(root.right)
ans.append(root.val)
ans = []
dfs(root)
return ans
|
显式栈写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def postorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
ans = []
stack = []
current = root
prev = None
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
# 当前节点的右节点为空或者已访问，那么可以将这个根节点加入到序列中
if not current.right or current.right == prev:
ans.append(current.val)
prev = current
current = None # 避免重复
else:
stack.append(current)
current = current.right
return ans
|
如果知道了左子树和右子树的最大深度 left 和 right，那么该二叉树的最大深度即为 max(left, right) + 1，因此可以使用递归解决。
1
2
3
4
5
6
7
8
|
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode]):
if not root:
return 0
return max(dfs(root.left), dfs(root.right)) + 1
return dfs(root)
|
或者更简洁一点，将求解函数本身作为递归函数：
1
2
3
4
5
6
|
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if root:
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1
else:
return 0
|
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
def dfs(root: Optional[TreeNode]):
if not root:
return
dfs(root.left)
dfs(root.right)
root.left, root.right = root.right, root.left
dfs(root)
return root
|
简洁写法：
1
2
3
4
5
6
7
|
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if root:
root.left, root.right = root.right, root.left
self.invertTree(root.left)
self.invertTree(root.right)
return root
|
如果一个树的左子树与右子树镜像对称，那么这个树是对称的。
那么，两个树在什么情况下互为镜像？
- 它们的两个根结点具有相同的值（递归最后判断条件）
- 每个树的左子树都与另一个树的右子树镜像对称
- 每个树的右子树都与另一个树的左子树镜像对称
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def isSymmetric(self, root: Optional[TreeNode]) -> bool:
def dfs(a: Optional[TreeNode], b: Optional[TreeNode]) -> bool:
# 两个节点都是空节点，对称
if not a and not b:
return True
# 两个节点中有一个是空节点，非对称
if not a or not b:
return False
if a.val != b.val:
return False
return dfs(a.left, b.right) and dfs(a.right, b.left)
return dfs(root.left, root.right)
|
简单来看，直径 = 左子树深度 + 右子树深度，但注意直径有可能不经过根节点，因此每次递归时都要进行判断更新答案。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def diameterOfBinaryTree(self, root: Optional[TreeNode]) -> int:
def dfs(root: Optional[TreeNode]):
nonlocal ans
if not root:
return 0
left = dfs(root.left)
right = dfs(root.right)
ans = max(ans, left + right)
return max(left, right) + 1
ans = 0
dfs(root)
return ans
|
广度优先搜索，使用队列解决。
每次循环让队列中所有元素出队列的写法有两种，下面写法是获取当前队列长度然后遍历，还有个写法是复制当前队列后让原队列清空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
queue = deque([root])
ans = []
while root and queue:
tmp = []
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
tmp.append(node.val)
ans.append(tmp)
return ans
|
理论：一个升序数组，其实就是某棵二叉搜索树的中序遍历结果。
选择区间中点 mid = (left + right) // 2 作为根；左半段 [left, mid-1] 建左子树，右半段 [mid+1, right] 建右子树。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def sortedArrayToBST(self, nums: List[int]) -> Optional[TreeNode]:
def dfs(left, right) -> Optional[TreeNode]:
if left > right:
return None
mid = (left + right) // 2
root = TreeNode(val=nums[mid])
root.left = dfs(left, mid - 1)
root.right = dfs(mid + 1, right)
return root
return dfs(0, len(nums) - 1)
|
理论：二叉搜索树中序遍历的结果一定是升序的
简单思路：先进行中序遍历，然后判断得到的数组是否是升序的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
def dfs(root: Optional[TreeNode]):
if not root:
return
dfs(root.left)
nums.append(root.val)
dfs(root.right)
nums = []
dfs(root)
for i in range(len(nums) - 1):
if nums[i] >= nums[i + 1]:
return False
return True
|
优化空间复杂度
边遍历边检查：实时检查当前节点的值是否大于前一个中序遍历到的节点的值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
prev = None
def dfs(node: Optional[TreeNode]):
nonlocal prev
if not node:
return True
if not dfs(node.left):
return False
if prev is not None and node.val <= prev:
return False
prev = node.val
return dfs(node.right)
return dfs(root)
|
迭代写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def isValidBST(self, root: Optional[TreeNode]) -> bool:
stack = []
current = root
prev = float("-inf")
while current or stack:
while current:
stack.append(current)
current = current.left
current = stack.pop()
if current.val <= prev:
return False
prev = current.val
current = current.right
return True
|
与上题一致，还是利用结论：二叉搜索树中序遍历的结果一定是升序的，因此在中序遍历结果中寻找第 K 小的元素。
递归写法（与上题相比只需要改变返回值即可）
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
def dfs(root: Optional[TreeNode]):
if not root:
return
dfs(root.left)
nums.append(root.val)
dfs(root.right)
nums = []
dfs(root)
return nums[k-1]
|
迭代写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def kthSmallest(self, root: Optional[TreeNode], k: int) -> int:
order = []
stack = []
current = root
while stack or current:
while current:
stack.append(current)
current = current.left
current = stack.pop()
order.append(current.val)
current = current.right
return order[k - 1]
|
层序遍历取每层最后一个节点即为二叉树的右视图。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def rightSideView(self, root: Optional[TreeNode]) -> List[int]:
queue = deque([root])
ans = []
while root and queue:
for _ in range(len(queue)):
node = queue.popleft()
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
ans.append(node.val)
return ans
|
这里直接考虑更难的进阶情况：使用原地算法（O(1) 额外空间）展开这棵树。
对于每个节点，先把自己的左子树“塞到右边”，再把原来的右子树链到左子树的最右侧，从而得到先序顺序的右指针链。
从实现上来说，
- 先找到左子树的最右节点 pre；
- 把右子树挂到 pre 右边；
- 把左子树整体搬到右边；
- 清空左指针。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def flatten(self, root: Optional[TreeNode]) -> None:
cur = root
while cur:
if cur.left:
# 1. 找到左子树的最右节点 pre
pre = cur.left
while pre.right:
pre = pre.right
# 2. 把右子树挂到 pre 右边
pre.right = cur.right
# 3. 把左子树整体搬到右边
cur.right = cur.left
# 4. 清空左指针
cur.left = None
cur = cur.right
|
对于任意一棵树而言，
- 前序遍历的形式总是【根节点，左子树的前序遍历结果，右子树的前序遍历结果】。
- 中序遍历的形式总是【左子树的前序遍历结果，根节点，右子树的前序遍历结果】。
思路：
- 先把中序值映射到下标，这样查找根位置的时间是 O(1)。
- 使用 next_root_index 指向在前序数组中下一颗还没构造的子树的根，初始化为 0，即整棵树的根节点位置。
- dfs(l,r) 代表中序区间，根把中序切成左右两半，递归构建。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
index = {v: i for i, v in enumerate(inorder)} # 中序序列“值->下标”映射
next_root_index = 0 # 下一颗需要构建的子树的根节点在前序序列中的位置
def dfs(left, right):
nonlocal next_root_index
if left > right:
return None
root = TreeNode(val=preorder[next_root_index]) # 构建根节点
next_root_index += 1 # 更新下一颗子树根节点位置
mid = index[root.val] # 找到当前根节点在中序序列中的位置
root.left = dfs(left, mid - 1) # 构建左子树
root.right = dfs(mid + 1, right) # 构建右子树
return root
return dfs(0, len(inorder) - 1)
|
本题思路和【560. 和为 K 的子数组】一样，类似求一个二叉树子路径的和，使用前缀和+哈希表解决。在二叉树上，前缀和相当于从根节点开始的路径元素和。
二叉树子路径的和等于当前节点的前缀和减去某个祖先节点的前缀和。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> int:
count = collections.defaultdict(int)
count[0] = 1 # 进入根之前，前缀和为 0 出现 1 次
ans = 0
def dfs(root: Optional[TreeNode], current: int):
nonlocal ans
if not root:
return
current += root.val
ans += count[current - targetSum]
count[current] += 1 # 进入子树，把当前前缀和放入“当前路径”
dfs(root.left, current)
dfs(root.right, current)
count[current] -= 1 # 离开子树，撤销当前前缀和，保证只作用于当前路径
dfs(root, 0)
return ans
|
前置题目（但和本题没有什么关系）
112. 路径总和
“倒着减小”达到递归的写法：不断减小 targetSum，如果碰到叶子节点则判断是否为 0。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
def dfs(root: Optional[TreeNode], targetSum: int):
if not root:
return False
targetSum -= root.val
if not root.left and not root.right: # 判断是否是叶子节点
return targetSum == 0
return dfs(root.left, targetSum) or dfs(root.right, targetSum)
return dfs(root, targetSum)
|
113. 路径总和 II
在上题基础上加入对路径的记录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
def dfs(root: Optional[TreeNode], targetSum: int):
if not root:
return
targetSum -= root.val
path.append(root.val)
if not root.left and not root.right:
if targetSum == 0:
ans.append(path.copy())
dfs(root.left, targetSum)
dfs(root.right, targetSum)
path.pop() # 回溯
ans = []
path = []
dfs(root, targetSum)
return ans
|
推荐：https://www.bilibili.com/video/BV1W44y1Z7AR
对当前节点进行分类讨论：
-
当前节点是空节点：返回空节点
-
当前节点是 p：停止递归，向上返回 p，原因如下：
- 如果 q 在 p 的子树中，则最近公共祖先必然是 p，因此不需要再继续递归。
- 如果 q 不在 p 的子树中，那么最近公共祖先也肯定不会出现在 p 的子树中，因此也不需要继续递归。
-
当前节点是 q：停止递归，向上返回 q，原因和上面一样。
-
其他：根据是否找到了 p 或 q 再分为以下 4 种情况
- 左右子树都找到：最近公共祖先就是当前节点，直接返回当前节点
- 只有左子树找到：最近公共祖先肯定在左子树中，返回递归左子树的结果
- 只有右子树找到：最近公共祖先肯定在右子树中，返回递归右子树的结果
- 左右子树都没找到：以当前节点为根的树中没有最近公共祖先，返回空节点
合并并简化一下分类情况：
- 当前节点是空节点、p、q：返回当前节点
- 其他：是否找到了 p 或 q
- 左右子树都找到：返回当前节点
- 只有左子树找到：返回递归左子树的结果
- 只有右子树找到：返回递归右子树的结果
- 左右子树都没找到：返回空节点
1
2
3
4
5
6
7
8
9
|
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if root in (None, p, q):
return root
left = self.lowestCommonAncestor(root.left, p, q)
right = self.lowestCommonAncestor(root.right, p, q)
if left and right: # 左右都找到
return root # 当前节点是最近公共祖先
return left or right
|
相似题：235. 二叉搜索树的最近公共祖先
这里的树从二叉树变成了二叉搜索树，因此分类讨论可以稍微简单一些：
1
2
3
4
5
6
7
8
|
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
x = root.val
if p.val < x and q.val < x: # p 和 q 都在左子树
return self.lowestCommonAncestor(root.left, p, q)
if p.val > x and q.val > x: # p 和 q 都在右子树
return self.lowestCommonAncestor(root.right, p, q)
return root # 其它
|
核心想法：
对于任意结点 x，能向父节点“贡献”的最大和（叫做 max_gain(x)）只能选择一条分支：
- 当前节点能贡献的最大值 = 自身 + max(左子树能贡献的最大值，右子树能贡献的最大值)
- 并且如果左右子的最大贡献是负数，就不取它。
由于题目要求的最大路径和是可以在某个节点“转弯”，即同时经过它的左右子树：
- 经过当前节点的最大路径和 = 自身 + 左子树能贡献的最大值 + 右子树能贡献的最大值
- 因此在遍历时用一个全局变量来维护最大路径和即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def maxPathSum(self, root: Optional[TreeNode]) -> int:
ans = float("-inf")
def dfs(root: Optional[TreeNode]):
nonlocal ans
if not root:
return 0
left = max(0, dfs(root.left)) # 左子树对父节点的最大单边贡献
right = max(0, dfs(root.right)) # 右子树对父节点的最大单边贡献
ans = max(ans, root.val + left + right) # 以当前节点为拐点的路径和
return root.val + max(left, right) # 往上只能带一边
dfs(root)
return ans
|
图论
遍历每一个格子，发现新岛屿时使用深搜完全探索这个岛，然后找下一个新岛。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m, n = len(grid), len(grid[0])
ans = 0
def dfs(i: int, j: int):
if 0 <= i < m and 0 <= j < n and grid[i][j] == "1":
grid[i][j] = "0"
dfs(i, j - 1)
dfs(i, j + 1)
dfs(i - 1, j)
dfs(i + 1, j)
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
dfs(i, j)
ans += 1
return ans
|
模拟题：先得到初始的状态，然后使用队列模拟腐烂的过程。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
queue = deque()
fresh_count = 0 # 新鲜橘子个数，用于最后判断是否全部腐烂
for i in range(m):
for j in range(n):
if grid[i][j] == 1:
fresh_count += 1 # 初始化：统计新鲜橘子个数
elif grid[i][j] == 2:
queue.append((i, j)) # 初始化：所有腐烂橘子入队列
ans = 0
while queue and fresh_count > 0:
for _ in range(len(queue)):
x, y = queue.popleft()
# 遍历 4 个方向，把新鲜句子变成腐烂橘子
for i, j in (x - 1, y), (x + 1, y), (x, y - 1), (x, y + 1):
if 0 <= i < m and 0 <= j < n and grid[i][j] == 1:
grid[i][j] = 2
fresh_count -= 1
queue.append((i, j))
ans += 1
return ans if fresh_count == 0 else -1
|
本题可简化为：课程安排图是否是有向无环图（DAG），使用拓扑排序解决。
基于 BFS 的拓扑排序（Kahn 算法）
基本思路：
- 计算每个节点的入度
- 将所有入度为 0 的节点加入队列
- 不断从队列取出节点，将其加入结果序列，并将其所有邻接节点的入度减 1
- 如果减 1 后邻接节点的入度变为 0，则将其加入队列
- 重复步骤 3 和 4 直到队列为空
本题中不用返回结果序列，使用 visited 表示已出队的节点数量，如果和 numCourses 一致，那么说明所有节点都已出队，即是有向无环图。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
edges = collections.defaultdict(list)
indegree = [0] * numCourses
# 1. 计算每个节点的入度和邻近关系
for x, y in prerequisites:
indegree[x] += 1
edges[y].append(x)
# 2. 将所有入度为 0 的节点加入队列
q = collections.deque([u for u in range(numCourses) if indegree[u] == 0])
visited = 0
# 3. 不断从队列取出节点
while q:
u = q.popleft()
visited += 1
# 将其所有邻接节点的入度减 1
for v in edges[u]:
indegree[v] -= 1
# 4. 如果减 1 后邻接节点的入度变为 0，则将其加入队列
if indegree[v] == 0:
q.append(v)
return visited == numCourses
|
基于 DFS 的拓扑排序
基本思路：
- 对图中每个未访问的节点进行 DFS
- 在 DFS 过程中，先递归访问当前节点的所有邻接节点
- 当节点的所有邻接节点都已被访问后，将当前节点加入结果序列
- 最后将结果序列反转即可得到拓扑排序。（可以使用栈，从栈顶到栈底的顺序即为拓扑排序结果）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
|
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# 构建邻接表表示图
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[course].append(prereq)
# 记录节点状态：0-未访问，1-正在访问，2-已完成访问
visited = [0] * numCourses
def dfs(course: int):
# 如果当前节点已完成访问，无需重复访问
if visited[course] == 2:
return True
# 标记为正在访问
visited[course] = 1
# 2. 递归访问当前节点的所有邻接节点
for prereq in graph[course]:
# 如果邻接节点正在被访问，说明存在环
if visited[prereq] == 1:
return False
# 如果邻接节点未访问或已完成访问但在递归中检测到环，返回False
if visited[prereq] == 0 and not dfs(prereq):
return False
# 3. 标记当前节点为已完成访问
visited[course] = 2
return True
# 1. 对图中每个未访问的节点进行 DFS
for i in range(numCourses):
if visited[i] == 0:
if not dfs(i):
return False
return True
|
前缀树（又称字典树），通常用来存储字符串。
前缀树的 3 个基本性质：
- 根节点不包含字符，除根节点外每一个节点都只包含一个字符。
- 从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。
- 每个节点的所有子节点包含的字符都不相同。
关键点是每个子节点都存储数量有限的不同字符，以及当前节点是否是终止节点（即代表一个有效字符串）。这里可以用列表做（self.children = [None] * 26），也可以使用字典做，以下是字典做法。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Trie:
def __init__(self):
self.children = {}
self.isEnd = False
def searchPrefix(self, prefix: str) -> Optional["Trie"]:
node = self
for c in prefix:
if c not in node.children:
return None
node = node.children[c]
return node
def insert(self, word: str) -> None:
node = self
for c in word:
if c not in node.children:
node.children[c] = Trie()
node = node.children[c]
node.isEnd = True
def search(self, word: str) -> bool:
node = self.searchPrefix(word)
return node is not None and node.isEnd
def startsWith(self, prefix: str) -> bool:
return self.searchPrefix(prefix) is not None
|
回溯
回溯算法是一种通过试错法（试探+回退）解决约束满足问题的通用策略，常用于解决组合优化、排列、子集生成等问题。其核心思想是逐步构建解，若发现当前路径无法达成目标，则回退到上一步尝试其他可能性。
核心思想
- 试探：按条件扩展当前解的候选可能性。
- 验证：若当前路径不满足约束，立即放弃（剪枝）。
- 回退：撤销上一步选择，回到之前的状态继续尝试其他路径。
操作
也就是说解决一个回溯问题，实际上就是一个决策树的遍历过程。在这个过程中只需要思考三个问题：
- 路径：也就是已经做出的选择；
- 选择列表：也就是你当前可以做的选择；
- 结束条件：也就是到达决策树底层，无法再做选择的条件。
回溯算法模板：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
result = [] # 结果集
path=[] # 路径
def backtracking(选择列表):
# 2.递归结束条件
if 满足结束条件:
# 2.1 存放结果
result.add(满足条件的路径)
# 2.2 返回
return
# 1.选择：在本层集合中遍历元素
for 选择 in 选择列表:
# 1.1 处理节点：做出选择
做选择
# 1.2 递归（缩小数据范围。数据范围缩小到一定程度，会触发递归终止条件）
backtracking(选择列表)
# 1.3 回溯，撤销选择
撤销选择
|
作者：沐林耀锦城
链接：https://leetcode.cn/problems/permutations/solutions/3730167/hui-su-suan-fa-3bu-gao-ding-quan-pai-lie-xkul/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
套上述模板（需要一个标记数组来保证元素不会被重复选择）：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = [] # 结果集
path = [] # 路径
used = [False] * len(nums) # 标记数组
def dfs():
# 递归结束条件：路径长度等于数组长度
if len(path) == n:
ans.append(path.copy())
return
# 遍历所有数字
for i in range(n):
if used[i]: # 如果已经使用过，跳过
continue
# 做选择
path.append(nums[i])
used[i] = True
# 递归
dfs()
# 撤销选择
path.pop()
used[i] = False
dfs()
return ans
|
如果不用标记数组的话，也可以这样写：
dfs 的两个参数分别是当前是第几位，以及可以选择的数的集合。不断枚举下一个位置可以选择的数，每次选择一个数后将其从集合中移除。这种方法无需手动撤销选择。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
ans = []
path = [0] * n
def dfs(i: int, s: set[int]):
if i == n:
ans.append(path.copy())
return
for x in s:
path[i] = x
dfs(i + 1, s - {x})
dfs(0, set(nums))
return ans
|
对于选择列表，考虑选与不选，dfs 中使用 index 参数来表示处理到哪一个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
path = []
def dfs(index: int):
if index == len(nums):
ans.append(path.copy())
return
# 选
path.append(nums[index])
dfs(index + 1)
path.pop()
# 不选
dfs(index + 1)
dfs(0)
return ans
|
隐式的“不选”：
这里的 ans.append(path[:]) 实际上就是“不选”，因此只需要处理“选”这个逻辑即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
ans = []
path = []
def dfs(start: int):
ans.append(path[:]) # 隐式“不选”
for i in range(start, len(nums)):
path.append(nums[i]) # 做选择
dfs(i + 1)
path.pop() # 撤销选择
dfs(0)
return ans
|
更简洁的写法：在原来的数组中不断追加下一个新数
1
2
3
4
5
6
|
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = [[]]
for num in nums:
res += [subset + [num] for subset in res] # 列表加法
return res
|
这题与【46. 全排列】的区别在于：
- 全排列中的选择列表不会发生改变，存在元素被多次选择的情况，因此需要一个标记数组来记住哪些元素已经使用过。
- 而本题中对于每个数字，选择列表都是不一样的，因此就无需标记数组。但需要一个参数来标记当前递归处理到数字串的第几位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
MAPPING = "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"
if not digits:
return []
ans = []
path = []
def dfs(index: int):
if index == len(digits):
ans.append("".join(path))
return
for c in MAPPING[int(digits[index])]:
path.append(c)
dfs(index + 1)
path.pop()
dfs(0)
return ans
|
这里的难点在于怎么排除重复的组合，比如 [2,3] 和 [3,2]。
可以给 dfs 中加入一个参数，指示当前数组从哪一个下标开始。这意味着每次递归只会考虑「当前位置及之后」的元素，这样自然保证了组合里的元素是按固定顺序加入的，不会出现 [3,2] 这种“倒着来的”组合。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
ans = []
path = []
def dfs(index: int):
if sum(path) == target:
ans.append(path.copy())
return
if sum(path) > target:
return
for i in range(index, len(candidates)):
path.append(candidates[i])
dfs(i)
path.pop()
dfs(0)
return ans
|
这里需要知道括号字符串（长度为 n）有效的充分必要条件：
- 左括号 ‘(’ 的数量不能超过 n
- 在任何位置，右括号 ‘)’ 的数量不能超过左括号 ‘(’
- 最终左右括号数量都要等于 n
在回溯过程中检查这些条件即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
ans = []
path = []
def dfs(left, right):
if len(path) == 2 * n:
ans.append("".join(path))
return
if left < n:
path.append("(")
dfs(left + 1, right)
path.pop()
if right < left:
path.append(")")
dfs(left, right + 1)
path.pop()
dfs(0, 0)
return ans
|
这题有一点点像 [994.腐烂的橘子]。
在数组中遍历找到起始字母，通过传递 index 来确定每一次查找的字母，因为这里是按着顺序匹配 word，所以不需要保存 path 或 ans，在长度一致时即可逐层向上返回 True。
这里有一个小技巧，直接修改了 board 数组，省去了使用 used 数组来标记该字母是否访问过。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
m, n = len(board), len(board[0])
def dfs(i: int, j: int, index: int):
if i < 0 or i >= m or j < 0 or j >= n or board[i][j] != word[index]:
return False
if index == len(word) - 1:
return True
temp = board[i][j]
board[i][j] = "#"
for x, y in (i, j + 1), (i, j - 1), (i + 1, j), (i - 1, j):
if dfs(x, y, index + 1):
return True
board[i][j] = temp
return False
for i in range(m):
for j in range(n):
if board[i][j] == word[0]:
if dfs(i, j, 0):
return True
return False
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
class Solution:
def partition(self, s: str) -> List[List[str]]:
n = len(s)
ans = []
path = []
def dfs(start: int):
if start == n:
ans.append(path.copy())
return
for end in range(start + 1, n + 1):
part = s[start:end]
if part == part[::-1]:
path.append(part)
dfs(end)
path.pop()
dfs(0)
return ans
|
逐行放置皇后，每行尝试所有可能的列，如果合法就放置，然后递归处理下一行。到最后一行放完，就得到一个完整的解。
难点：如何快速判断“合法”
皇后能攻击同列、主对角线、副对角线上的棋子，所以用三个集合来记录哪些位置被占用了：
- 列集合 cols：记录哪些列已经有皇后，因为同一列最多只能放一个皇后。
- 主对角线集合 diag1：主对角线的特征是行号 - 列号相等，因此使用 row - col 来表示一条主对角线
- 副对角线集合 diag2：副对角线的特征是行号 + 列号相等，因此使用 row + col 来表示一条主对角线
只要在放置新皇后时，检查对应的 c、r-c、r+c 是否已经出现，就能判断是否冲突。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
|
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
cols = set()
diag1 = set()
diag2 = set()
board = [["."] * n for _ in range(n)]
ans = []
def dfs(row: int):
if row == n:
ans.append(["".join(row) for row in board])
return
for col in range(n):
if col in cols or (row - col) in diag1 or (row + col) in diag2:
continue
# 放置
board[row][col] = "Q"
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
dfs(row + 1)
# 回溯
board[row][col] = "."
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
dfs(0)
return ans
|
二分查找
标准二分查找写法：
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
if nums[mid] < target:
left = mid + 1
else:
right = mid - 1
return left
|
本题条件比【[240. 搜索二维矩阵 II](#240. 搜索二维矩阵 II)】更宽松，仍可以使用 240 的最优解 Z 字形查找。
也可以使用本题想要考察的二分查找：第一种方法是对第一列先进行二分查找，找到数字位于的行中，再对该行进行一次二分查找；第二种方法是把矩阵拼接成数组（题目条件保证拼接后仍有序），再对数组使用一次二分查找即可。
本代码采取第二种方法，先拼接再查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
matrix = [x for row in matrix for x in row]
left, right = 0, len(matrix) - 1
while left <= right:
mid = (left + right) // 2
if matrix[mid] == target:
return True
elif matrix[mid] < target:
left = mid + 1
else:
right = mid - 1
return False
|
先用一次二分找到左边界（第一个大于等于 target 的位置）。再用同样的函数，传入 target+1 来找到第一个大于等于 target+1 的位置，然后 -1 就是右边界。
这题的难点是区间写法是左闭右开（否则会死循环），因此循环判断条件是 left < right。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def lower_bound(x: int) -> int:
left, right = 0, len(nums)
while left < right:
mid = (left + right) // 2
if nums[mid] < x:
left = mid + 1
else:
right = mid
return left
left = lower_bound(target)
right = lower_bound(target + 1) - 1
if left <= right and left < len(nums) and nums[left] == target:
return [left, right]
return [-1, -1]
|
将数组从中间分开成左右两部分的时候，一定有一部分的数组是有序的。
因此对区间 [l, r] 做二分。若 nums[l] <= nums[mid]，说明左半段有序；否则右半段有序。再判断 target 是否落在有序段内，决定收缩哪边。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = (left + right) // 2
if nums[mid] == target:
return mid
# 左半段有序
if nums[left] <= nums[mid]:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
# 右半段有序
else:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
return -1
|
利用右侧是否有序来判断最小值所在区间。
- 如果 nums[mid] 小于等于 nums[right]，说明右半段是有序的，那么最小值不可能在右半段出现，所以 right = mid。
- 如果 nums[mid] 大于 nums[right]，说明最小值在 mid 右侧，移动左边界 left = mid+1
- 循环终止时，left == right，即最小值位置。
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = (left + right) // 2
if nums[mid] <= nums[right]:
right = mid
else:
left = mid + 1
return nums[left]
|
我们需要找到一个「划分位置」，使得：
这样，中位数就可以通过左半部分最大值和右半部分最小值得到。
设：
- 在 nums1 中取前 i 个元素，在 nums2 中取前 j 个元素。
- 要保证：i + j = (m + n + 1) // 2（使左边总长度与右边差不超过 1）。
检查条件：
-
nums1[i-1] <= nums2[j]
-
nums2[j-1] <= nums1[i]
若不满足，调整 i（即在 nums1 上二分搜索）。
因为两个数组都有序，通过二分调整 i，最终可以找到一个「分割点」满足条件。这样：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
while left <= right:
i = (left + right) // 2
j = (m + n + 1) // 2 - i
maxLeft1 = float("-inf") if i == 0 else nums1[i - 1]
minRight1 = float("inf") if i == m else nums1[i]
maxLeft2 = float("-inf") if j == 0 else nums2[j - 1]
minRight2 = float("inf") if j == n else nums2[j]
if maxLeft1 <= minRight2 and maxLeft2 <= minRight1:
if (m + n) % 2 == 0:
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2
else:
return max(maxLeft1, maxLeft2)
elif maxLeft1 > minRight2:
right = i - 1
else:
left = i + 1
|
栈
枚举到右括号时检查栈顶元素是否对应即可，最后的正确条件是栈为空
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def isValid(self, s: str) -> bool:
stack = []
pairs = {"(": ")", "{": "}", "[": "]"}
for char in s:
if char in pairs:
stack.append(char)
else:
if stack and char == pairs[stack[-1]]:
stack.pop()
else:
return False
return not stack
|
使用辅助栈的方法来维护最小值
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.min_stack or x <= self.min_stack[-1]:
self.min_stack.append(x)
def pop(self) -> None:
tmp = self.stack.pop()
if tmp == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
|
直接进行模拟即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def decodeString(self, s: str) -> str:
stack = []
for char in s:
if char != "]":
stack.append(char)
else:
# 取出被 [] 包裹的子串
tmp = []
while stack and stack[-1] != "[":
tmp.append(stack.pop())
stack.pop() # 弹出 '['
# 取出重复次数
num = []
while stack and stack[-1].isdigit():
num.append(stack.pop())
repeat = int("".join(reversed(num))) if num else 1
# 压回重复后的子串
stack.append("".join(reversed(tmp)) * repeat)
return "".join(stack)
|
单调栈基础模型：在一维数组中对每一个数找第一个满足某种条件的数。
本题是在一维数组中对每一个数找到第一个【比自己大】的元素。从栈底到栈顶递减，栈顶元素是栈中最小值。注意单调栈中保存的是数组下标，而不是数。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
ans = [0] * len(temperatures)
stack = []
for i, x in enumerate(temperatures):
# 保持栈顶是最小值的性质（即之前保存在栈中的温度，找到了下一个更高的温度）
while stack and x > temperatures[stack[-1]]:
j = stack.pop()
ans[j] = i - j
stack.append(i)
return ans
|
单调栈基础模型：在一维数组中对每一个数找第一个满足某种条件的数。本题是在一维数组中对每一个数找到第一个【比自己小】的元素
由于面积最大矩形的高度一定是 heights 中的元素，因此可以遍历每一个高度，然后找到其左侧小于当前高度的最近元素下标 left，那么 left+1 就是最左侧的那根柱子；再找到其右侧小于当前高度的最近下标 right，那么 right -1 就是最右侧的那根柱子。这样就达到了最大的宽度 (right -1) - (left+1) + 1 = right - left - 1。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
n = len(heights)
left = [-1] * n
stack = []
for i, h in enumerate(heights):
while stack and h <= heights[stack[-1]]:
stack.pop()
if stack:
left[i] = stack[-1]
stack.append(i)
right = [n] * n
stack.clear()
for i in range(n - 1, -1, -1):
h = heights[i]
while stack and h <= heights[stack[-1]]:
stack.pop()
if stack:
right[i] = stack[-1]
stack.append(i)
ans = 0
for h, l, r in zip(heights, left, right):
ans = max(ans, h * (r - l - 1))
return ans
|
堆
基于堆排序的选择方法，但时间复杂度是 O(nlogn)，官解看起来不太行。
1
2
3
4
5
6
7
|
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
nums = [-x for x in nums]
heapq.heapify(nums)
for _ in range(k - 1):
heapq.heappop(nums)
return -heapq.heappop(nums)
|
先用哈希表统计每个元素的出现次数，再用桶排序思想把出现次数相同的元素放到一个桶中，最后倒序遍历所有桶（因为桶的数组下标是出现次数），把前 k 个元素加入到结果中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# 统计每个元素的出现次数
cnt = Counter(nums)
max_cnt = max(cnt.values())
# 把出现次数相同的元素放到一个桶中
buckets = [[] for _ in range(max_cnt + 1)] # 也可以用 defaultdict(list)
for x, c in cnt.items():
buckets[c].append(x)
# 倒序遍历 buckets，把出现次数前 k 大的元素加入答案
ans = []
for bucket in reversed(buckets):
ans += bucket
if len(ans) == k:
return ans
|
贪心算法
一次遍历，记录一个历史最低点，只需要思考今天卖出能赚多少钱即可。
1
2
3
4
5
6
7
8
|
class Solution:
def maxProfit(self, prices: List[int]) -> int:
ans = 0
min_ = float("inf")
for i, x in enumerate(prices):
min_ = min(min_, x)
ans = max(ans, x - min_)
return ans
|
维护能跳到的最远的距离
1
2
3
4
5
6
7
8
9
|
class Solution:
def canJump(self, nums: List[int]) -> bool:
ans = 0
for i, x in enumerate(nums):
if i <= ans:
ans = max(ans, i + x)
else:
return False
return True
|
在每次跳跃中更新能跳到的最远的距离。
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def jump(self, nums: List[int]) -> int:
jump = 0
farther = 1
while farther < len(nums) - 1:
jump += 1
for i in range(farther + 1):
farther = max(farther, i + nums[i])
return jump
|
优化：遍历数组，在达到能跳到的最远的距离时，再更新跳跃次数。
1
2
3
4
5
6
7
8
9
10
11
12
13
|
class Solution:
def jump(self, nums: List[int]) -> int:
ans = 0
farther = 0
tmp = 0
for i, x in enumerate(nums):
tmp = max(tmp, i + x)
# 到达数组最后一个元素时，不需要再跳跃
if i != len(nums) - 1 and i == farther:
ans += 1
farther = tmp
return ans
|
“同一字母最多出现在一个片段中”意味着一个片段如果包含字母 a，那么所有的字母 a 都需要在这个片段中，于是可以找出所有字母的下标区间，进行合并。
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def partitionLabels(self, s: str) -> List[int]:
last = {c: i for i, c in enumerate(s)} # 每个字母最后出现的下标
ans = []
start = end = 0
for i, c in enumerate(s):
end = max(end, last[c]) # 更新当前区间右端点的最大值
if end == i: # 当前区间合并完毕
ans.append(end - start + 1) # 区间长度加入答案
start = i + 1 # 下一个区间的左端点
return ans
|
动态规划
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
f = [0] * n
f[0] = 1
f[1] = 2
for i in range(2, n):
f[i] = f[i - 1] + f[i - 2]
return f[n - 1]
|
因为本题中前面计算出的 f[i] 永远不会使用到了，因此还可以使用滚动数组进行空间复杂度优化，从 O(n) 降到 O(1)：
1
2
3
4
5
6
7
8
|
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
f0, f1 = 1, 2
for i in range(2, n):
f0, f1 = f1, f0 + f1
return f1
|
把每一排进行左对齐：
$$
\begin{array}{l}
[1] \\\\
[1,1] \\\\
[1,2,1] \\\\
[1,3,3,1] \\\\
[1,4,6,4,1]
\end{array}
$$二维数组下标从 0 开始，则第三行的 2 ：c[2][1] = c[1][0] + c[1][1] = 1 + 1 = 2
即有状态转移方程：
$$
c[i][j] = c[i-1][j-1] + c[i-1][j]
$$
1
2
3
4
5
6
7
8
9
|
class Solution:
def generate(self, numRows: int) -> List[List[int]]:
# 每行首尾元素都是 1，覆盖中间值即可
f = [[1] * (i + 1) for i in range(numRows)]
# 从第三行开始计算
for i in range(2, numRows):
for j in range(1, i):
f[i][j] = f[i - 1][j - 1] + f[i - 1][j]
return f
|
状态转移方程
$$
f[i]=max(f[i-2]+nums[i],f[i-1])
$$
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
f = [0] * n
f[0] = nums[0]
f[1] = max(nums[0], nums[1])
for i in range(2, n):
f[i] = max(f[i - 2] + nums[i], f[i - 1])
return f[n - 1]
|
滚动数组优化：
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def rob(self, nums: List[int]) -> int:
n = len(nums)
if n == 1:
return nums[0]
f0 = nums[0]
f1 = max(nums[0], nums[1])
for i in range(2, n):
f0, f1 = f1, max(f0 + nums[i], f1)
return f1
|
状态转移方程：【每个整数的最少完全平方数数量】等于【减去开根号范围内的某个值得到的数的完全平方数的最少数量】的最小值，再加一。
$$
f[i] = \mathop{min}_{j=1}^{\lfloor\sqrt{i}\rfloor} f[i-j^2] + 1
$$
f[i] 表示最少的完全平方数个数- 由于
0 不需要任何完全平方数，因此初始化 f[0] 为 0。
1
2
3
4
5
6
7
8
9
10
|
class Solution:
def numSquares(self, n: int) -> int:
f = [float("inf")] * (n + 1)
f[0] = 0
for i in range(1, n + 1):
j = 1
while j * j <= i:
f[i] = min(f[i], f[i - j * j] + 1)
j += 1
return f[n]
|
本题还可以使用 BFS 来达到 O(sqrt(n)) 的时间复杂度，在此不表。
状态转移方程：【每个金额的最少硬币个数】等于【减去某个硬币面额得到的该金额的最少硬币个数】的最小值，再加一。
$$
f[i] = \mathop{min}_{j=0...n-1} f[i-coins_j] + 1
$$
1
2
3
4
5
6
7
8
9
|
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
f = [float("inf")] * (amount + 1)
f[0] = 0
for i in range(1, amount + 1):
for coin in coins:
if i - coin >= 0:
f[i] = min(f[i], f[i - coin] + 1)
return f[amount] if f[amount] != float("inf") else -1
|
状态转移方程：【每个子串能否被拼接】等于【检查字典中是否存在某个单词，且剩余的子串能否被拼接】。
$$
f[i] = \bigvee_{0 \leq j < i} \left( f[j] \land \text{s[j:i]} \in \text{wordDict} \right)
$$
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def wordBreak(self, s: str, wordDict: list[str]) -> bool:
n = len(s)
f = [False] * (n + 1)
f[0] = True
word_set = set(wordDict) # 使用 set 来加速单词查找的时间复杂度
for i in range(1, n + 1):
for j in range(i):
if f[j] and s[j:i] in word_set:
f[i] = True
break
return f[n]
|
状态转移方程：【以每个元素为结尾的最长递增子序列长度】等于【之前所有较小元素的最长递增子序列长度加一】。
$$
dp[i] = \max(dp[i], dp[j] + 1) \quad \text{for all } j < i \text{ and } nums[i] > nums[j]
$$
1
2
3
4
5
6
7
8
9
|
class Solution:
def lengthOfLIS(self, nums: list[int]) -> int:
n = len(nums)
f = [1] * n # 每个位置至少有一个自己作为递增子序列
for i in range(1, n):
for j in range(i):
if nums[i] > nums[j]:
f[i] = max(f[i], f[j] + 1)
return max(dp)
|
同时存储最大值与最小值，绕过正数还是负数的考虑
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def maxProduct(self, nums: List[int]) -> int:
n = len(nums)
f_max = [0] * n
f_min = [0] * n
f_max[0] = f_min[0] = nums[0]
for i in range(1, n):
x = nums[i]
f_max[i] = max(x, f_max[i - 1] * x, f_min[i - 1] * x)
f_min[i] = min(x, f_max[i - 1] * x, f_min[i - 1] * x)
return max(f_max)
|
原题是：能不能把数组分成两个子集，使得两个子集和相等？
设数组和为 S。如果 S 是奇数，那肯定不行（因为奇数除以 2 不是整数）。如果 S 是偶数，那么问题转化为：是否存在一个子集，它的和恰好等于 target = S/2。如果能找到，另一半自然也是 S/2，分割成立。
f[j] 表示是否能从数组的部分元素中选出若干个，使得它们的和正好等于 j。
初始条件：和为 0 是永远可以做到的（什么都不选），所以 f[0] = True。
依次考虑数组里的每个数 x，遍历 j 从大到小（下会解释为什么倒序）。如果之前能组成 j - x，那么现在加上 x 就能组成 j，于是：
$$
f[j] = f[j] \ or \ f[j - x]
$$
- 左边的 dp[j] 表示“之前已经能组成 j”。
- 右边的 dp[j - x] 表示“之前能组成 j-x，再加上 x，就能组成 j”。
以 [1,5,11,5] 为例，target = sum(nums)/2 = 11。
初始状态：
1
|
f = [True, False, False, False, False, False, False, False, False, False, False, False]
|
处理第 1 个数 1，倒序 j 从 11 到 1 更新：
- j = 1：f[1] = f[1] or f[0] = False or True = True，即通过 1 本身已经可以组成 1 了
处理第 2 个数 5，倒序 j 从 11 到 5 更新：
- j = 6：f[6] = f[6] or f[1] = False or True = True，即通过 1 和 5 已经可以组成 6 了
- j = 5：f[5] = f[5] or f[0] = False or True = True，即通过 5 本身已经可以组成 5 了
处理第 3 个数 11，倒序 j 从 11 到 11 更新：
- j = 11：f[11] = f[11] or f[0] = False or True = True，即通过 11 本身已经可以组成 11 了
此时其实已经可以返回了，也可以继续算完
处理第 4 个数 5，倒序 j 从 11 到 5 更新：
- j = 10：f[10] = f[10] or f[5] = False or True = True，即通过 5 和 5 已经可以组成 10 了
最终结果：
1
|
f = [True, True, False, False, False, True, True, False, False, False, True, True]
|
即在 [1,5,11,5] 这 4 个数中选取任意出若干个，可以组成的数有 0，1，5，6，10，11。其中我们需要的是组成 11，即 f[target]。
1
2
3
4
5
6
7
8
9
10
11
12
|
class Solution:
def canPartition(self, nums: List[int]) -> bool:
s = sum(nums)
if s % 2 != 0:
return False
target = s // 2
f = [False] * (target + 1)
f[0] = True
for x in nums:
for j in range(target, x - 1, -1):
f[j] |= f[j - x]
return f[target]
|
为什么要倒序？
这里举例说明：数组 [1, 5]，目标和 6。
- 如果正序更新：当处理 1 时，我们会让 dp[1] = True。接下来处理 5 时，更新 dp[6] 时，可能会错误地用到刚刚更新的 dp[1]，这就相当于把 1 用了两次（违背 0/1 背包“一件物品只能用一次”的规则）。
- 倒序更新：确保每个数 x 在一次循环里只被用一次，因为我们不会用到本轮刚刚更新的状态。
个人觉得栈的写法比动态规划好懂（并且时空复杂度一致）：用栈记录“可能成为有效子串起点的下标”。
比如："(()))("，处理前三个 “(()” 时，栈里有两个 ‘(’ 的下标。
到第 4 个 ‘)’ 时，pop 一次 → 还能匹配。
到第 5 个 ‘)’ 时，再 pop → 把最后一个 ‘(’ 用掉。
结果这时候栈只剩哨兵 -1，再遇到 ‘)’ 就会变空 → 必须把这个下标当作新的断点。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1] # 哨兵：上一个无法匹配的位置
ans = 0
for i, ch in enumerate(s):
if ch == "(":
stack.append(i)
else:
stack.pop() # 弹出栈中的一个 '(' 来匹配
if not stack: # 把当前的 ')' 匹配完之后，栈中没有可以再次匹配的 '(' 了
stack.append(i) # 这个 i 成为新的“起点”
else:
ans = max(ans, i - stack[-1])
return ans
|
多维动态规划
设 dp[i][j] 表示从起点 (0, 0) 到达格子 (i, j) 的不同路径数。
初始条件：
-
dp[0][0] = 1，因为起点只有一种路径（即不动）。
-
对于第一行 dp[0][j] = 1，因为机器人只能一直向右走。
-
对于第一列 dp[i][0] = 1，因为机器人只能一直向下走。
1
2
3
4
5
6
7
8
9
|
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
f = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
f[i][j] = f[i - 1][j] + f[i][j - 1]
return f[m - 1][n - 1]
|
和上题基本一致，初始条件需要处理第一行和第一列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
f = [[0] * n for _ in range(m)]
f[0][0] = grid[0][0]
for j in range(1, n):
f[0][j] = f[0][j - 1] + grid[0][j]
for i in range(1, m):
f[i][0] = f[i - 1][0] + grid[i][0]
for i in range(1, m):
for j in range(1, n):
f[i][j] = min(f[i - 1][j], f[i][j - 1]) + grid[i][j]
return f[m - 1][n - 1]
|
中心扩展算法
回文关于中心对称。中心可以是一个字符（奇数长度），也可以是两个字符之间的缝（偶数长度）。从每个中心向两侧扩展，统计能扩到的最长回文。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
class Solution:
def longestPalindrome(self, s: str) -> str:
start, end = 0, 0
def expand(left: int, right: int) -> None:
nonlocal start, end
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
# 跳出循环时 s[left+1:right] 是回文
if right - left - 2 > end - start:
start, end = left + 1, right - 1
for i in range(len(s)):
expand(i, i) # 以 i 为中心（奇数长度）
expand(i, i + 1) # 以 i 与 i+1 为中心（偶数长度）
return s[start : end + 1]
|
动态规划
时间复杂度不如中心扩展算法，感觉也没有中心扩展算法好记，这里跳过。
马拉车算法
官解表示十分复杂， 一般不作为面试内容，这里跳过。
f[i][j] 表示 test1[0:i] 和 test2[0:j] 的最长公共子序列的长度。
状态转移方程：
- 如果 text1[i-1] == text2[j-1]，那么 dp[i][j] = dp[i-1][j-1] + 1；
- 否则：dp[i][j] = max(dp[i-1][j], dp[i][j-1])
边界：dp[0][*]=dp[*][0]=0
1
2
3
4
5
6
7
8
9
10
11
|
class Solution:
def longestCommonSubsequence(self, text1: str, text2: str) -> int:
m, n = len(text1), len(text2)
f = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
f[i][j] = f[i - 1][j - 1] + 1
else:
f[i][j] = max(f[i - 1][j], f[i][j - 1])
return f[m][n]
|
设 dp[i][j] 表示把 word1 的前 i 个字符变成 word2 的前 j 个字符所需的最少操作数。
状态转移：
- 若 word1[i-1] == word2[j-1]：dp[i][j] = dp[i-1][j-1]（最后一个字符相同，无需操作）
- 否则取三种操作的最小值 + 1：
- 插入：dp[i][j-1] + 1（向 word1 末尾插入与 word2[j-1] 相同的字符）
- 删除：dp[i-1][j] + 1（删掉 word1[i-1]）
- 替换：dp[i-1][j-1] + 1（把 word1[i-1] 替换成 word2[j-1]）
边界：
- dp[0][j] = j（空串到长度 j 需要 j 次插入）
- dp[i][0] = i（长度 i 到空串需要 i 次删除）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
|
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i - 1] == word2[j - 1]:
dp[i][j] = dp[i - 1][j - 1]
else:
dp[i][j] = min(
dp[i][j - 1] + 1, # 插入
dp[i - 1][j] + 1, # 删除
dp[i - 1][j - 1] + 1, # 替换
)
return dp[m][n]
|
技巧
把数组所有元素依次做异或，成对出现的数两两抵消为 0，最后只剩下那个只出现一次的数。
详见官方题解 https://leetcode.cn/problems/single-number/solutions/242211/zhi-chu-xian-yi-ci-de-shu-zi-by-leetcode-solution/?envType=study-plan-v2&envId=top-100-liked
1
2
3
|
class Solution:
def singleNumber(self, nums: List[int]) -> int:
return reduce(lambda x, y: x ^ y, nums)
|
Python 语法技巧
- reduce (function, iterable) 把一个函数连续地应用在序列的元素上，前一次的结果作为下一次的输入。
- lambda x, y: x ^ y：匿名函数，接收两个参数 x 和 y，返回它们的按位异或结果。
上述代码的整体效果就是把数组里所有元素依次做异或运算。
摩尔投票算法的核心思想是“抵消”。
- 由于多数元素的出现次数大于
⌊n/2⌋，即超过数组长度的一半，因此在数组中，除了多数元素外，所有其它元素的总出现次数都不足以抵消多数元素。
- 在算法中，
count 的增加和减少相当于在“相互抵消”，当我们遇到一个和候选元素相同的数字时，count 增加；当遇到一个不同的数字时，count 减少。如果 count 变为 0，我们重新选择一个候选元素。
- 即便存在其他元素，它们的出现次数不足以与多数元素的出现次数相抗衡，因此这些非多数元素的影响最终会被“抵消”掉，剩下的最终就是多数元素。
1
2
3
4
5
6
7
8
9
|
class Solution:
def majorityElement(self, nums: List[int]) -> int:
count = 0
candidate = None
for num in nums:
if count == 0:
candidate = num
count += (1 if num == candidate else -1)
return candidate
|
这题类似 [283.移动零]，可以用 3 个指针把数组划分成 0/1/2 这样 3 个区域：
- low：指向所有 0 的最后一个位置。初始化为 0。
- mid：指向当前遍历的元素。初始化为 0。
- high：指向所有 2 的第一个位置。初始化为 n - 1。
用 mid 指针遍历数组直至 mid 超过 high：
- 如果当前数是 0，则与 low 交换，同时 low 往右移动。
- 如果当前数是 1，则无需操作。
- 如果当前数是 2，则与 high 交换，同时 high 往左移动。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
class Solution:
def sortColors(self, nums: List[int]) -> None:
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1
return nums
|
见灵神题解：https://leetcode.cn/problems/next-permutation/solutions/3621022/jiao-ni-cong-ling-kai-shi-si-kao-zhe-ti-9qfrq/?envType=study-plan-v2&envId=top-100-liked
-
从右往左找“下降点” i：找到最大下标 i，使得 nums[i] < nums[i+1]。若不存在这样的 i，说明序列整体非升序（如 [3,2,1]），直接原地反转整个数组，得到最小排列，结束。
-
从右往左找第一个比 nums[i] 大的元素 j：即 j 是右侧尾部中最靠右、且 nums[j] > nums[i] 的位置。
-
交换 i 与 j，反转后缀：交换 nums[i], nums[j]，再把区间 [i+1, n-1] 反转，使后缀变为最小的升序。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
n = len(nums)
# 1. 找下降点 i
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# 2. 从右侧找第一个 > nums[i] 的 j
j = n - 1
while nums[j] <= nums[i]:
j -= 1
# 交换
nums[i], nums[j] = nums[j], nums[i]
# 3. 反转后缀 [i+1, n-1]
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
|