Hot100刷题记录
语言基础
由于本人这里全部使用Python，所以再强调一下Python会在算法中使用到的语言基础。
常用到的数据结构有：列表、元组、字典（哈希表）。
列表list可以作为数组，可以作为堆栈，也可以作为队列使用。
# 数组
arr = [1, 2, 3, 4]
# 输出：3
print(arr[2])
# 在列表尾部添加元素
arr.append(5)
# -1 表示列表的末尾，输出：5
print(arr[-1])
# 模拟堆栈
stack = []
# 把列表尾部作为栈顶
# 在栈顶添加元素
stack.append(1)
stack.append(2)
# 删除栈顶元素并返回该元素
e1 = stack.pop()
# 查看栈顶元素
e2 = stack[-1]
剩下常用的数据结构就是元组tuple和字典dict。这个两个数据结构会经常作为自顶向下动态规划的“备忘录”。
memo = dict()
# 二维动态规划的dp函数
def dp(i, j):
# 元组(i, j)作为哈希表的键
# 用 in 判断键是否存在于哈希表中
if (i, j) in memo:
# 返回键对应的值
return memo[(i, j)]
# 状态转移方程
memo[(i, j)] = ...
return memo[(i, j)]
哈希
什么时候使用哈希法？当我们需要查询一个元素是否出现过，或者一个元素是否在集合里的时候，就需要我们第一时间想到哈希法。
两数之和
题目描述：给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
records = dict()
for idx, val in enumerate(nums):
if target - val not in records:
records[val] = idx
else:
return [records[target - val], idx]
enumerate是Python的内置函数，它的核心作用是：在遍历序列（如列表、元组、字符串等）时，同时获取元素的“索引（下标）”和“元素值”。
可以使得代码更加简洁，避免手动维护计数器的麻烦。
核心场景：遍历时替代range(len())，传统写法需要同时使用range和len，还要通过索引取值。
函数语法：enumerate(iterable, start=0)
- iterable：可迭代对象，如列表、元组、字符串等。
- start：起始索引，默认为0，比如显示“第几个”），可以设置 start=1
fruits = ['apple', 'banana', 'cherry']
for count, fruit in enumerate(fruits, start=1):
print(f"第 {count} 个水果是：{fruit}")
输出结果：
第 1 个水果是：apple
第 2 个水果是：banana
第 3 个水果是：cherry
由于我们不仅要知道元素有没有遍历过，还要知道元素对应的下标，需要使用 key-value 结构来存放元素和下标，于是使用字典 dict 来存储元素和下标。
字母异位词分组
题目描述：给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
示例 1：
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["ate","eat","tea"],["nat","tan"],["bat"]]
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result = defaultdict(list)
for s in strs:
sorted_s = ''.join(sorted(s))
result[sorted_s].append(s)
return list(result.values())
核心算法思想：哈希表分组
- 思想：利用哈希表（字典）将具有相同特征的元素归类到一起。
- Key 的设计（最关键）：
- 字母异位词排序后都会变成同一个字符串。
- 所以，将排序后的字符串作为 key，将原字符串作为 value，将具有相同特征（排序后的字符串相同）的元素归为一类。
关键工具：defaultdict
- 作用：
- 自动初始化：当遇到新的 key 时，会自动初始化一个空列表作为 value。
- 简化逻辑：避免手动判断 key 是否存在，直接使用
result[key]访问即可。
字符串处理技巧：sorted + join
- 代码：
sorted_s = ''.join(sorted(s)) - 步骤分解：
sorted(s)：将字符串s转换为列表，并排序。''.join(sorted(s))：将排序后的列表转换为字符串。
- 为什么必须
join- 字典的 key 必须是 immutable 类型，因此，不能使用列表作为 key。
sorted(s)返回的是一个列表，而不是字符串，不能作为字典的 key。''.join(sorted(s))可以将排序后的列表转换为字符串，从而实现字典的 key 的要求。
字典操作方法：.values()
- 作用：
- 获取字典中所有 value 。
list(...)将dict_values视图对象转换为真正的列表。
时间与空间复杂度
- 时间复杂度：\(O(N * K log K)\)，其中 \(N\) 是字符串个数，\(K\) 是字符串的最大长度。
- 空间复杂度：\(O(N * K)\)，需要存储所有字符串在结果字典中。
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
result = dict()
for s in strs:
sorted_s = ''.join(sorted(s))
if sorted_s not in result:
result[sorted_s] = [s]
else:
result[sorted_s].append(s)
return list(result.values())
最长连续序列
题目描述：给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
result = 1
cnt = 1
nums.sort()
for i in range(1, len(nums)):
if nums[i] == nums[i-1]:
pass
elif nums[i] - nums[i-1] == 1:
cnt += 1
if cnt > result:
result = cnt
else:
cnt = 1
return result
很朴素的想到的一种暴力思路，就是将数组排序，然后遍历数组，如果当前数字和前一个数字相差1，则计数器加1，并更新结果。
列表排序
关注点：
- 在 Python 中，判断列表(数组)是否为空，最简洁、最 Pythonic 的写法是：
if not nums:。if len(nums) == 0:，这种写法也可以，但是略微显得啰嗦。if nums == []:，这种写法效率低下，需要创建临时的空列表。
- 列表排序：
nums.sort()nums.sort()，对列表进行原地排序，是属于列表list的专属方法。- 默认情况下，Python 的列表排序是升序的。如果需要降序，可以使用
nums.sort(reverse=True)。 sorted(nums)，返回一个新的列表，而不是原地修改列表。sorted()是内置函数，不修改原对象，而是返回一个新的对象，可以用于任何可以迭代的对象（列表、元组、字符串、字典、集合等）
请你设计并实现时间复杂度为 \(O(n)\) 的算法解决此问题。
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
st = set(nums) # 把 nums 转成哈希集合
m = len(st)
ans = 0
for x in st: # 遍历哈希集合
if x - 1 in st: # 如果 x 不是序列的起点，直接跳过
continue
# x 是序列的起点
y = x + 1
while y in st: # 不断查找下一个数是否在哈希集合中
y += 1
# 循环结束后，y-1 是最后一个在哈希集合中的数
ans = max(ans, y - x) # 从 x 到 y-1 一共 y-x 个数
if ans * 2 >= m: # ans 不可能变得更大
break
return ans
如果还是采取之前排序的思路的话，那么时间复杂度可以优化到 \(O(nlogn)\)，不符合题目的要求。
核心思路：对于nums中的元素x，以x为起点，不断查找下一个数字x + 1，x + 2，...，直到不能找到下一个数字为止，同时统计序列的长度。
为了做到\(O(n)\)的时间复杂度，需要两个关键优化：
- 创建一个哈希集合，用于存储数组中的元素，这样可以\(O(1)\)的判断某个元素是否存在。
- 如果某个元素
x不是序列的起点，则跳过。为什么？因为以x-1为起点计算出的序列长度，一定比以x为起点计算出的序列长度要长！这样可以避免大量的重复计算。
| 问题 | 答案 |
|---|---|
| set 底层是哈希吗？ | ✅ 是，开放寻址哈希表 |
| 为什么能 O(1) 查找？ | 哈希函数 + 直接定位 + 冲突解决 |
| dict 是哈希吗？ | ✅ 是，和 set 共享底层实现 |
| 最坏情况？ | 哈希冲突极多时退化到 O(n)，但实际很少见 |
| 如何保证效率？ | 优秀哈希函数 + 动态扩容 + 负载因子控制 |
一句话理解：
set和dict就像"智能储物柜"：存东西时算个号直接放，取东西时算个号直接拿，不用一个个找，所以快！🚀
双指针
双指针（Two Pointers）是算法刷题中最核心、最高频的技巧之一。它的本质是通过两个变量（索引或引用）的协同移动，将嵌套循环优化为单层循环。
以下是双指针的使用场景、核心意义及分类总结：
核心意义：为什么要用双指针？
| 维度 | 暴力解法 | 双指针解法 | 提升点 |
|---|---|---|---|
| 时间复杂度 | 通常 \(O(n^2)\) | 通常 \(O(n)\) | 效率大幅提升 |
| 空间复杂度 | 可能需要 \(O(n)\) 哈希表 | 通常 \(O(1)\) | 节省内存 |
| 代码逻辑 | 多层嵌套，易乱 | 单层循环，清晰 | 可读性更强 |
一句话总结：
双指针是用空间换时间（哈希法）之外的另一种优化思路，它通过利用数据的有序性或结构特性，避免不必要的遍历。
四大经典使用场景
1. 左右碰撞指针（Collision Pointers）
特征：两个指针分别在两端，向中间移动。 前提：通常要求数组有序（或具有单调性）。
| 典型问题 | 逻辑 | 代码模板 |
|---|---|---|
| 两数之和 II | 和太大 → 右指针左移 和太小 → 左指针右移 |
while left < right: |
| 三数之和 | 固定一个数，剩下两个用双指针 | 外层 for + 内层 while |
| 盛最多水的容器 | 移动短板，尝试寻找更高边 | if h[l] < h[r]: l++ |
| 反转字符串/数组 | 交换两端，向中间靠拢 | s[l], s[r] = s[r], s[l] |
示例（两数之和 II）：
def twoSum(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return [left + 1, right + 1]
elif s < target:
left += 1 # 和太小，左指针右移增大和
else:
right -= 1 # 和太大，右指针左移减小和
2. 快慢指针（Fast & Slow Pointers）
特征：两个指针在同一端，向同一方向移动，但速度不同。 前提：链表或数组，常用于检测环、找中点、去重。
| 典型问题 | 逻辑 | 代码模板 |
|---|---|---|
| 链表是否有环 | 快指针走 2 步，慢指针走 1 步 相遇则有环 |
fast = fast.next.next |
| 链表找中点 | 快指针到终点时，慢指针正好在中点 | slow = slow.next |
| 删除重复元素 | 快指针探索，慢指针记录有效位置 | if nums[fast] != nums[slow]: slow++ |
| 寻找倒数第 K 个节点 | 快指针先走 K 步，然后同步走 | for _ in range(k): fast = fast.next |
示例（链表判环）：
def hasCycle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next # 走 1 步
fast = fast.next.next # 走 2 步
if slow == fast: # 相遇
return True
return False
3. 滑动窗口（Sliding Window）
特征：双指针维护一个区间，右指针扩张，左指针收缩。 前提：连续子数组/子串问题（求最值、满足条件）。
| 典型问题 | 逻辑 | 代码模板 |
|---|---|---|
| 最大连续 1 的个数 | 右指针扩展，不满足条件时左指针收缩 | while 不满足条件：left++ |
| 长度最小的子数组 | 和 ≥ target 时，尝试收缩左边界 | while sum >= target: |
| 无重复字符的最长子串 | 遇到重复字符，移动左指针直到无重复 | while s[right] in window: |
示例（长度最小的子数组）：
def minSubArrayLen(target, nums):
left = 0
total = 0
min_len = float('inf')
for right in range(len(nums)):
total += nums[right] # 右指针扩张
while total >= target: # 满足条件，尝试收缩
min_len = min(min_len, right - left + 1)
total -= nums[left]
left += 1
return min_len
4. 双指针归并（Parallel Pointers）
特征：两个指针分别在两个独立的结构上遍历。 前提：两个有序数组/链表的合并或比较。
| 典型问题 | 逻辑 | 代码模板 |
|---|---|---|
| 合并两个有序数组 | 谁小取谁，指针后移 | if nums1[p1] < nums2[p2]: |
| 合并两个有序链表 | 同上，操作 next 指针 | if l1.val < l2.val: |
| 寻找两个正序数组的中位数 | 模拟归并过程找到中间位置 | 双指针同步移动 |
示例（合并两个有序数组）：
def merge(nums1, m, nums2, n):
p1, p2 = m - 1, n - 1
p = m + n - 1 # 从后往前填，避免覆盖
while p1 >= 0 and p2 >= 0:
if nums1[p1] > nums2[p2]:
nums1[p] = nums1[p1]
p1 -= 1
else:
nums1[p] = nums2[p2]
p2 -= 1
p -= 1
双指针 vs 哈希法（如何选择？）
这是面试中最容易纠结的点，以 两数之和 为例：
| 特性 | 哈希法 (Hash Map) | 双指针 (Two Pointers) |
|---|---|---|
| 是否需要排序 | ❌ 不需要 | ✅ 需要排序 (O(n log n)) |
| 时间复杂度 | O(n) | O(n log n) (排序) + O(n) (遍历) |
| 空间复杂度 | O(n) (存哈希表) | O(1) (仅指针) |
| 返回内容 | 返回原始下标方便 | 返回值方便（下标会变） |
| 适用场景 | 无序数组，需返回下标 | 有序数组，或空间敏感，或三数之和 |
决策树：
- 题目要求返回原始下标？ → 选 哈希法。
- 题目允许修改数组/排序，且追求空间 O(1)？ → 选 双指针。
- 题目是 三数之和/四数之和？ → 必须 排序 + 双指针（哈希法难以处理去重）。
- 题目是 链表？ → 只能用 双指针（链表不支持随机访问，无法建哈希索引）。
避坑指南与注意事项
- 边界条件：
while left < right还是left <= right？- 链表判空：
while fast and fast.next（先判 fast 再判 next）。
- 死循环风险：
- 确保指针一定会移动（特别是在
if-else分支中）。 - 快慢指针中，快指针必须比慢指针快，否则永远追不上。
- 确保指针一定会移动（特别是在
- 排序副作用：
- 双指针常需排序，排序会打乱原始下标。如果题目要求返回原下标，需先备份索引。
- Python 特性：
- Python 没有真正的指针，数组双指针是索引，链表双指针是对象引用。
- 注意可变对象（如链表节点）的引用修改会影响原结构。
总结速查表
| 场景 | 指针类型 | 移动方向 | 典型题目 |
|---|---|---|---|
| 有序数组查找 | 左右指针 | 相向而行 | 两数之和 II、盛水容器 |
| 链表/环/中点 | 快慢指针 | 同向不同速 | 链表环、找中点、去重 |
| 子数组/子串 | 滑动窗口 | 同向（一扩一缩） | 最小覆盖子串、最大连续 1 |
| 多路归并 | 平行指针 | 同向同步 | 合并有序链表/数组 |
核心心法：
看到“有序数组”想左右指针，看到“链表”想快慢指针，看到“连续子串”想滑动窗口。
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
slow = 0
for i in range(len(nums)):
if nums[i] != 0:
nums[slow], nums[i] = nums[i], nums[slow]
slow += 1
print(nums)
典型的快慢指针，因为要求是在原数组中进行操作，所以不能使用额外的空间。
所谓指针其实是一种标志位，而不是例如C和C++中的实际指针，本题还有一个技巧，其实不难发现交换之前快慢指针之间的元素全部为0，因此这样一直交换下去，最终也就实现了移动零的目的。
Python中交换元素的语法是 a, b = b, a，我们可以借助这个语法来交换元素。
盛最多的水
给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。
找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
class Solution:
def maxArea(self, height: List[int]) -> int:
ans = 0
left = 0
right = len(height) - 1
while left < right:
tmp = (right - left) * min(height[left], height[right])
ans = max(ans, tmp)
if height[left] < height[right]:
# height[left]与右边不管哪一条垂线都无法组成一个比ans更大的面积了
left += 1
else:
# height[right]与左边不管哪一条垂线都无法组成一个比ans更大的面积了
right -= 1
return ans
盛水问题，就是两个指针，一个指向数组的左边，一个指向数组的右边，然后计算两个指针之间的面积，并更新最大面积。
左右指针而非快慢指针，同样只需要遍历一次数组即可解决问题。
三数之和
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
class Solution:
def threeSum(self, nums: list[int]) -> list[list[int]]:
result = []
nums.sort()
n = len(nums)
# 固定一个元素
for i in range(n - 2):
if nums[i] > 0: # 剪枝
break
# 首位元素的去重
if i > 0 and nums[i] == nums[i - 1]: # 去重
continue
# 双指针
left = i + 1
right = n - 1
while left < right:
three_sum = nums[i] + nums[left] + nums[right]
if three_sum == 0:
# 符合条件
result.append([nums[i], nums[left], nums[right]])
# 第二位元素的去重
while left < right and nums[left + 1] == nums[left]:
left += 1
# 第三个元素的去重
while left < right and nums[right - 1] == nums[right]:
right -= 1
# 还需要到下一个不同元素
left += 1
right -= 1
elif three_sum > 0:
# 三数和偏大，右指针移动
right -= 1
else:
# 三数和偏小，左指针移动
left += 1
return result
三数之和的标准解法：
- 外层循环：固定第一个数
nums[i]，其实也就是固定一个，退化为两数之和。 - 内层双指针：在 i+1 到末尾之间，用 left 和 right 找另外两个数。
接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
class Solution:
def trap(self, height: List[int]) -> int:
ans = 0
left_max = right_max = 0
left, right = 0, len(height) - 1
while left < right:
left_max = max(left_max, height[left])
right_max = max(right_max, height[right])
if left_max < right_max:
ans += left_max - height[left]
left += 1
else:
ans += right_max - height[right]
right -= 1
return ans
关键在于每个柱子能接的雨水量，即柱子两边的柱子中较小的一个减去柱子的高度。分别向左和向右找到能看到的最高的柱子。
滑动窗口
一般解决连续子串问题，可以使用滑动窗口。其实滑动窗口就是两个指针，一个指向窗口的左边界，一个指向窗口的右边界。
无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
class Solution:
def lengthOfLongestSubstring(self, s: str) -> int:
char_set = set() # 用集合存储当前窗口的字符，查找速度 O(1)
left = 0
result = 0
for right in range(len(s)):
# 如果当前字符已在窗口中，不断移动左指针直到移除该字符
while s[right] in char_set:
char_set.remove(s[left])
left += 1
# 将当前字符加入窗口
char_set.add(s[right])
# 更新最大长度 (此时窗口是合法的 [left, right])
# 窗口长度 = right - left + 1
result = max(result, right - left + 1)
return result
由于不含有重复字符的最长子串，因此，只需要使用一个集合来存储当前窗口的元素，并使用两个指针来移动窗口。
连续子串问题，理应想到使用滑动窗口来优化解法，其本质还是双指针，利用窗口的左右边界来确定窗口内字符的集合，从而判断窗口是否合法。
窗口的左右边界，以及窗口内字符的集合，都是通过指针移动来更新的。
注意点：添加元素
- 想要排队（有顺序、可重复），用 append (List/Deque)。
- 想要集邮（不重复、不在乎顺序），用 add (Set)。
注意点：移除元素
- pop 通常跟位置/键有关，且会返回被删的东西。
- remove 跟具体的值有关，且不返回东西（返回 None）。
找到字符串中所有字母异位词
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
window_size = len(p)
total_size = len(s)
if total_size < window_size:
return []
result = []
left = 0
need = dict()
window = dict()
for p_item in p:
if p_item in need:
need[p_item] += 1
else:
need[p_item] = 1
for right in range(total_size):
if s[right] in need:
if s[right] in window:
window[s[right]] += 1
else:
window[s[right]] = 1
if need == window:
result.append(left)
if right - left + 1 >= window_size:
if s[left] in window:
window[s[left]] -= 1
left += 1
return result
上面我使用了字典的比较操作，相等是要比较全部的键和值。
同时由于本题是定长的窗口，内部可以不使用循环而仅仅采用条件判断，因为窗口内元素达到数量时，左右会跟随移动。
使用 Counter 进行比较，可以优化我们的代码。
# 请选择 Python3 提交代码，而不是 Python
class Solution:
def findAnagrams(self, s: str, p: str) -> List[int]:
cnt_p = Counter(p) # 统计 p 的每种字母的出现次数
cnt_s = Counter() # 统计 s 的长为 len(p) 的子串 t 的每种字母的出现次数
ans = []
for right, c in enumerate(s):
cnt_s[c] += 1 # 右端点字母进入窗口
left = right - len(p) + 1
if left < 0: # 窗口长度不足 len(p)
continue
if cnt_s == cnt_p: # t 和 p 的每种字母的出现次数都相同
ans.append(left) # t 左端点下标加入答案
cnt_s[s[left]] -= 1 # 左端点字母离开窗口
return ans
Counter的比较运算：
cnt3 = Counter({'red': 20, 'green': 10, 'blue': 0})
cnt4 = Counter({'red': 20, 'green': 10})
print(cnt3 == cnt4)
print(cnt4 < cnt3)
Output：
True
False
注意：
- Counter之间可以进行比较运算，支持
==, !=, <, <=, >, >=。 - 在比较时，如果不存在的元素，会用计数0进行比较，所以上面的cnt3和cnt4相等。
- 对于小于，只要Counter中有一个元素的计数值小于另一个Counter，其他元素的计数值可以相等，此时会返回True。大于同理。
子串
和为K的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
正常暴力思想，遍历所有子数组，求出每一段子数组的和并判断是否等于k。
优化技巧？前缀和思想，空间换时间，利用前缀和，将子数组的和转换为前缀和之差。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
pre_sum = [0]
cnt = 0
# 计算前缀和
for idx, num in enumerate(nums):
pre_sum.append(pre_sum[idx] + num)
for i in range(len(nums)):
for j in range(i + 1, len(nums) + 1):
if pre_sum[j] - pre_sum[i] == k:
cnt += 1
return cnt
超时？即使使用前缀和，还是需要两层循环，时间复杂度仍然为\(O(n^2)\)
优化思路：
- 创建一个字典，用于记录前缀和出现的次数。
- 创建一个变量，记录当前前缀和。
- 遍历数组，将当前前缀和加入字典中，并判断当前前缀和减去k的值是否在字典中，如果存在，则将字典中该值出现的次数加到结果中。
- 更新当前前缀和字典。
依旧空间换时间，利用字典，存储了前缀和出现的次数，空间复杂度\(O(n)\)。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
cnt = 0
pre_sum = 0
records = Counter({0: 1})
for num in nums:
pre_sum += num
cnt += records[pre_sum - k]
records[pre_sum] += 1
return cnt
滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
单调队列问题？一个队列中元素全是单调的数据结构，可以用来解决滑动窗口的一系列问题，比如“滑动窗口最大值”。
一堆数字中，已知最值，如果增加一个数字，比较一下即可得到最新的最值；但如果是减少一个数字，就不能直接得到最值，因为如果减少的数字恰好是最值，就需要遍历所有数重新找出最值。
每个窗口前进时，要添加一个数同时减少一个数，因此想\(O(1)\)时间内得到新的最值，不是一件容易的事情，我们需要“单调队列”这种特殊的数据结构。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if k == 1: return nums
ans, q = [], deque()
for i, num in enumerate(nums):
# 1. 维护单调性 (改为 < 保留重复值)
while q and q[-1] < num:
q.pop()
q.append(num)
# 2. 窗口形成后记录答案
if i >= k - 1:
ans.append(q[0])
# 3. 移除滑出窗口的元素
if q[0] == nums[i - k + 1]:
q.popleft()
return ans
上述是一种存值的思路。不过该思路存在点问题，相同大小的值也需要存，否则可能导致删除之前的值而将现在窗口中的最值丢失的情况。
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
ans = []
q = deque() # 存储索引，不是值
for i in range(len(nums)):
# 1. 移除超出窗口的索引，即左边出
if q and q[0] <= i - k:
q.popleft()
# 2. 维护单调递减队列，即右边入
while q and nums[q[-1]] <= nums[i]:
q.pop()
# 3. 添加当前索引
q.append(i)
# 4. 当窗口形成后，记录结果
if i >= k - 1:
ans.append(nums[q[0]])
return ans
较为可靠的想法，采用存储索引的思路。
这是一个降本增笑的故事：
- 如果新员工比老员工强（或者一样强），把老员工裁掉。（元素进入窗口）
- 如果老员工 35 岁了，也裁掉。（元素离开窗口）
裁员后，资历最老（最左边）的人就是最强的员工了
单调队列套路
- 右边入（元素进入队尾，同时维护队列单调性）
- 左边出（元素离开队首）
- 记录/维护答案（根据队首）
最小覆盖子串
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ""
cnt_t = Counter(t)
window_cnt = Counter()
formed = 0 # 已满足数量要求的字符种类数
required = len(cnt_t) # 需要满足的字符种类数
left = 0
min_len = float('inf')
ans = (0, 0) # (left, right)
for right, char in enumerate(s):
window_cnt[char] += 1
# 如果当前字符在 t 中，且数量已满足要求，注意是等于时才标记一次+1
if char in cnt_t and window_cnt[char] == cnt_t[char]:
formed += 1
# 当所有字符都满足时，尝试收缩左边界
while formed == required:
# ✅ 先记录当前有效窗口，但并不急着记录子串，而是仅仅记录起始和终止位置
if right - left + 1 < min_len:
min_len = right - left + 1
ans = (left, right)
# 收缩左边界
window_cnt[s[left]] -= 1
# 不再满足
if s[left] in cnt_t and window_cnt[s[left]] < cnt_t[s[left]]:
formed -= 1
left += 1
return "" if min_len == float('inf') else s[ans[0]:ans[1] + 1]
下面是我个人的一种写法，但复杂度比上面使用变量追踪是否满足要高。
class Solution:
def minWindow(self, s: str, t: str) -> str:
if not s or not t:
return ""
cnt_t = Counter(t)
cnt_zero = Counter({key: 0 for key in cnt_t})
min_len = float('inf')
ans = ""
left = 0
for right in range(len(s)):
if s[right] in cnt_t:
cnt_zero[s[right]] += 1
# 收缩窗口（在满足条件时）
while cnt_zero >= cnt_t:
# ✅ 先记录当前有效窗口
if right - left + 1 < min_len:
min_len = right - left + 1
ans = s[left:right + 1]
# 再收缩
if s[left] in cnt_t:
cnt_zero[s[left]] -= 1
left += 1
return ans
float('inf') 是 Python 中表示"无限大"的标准方式，常用于初始化最小值搜索！
1. dict 有 get 方法吗？
有！ get 是所有字典（包括 dict 和 defaultdict）的标准方法。
# dict 的 get 方法
d = {'a': 1}
print(d.get('a')) # 1
print(d.get('b')) # None (key 不存在)
print(d.get('b', 0)) # 0 (指定默认值)
print(d.get('b', -1)) # -1 (指定默认值)
2. defaultdict 的 get 方法
defaultdict 继承自 dict，get 方法行为完全相同：
from collections import defaultdict
dd = defaultdict(int, {'a': 1})
print(dd.get('a')) # 1
print(dd.get('b')) # None (key 不存在，不会触发默认工厂)
print(dd.get('b', 0)) # 0
⚠️ 关键点：
get方法不会触发defaultdict的默认工厂函数！
3. get vs [] 的核心区别 ⭐
| 操作 | dict |
defaultdict |
|---|---|---|
d.get(key) |
不存在返回 None |
不存在返回 None |
d.get(key, default) |
不存在返回 default |
不存在返回 default |
d[key] |
不存在抛 KeyError |
不存在自动创建默认值 |
from collections import defaultdict
dd = defaultdict(int)
# 使用 get - 不会创建新 key
print(dd.get('a')) # None
print(dd) # defaultdict(int, {}) 空字典
# 使用 [] - 会创建新 key
print(dd['b']) # 0 (自动创建)
print(dd) # defaultdict(int, {'b': 0}) 有 key 了！
4. 实际应用场景
场景一：计数（推荐用 []）
from collections import defaultdict
# ✅ 推荐：用 [] 自动初始化
cnt = defaultdict(int)
for char in "hello":
cnt[char] += 1 # 不存在时自动为 0
print(cnt) # {'h': 1, 'e': 1, 'l': 2, 'o': 1}
# ❌ 不推荐：用 get 需要手动处理
cnt = {}
for char in "hello":
cnt[char] = cnt.get(char, 0) + 1
场景二：安全读取（用 get）
dd = defaultdict(list, {'a': [1, 2]})
# 只想读取，不想创建新 key
value = dd.get('b', []) # []，不会在 dd 中创建 'b'
print(dd) # defaultdict(list, {'a': [1, 2]})
# 如果用 [] 会创建空列表
value = dd['c'] # 自动创建 'c': []
print(dd) # defaultdict(list, {'a': [1, 2], 'c': []})
场景三：滑动窗口
from collections import Counter, defaultdict
# 方案 1: 用 Counter (推荐)
window_cnt = Counter()
window_cnt['a'] # 返回 0，不会创建 key
# 方案 2: 用 defaultdict
window_cnt = defaultdict(int)
window_cnt['a'] # 返回 0，但会创建 key 'a'
# 方案 3: 用 get (不修改字典)
window_cnt = {}
count = window_cnt.get('a', 0) # 返回 0，不创建 key
5. 完整对比表
| 特性 | dict.get() |
defaultdict.get() |
defaultdict[] |
|---|---|---|---|
| key 不存在时 | 返回 None 或默认值 |
返回 None 或默认值 |
自动创建默认值 |
| 是否修改字典 | 否 | 否 | 是 |
| 触发默认工厂 | 否 | 否 | 是 |
| 适用场景 | 安全读取 | 安全读取 | 计数、累加 |
6. 代码示例
from collections import defaultdict
dd = defaultdict(list)
# get 不会触发默认工厂
print(dd.get('x')) # None
print('x' in dd) # False
print(dd) # defaultdict(list, {})
# [] 会触发默认工厂
print(dd['y']) # [] (空列表)
print('y' in dd) # True
print(dd) # defaultdict(list, {'y': []})
# get 可以指定默认值
print(dd.get('z', [])) # []
print('z' in dd) # False (还是没有创建)
总结
| 问题 | 答案 |
|---|---|
dict 有 get 吗？ |
有，所有字典都有 |
defaultdict.get() 特殊吗？ |
不特殊，和 dict.get() 一样 |
什么时候用 get？ |
只想读取，不想创建新 key |
什么时候用 []？ |
想自动初始化新 key（计数、累加） |
| 会触发默认工厂吗？ | get 不会，[] 会 |
一句话：get 是安全读取，[] 是自动创建！根据需求选择使用。🎯
普通数组
最大子数组和
给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
子数组是数组中的一个连续部分。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
f = [0] * len(nums)
f[0] = nums[0]
for i in range(1, len(nums)):
f[i] = max(f[i - 1] + nums[i], nums[i])
return max(f)
动态规划解法，维护一个f数组，f[i]表示以nums[i]为结尾的子数组的最大和。状态转移方程为：f[i] = max(f[i - 1] + nums[i], nums[i])。初始状态为f[0] = nums[0]。最后返回max(f)。
还可以怎么做？分治思想！左侧最大和右侧最大以及横跨左右最大的比较。
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def merge(left, mid, right):
"""O(n) 计算跨越mid的最大子数组和"""
# 左半部分：以mid结尾的最大后缀和
left_sum = float('-inf')
current = 0
for i in range(mid, left - 1, -1):
current += nums[i]
left_sum = max(left_sum, current)
# 右半部分：以mid+1开头的最大前缀和
right_sum = float('-inf')
current = 0
for j in range(mid + 1, right + 1):
current += nums[j]
right_sum = max(right_sum, current)
return left_sum + right_sum
def maxSum(left, right):
if left == right:
return nums[left]
mid = left + (right - left) // 2
left_max = maxSum(left, mid)
right_max = maxSum(mid + 1, right)
cross_max = merge(left, mid, right)
return max(left_max, right_max, cross_max)
if not nums:
return 0
return maxSum(0, len(nums) - 1)
嵌套函数
学到一招，Python 可以在函数中嵌套函数，从而将辅助函数写在主函数的内部。
避免全局变量，保持代码封闭
# ❌ 不推荐：用类属性/全局变量传状态
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
self.result = 0 # 污染类状态，多测试用例会干扰
return self.helper(nums)
# ✅ 推荐：内部函数 + 闭包，状态隔离
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def helper(left, right):
# 直接访问外层 nums，无需 self
...
return helper(0, len(nums)-1)
递归/分治时参数传递更简洁
# 分治需要 left/right 等额外参数，但题目接口固定
def maxSubArray(self, nums: List[int]) -> int:
def dfs(l, r): # ✅ 内部函数可自定义参数
if l == r: return nums[l]
...
return dfs(0, len(nums)-1)
避免命名冲突，作用域清晰
内部函数只在主函数内可见，不会污染模块命名空间。
合并区间
以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
class Solution:
def merge(self, intervals: List[List[int]]) -> List[List[int]]:
# 按照左端点从小到大排序
intervals.sort(key=lambda p: p[0])
ans = []
for interval in intervals:
# 能合并就进行合并
if ans and interval[0] <= ans[-1][1]:
# 更新右端点的最大值
ans[-1][1] = max(ans[-1][1], interval[1])
else:
# 不相交，无法进行合并
ans.append(interval)
return ans
本题我之前将其视作贪心，可仔细想来有与传统的贪心算法不同，以往贪心是按照哪个排序，就选择哪个最小或者最大，这道题似乎只是一种很自然的解题思路就是：按照左端点排序，然后判断当前区间是否与前一个区间相交，相交就进行合并，否则就加入结果中。
简短回答：区间合并严格来说不算经典贪心，它更像是「排序 + 线性扫描 + 确定性合并」的直接模拟。但它体现了贪心的某些思想，所以很多资料会把它归为"贪心类"。
🔍 一、经典贪心 vs 区间合并：核心差异
| 特征 | 经典贪心（如活动选择） | 区间合并 |
|---|---|---|
| 是否有"选择" | ✅ 要在多个选项中取舍（选/不选某个活动） | ❌ 没有选择，重叠就必须合并 |
| 决策是否可逆 | ✅ 选错了可能后悔（但贪心证明不会后悔） | ❌ 合并是确定性的，不存在"选错" |
| 局部最优→全局最优 | ✅ 需要证明贪心选择性质 | ⚠️ 合并策略是"唯一合理"的，无需证明 |
| 排序目的 | 让贪心选择具有"无后效性" | 让可合并区间相邻出现，便于扫描 |
🎨 对比代码更直观：
# 🎪 活动选择（经典贪心）：有"选/不选"的决策
def maxActivities(intervals):
intervals.sort(key=lambda x: x[1]) # 按结束时间排序
cnt, last_end = 0, -inf
for s, e in intervals:
if s >= last_end:
cnt += 1 # 🔑 决策点：选这个活动！
last_end = e
# else: 跳过（不选） # 🔑 有"舍弃"的操作
return cnt
# 📦 区间合并（确定性模拟）：没有选择，只有合并
def merge(intervals):
intervals.sort(key=lambda x: x[0]) # 按开始时间排序
ans = []
for s, e in intervals:
if ans and s <= ans[-1][1]:
ans[-1][1] = max(ans[-1][1], e) # 🔑 必须合并，没得选
else:
ans.append([s, e]) # 🔑 必须添加，没得选
return ans
💡 关键区别：
活动选择中，else分支是"主动舍弃"；区间合并中，else分支是"不得不添加"。
🎯 二、为什么很多人说区间合并是"贪心"？
因为它符合贪心的某些表层特征：
✅ 特征1：排序 + 线性扫描
→ 和经典贪心写法高度相似
✅ 特征2：局部决策
→ 每遇到一个区间，立即决定"合并"或"新增"
✅ 特征3：无后效性
→ 一旦确定某个区间不能合并，它就可以安全输出，无需回溯
✅ 特征4：右端点取最大
→ 看似"局部最优"：尽可能延长覆盖范围
但这些特征不足以构成严格贪心，因为：
❌ 缺少"选择空间"：重叠区间必须合并，没有"合并不合并"的权衡
❌ 缺少"策略证明"：不需要证明"为什么合并是最优的"，因为这是问题定义
❌ 缺少"取舍权衡"：不像背包、活动选择那样要在冲突选项中做决策
🧠 三、更准确的分类：区间合并是什么？
📦 区间合并 = 排序预处理 + 确定性状态机模拟
1️⃣ 排序阶段：按左端点升序
→ 目的：让"可能重叠"的区间在数组中相邻
→ 本质：数据预处理，不是贪心策略
2️⃣ 扫描阶段：维护一个"当前合并区间"状态
→ 状态转移：
- 若重叠：更新右端点（状态内更新）
- 若不重叠：输出当前状态，开启新状态
→ 本质：确定性有限状态机，不是贪心选择
3️⃣ 合并策略：右端点取 max
→ 看似"贪心"，实则是**问题定义的必然要求**
→ 合并后的区间必须覆盖所有原始区间，所以右端点必须取最大
🎯 一句话总结：
区间合并的"贪心感"来自于写法相似，但逻辑本质是确定性模拟。
🔄 四、对比：什么才是真正的区间贪心？
# 🎯 真正的区间贪心：区间选点（有选择！）
def minPoints(intervals):
"""用最少的点覆盖所有区间"""
intervals.sort(key=lambda x: x[1]) # 按右端点排序
points = []
last_point = -inf
for s, e in intervals:
if s > last_point: # 🔑 决策点：这个区间还没被覆盖！
point = e # 🔑 贪心选择：点放在右端点（覆盖最多后续区间）
points.append(point)
last_point = point
# else: 区间已被覆盖，跳过（主动不选新点）
return len(points)
# ✅ 这才是贪心：
# - 有多个点可选，但贪心选择"右端点"这个局部最优位置
# - 需要证明：为什么选右端点不会导致全局更差
# - 有"选/不选"的决策空间
🎨 五、可视化：两种思维模式
📦 区间合并（确定性模拟）:
输入: [[1,3], [2,6], [8,10]]
状态机视角:
state = None
→ 读[1,3]: state为空 → state = [1,3]
→ 读[2,6]: 2≤3(重叠) → state = [1, max(3,6)] = [1,6] # 确定性更新
→ 读[8,10]: 8>6(不重叠) → 输出[1,6], state = [8,10] # 确定性输出
→ 结束: 输出[8,10]
→ 全程没有"选择"，只有"状态转移"
🎯 活动选择（经典贪心）:
输入: [[1,3], [2,4], [3,5]]
贪心决策视角:
按右端点排序: [[1,3], [2,4], [3,5]]
→ 读[1,3]: 可选 → 🔑 贪心选择: 选它！(结束最早)
→ 读[2,4]: 2<3(冲突) → 🔑 贪心选择: 舍弃！
→ 读[3,5]: 3≥3(不冲突) → 🔑 贪心选择: 选它！
→ 每一步都有"选/舍"的决策，且需要证明决策的最优性
📚 六、算法分类的"灰色地带"
实际上，算法分类本身就有模糊性：
🌈 连续谱系视角：
[纯模拟] ---- [带贪心思想的模拟] ---- [经典贪心] ---- [动态规划]
↑ ↑ ↑
区间合并 区间合并(某些观点) 活动选择/区间选点
→ 区间合并在"带贪心思想的模拟"这个灰色地带
不同资料的不同归类：
| 资料类型 | 常见归类 | 原因 |
|---|---|---|
| 面试突击课 | 贪心专题 | 写法相似，便于记忆 |
| 算法竞赛书 | 排序+模拟 | 强调问题本质 |
| 理论教材 | 不单独归类 | 作为"扫描线"的简单应用 |
| LeetCode标签 | 数组/排序 | 按实现特征分类 |
💡 七、实用建议：不用纠结分类！
🎯 刷题时关注这三点就够了：
1️⃣ 识别模式：
- 看到"区间"+"重叠/覆盖/选择" → 考虑排序+扫描
2️⃣ 确定排序关键字：
- 要"合并/从左处理" → 按左端点
- 要"选择/早结束优先" → 按右端点
3️⃣ 写对判断条件：
- 闭区间重叠: `cur.start ≤ last.end`
- 活动可衔接: `cur.start ≥ last.end`
- 点覆盖闭区间: `cur.start > last_point`
✅ 比纠结"这是不是贪心"更重要！
🔚 终极总结
📦 区间合并的本质：
= 排序(预处理) + 线性扫描(顺序保证) + 确定性合并(问题定义)
🎯 它"像贪心"的原因：
- 写法模式相似: sort + for + if-else
- 有局部决策感: 遇到区间立即处理
- 有"右端点取最大"的策略
❌ 但它不是经典贪心：
- 没有"选择空间": 重叠就必须合并
- 无需"策略证明": 合并方式是问题定义的必然
- 没有"取舍权衡": 不存在"合并可能更差"的情况
💡 学习建议：
把它当作"排序+模拟"的模板题掌握，
遇到类似区间问题能举一反三，
比纠结算法分类标签更有价值！🚀
🎯 一句话记忆：
"区间合并是模拟，贪心思想沾点边；
分类模糊不用管，掌握模式是关键！"
轮转数组
给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。
解法一
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
k = k % len(nums)
nums[:] = nums[-k:] + nums[:-k]
我最先想到的就是切片的方法，直接把原数组进行切片拼接不就可以了吗。
经典陷阱
k = k % len(nums)
nums = nums[-k:] + nums[:-k]
核心问题：nums = ... 没有原地修改！
可视化理解：
调用前:
外部列表: [1,2,3,4,5,6,7] ← 内存地址 0x100
函数参数 nums 指向: 0x100
执行 `nums = nums[-k:] + nums[:-k]` 后:
1. 右边: 创建新列表 [5,6,7,1,2,3,4] ← 新地址 0x200
2. 赋值: 局部变量 nums 现在指向 0x200
3. 但！外部列表仍在 0x100，内容还是 [1,2,3,4,5,6,7] ❌
函数返回后:
- 局部变量 nums (0x200) 被销毁
- 外部列表 (0x100) 纹丝不动 → 测试用例失败！
实验验证：
# 模拟你的代码
def rotate_wrong(nums, k):
k = k % len(nums)
nums = nums[-k:] + nums[:-k] # 重新赋值
print(f"函数内: {nums}") # [5,6,7,1,2,3,4] ✓
arr = [1,2,3,4,5,6,7]
rotate_wrong(arr, 3)
print(f"函数外: {arr}") # [1,2,3,4,5,6,7] ❌ 没变！
解决方法：切片赋值
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
k = k % len(nums)
# 🔑 关键：用 nums[:] = ... 而不是 nums = ...
# nums[:] 表示"修改原列表的所有元素"，不是"让nums指向新列表"
nums[:] = nums[-k:] + nums[:-k]
nums[:] = ... vs nums = ... 对比：
lst = [1, 2, 3]
print(id(lst)) # 0x100
# ❌ nums = ... : 重新绑定变量
lst = [4, 5, 6]
print(id(lst)) # 0x200 (新对象！)
# ✅ nums[:] = ... : 修改原对象内容
lst = [1, 2, 3]
original_id = id(lst) # 0x300
lst[:] = [4, 5, 6]
print(id(lst)) # 0x300 (同一对象！)
print(lst) # [4, 5, 6] ✓
💡 记忆口诀： "等号左边加 [:]，原地修改不迷路！"
Python为什么这样设计？
这是 Python 的"名称绑定"机制决定的
def f(lst):
print(id(lst)) # 0x100
lst = [9,9,9] # 创建新对象，lst 绑定到新地址
print(id(lst)) # 0x200
arr = [1,2,3]
print(id(arr)) # 0x100
f(arr)
print(id(arr)) # 0x100 (没变！)
print(arr) # [1,2,3] (没变！)
真正修改原对象的方法：
# 方法1: 切片赋值
lst[:] = [9,9,9]
# 方法2: 逐个元素修改
for i in range(len(lst)):
lst[i] = 9
# 方法3: 列表方法
lst.clear()
lst.extend([9,9,9])
解法二
三次反转法（\(O(1)\)空间）
如果面试要求 O(1) 额外空间，切片赋值虽然通过，但实际创建了临时列表。更优雅的做法：
class Solution:
def rotate(self, nums: List[int], k: int) -> None:
n = len(nums)
k = k % n
# 辅助函数：反转区间 [left, right]
def reverse(left, right):
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# 🔑 三次反转：
# 1. 整体反转: [1,2,3,4,5,6,7] → [7,6,5,4,3,2,1]
reverse(0, n-1)
# 2. 反转前k个: [7,6,5,4,3,2,1] → [5,6,7,4,3,2,1]
reverse(0, k-1)
# 3. 反转后n-k个: [5,6,7,4,3,2,1] → [5,6,7,1,2,3,4] ✓
reverse(k, n-1)
除了自身以外数组的乘积
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除了 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 \(O(n)\) 时间复杂度内完成此题。
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# 计算前缀乘积和后缀乘积，相乘不就是答案吗
pre_result = [1] * len(nums)
suf_result = [1] * len(nums)
result = [0] * len(nums)
for i in range(1, len(nums)):
pre_result[i] = pre_result[i-1] * nums[i-1]
for i in range(len(nums) - 2, -1, -1):
suf_result[i] = suf_result[i+1] * nums[i+1]
for i in range(len(nums)):
result[i] = pre_result[i] * suf_result[i]
return result
由于不允许使用除法，且要在时间复杂度 \(O(n)\) 内完成，我联想到了此前的前缀和，通过空间换取时间，本题我转换了一下，前缀积和后缀积，相乘就是答案。
缺失的第一个正数
给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
请你实现时间复杂度为 \(O(n)\) 并且只使用常数级别额外空间的解决方案。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
signs = [0] * (len(nums) + 1)
for num in nums:
if num > 0 and num <= len(nums):
signs[num] += 1
for i in range(1, len(signs)):
if signs[i] == 0:
return i
return len(signs)
我很自然的想法就是用一个数组来记录数字出现的次数，然后遍历数组，找到第一个没有出现的数字。而且是只统计[1, n]这个范围内的数字。
但是显然这与题目要求的常数级别额外空间有冲突。思考如何优化？
常数级别空间要不就是确实可以使用几个变量做到，要不就利用好现在的数组空间，在这上面进行操作。
class Solution:
def firstMissingPositive(self, nums: List[int]) -> int:
n = len(nums)
# Step 1: 原地哈希 - 把数字 k 放到索引 k-1 处
for i in range(n):
# 条件：数字在 [1, n] 范围内，且不在正确位置
while 1 <= nums[i] <= n and nums[nums[i] - 1] != nums[i]:
# 交换到正确位置
correct_idx = nums[i] - 1
nums[correct_idx], nums[i] = nums[i], nums[correct_idx]
# Step 2: 查找第一个位置不匹配的
for i in range(n):
if nums[i] != i + 1: # 索引 i 处应该是数字 i+1
return i + 1
# Step 3: 如果 1~n 都存在，返回 n+1
return n + 1
注意不是使用\(nums[i] != i + 1\)而是\(nums[nums[i] - 1] != nums[i]\)进行判断对应位置是否已经有了正确的元素，因为可能有重复元素的原因，会陷入反复交换的死循环。
时间复杂度：\(O(n)\)，其中 n 是 nums 的长度。虽然我们写了个二重循环，但每次交换都会把一个学生换到正确的座位上，所以总交换次数至多为 n，所以内层循环的总循环次数是 \(O(n)\) 的，所以时间复杂度是 \(O(n)\)。
矩阵
矩阵置零
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
row_has_zero = [0 in row for row in matrix]
col_has_zero = [0 in col for col in zip(*matrix)]
for i, row in enumerate(row_has_zero):
for j, col in enumerate(col_has_zero):
if row or col:
matrix[i][j] = 0
最直观的思路，使用两个数组记录行和列的零元素，然后根据这两个数组进行置零。
注意：不能在发现matrix[i][j] == 0时，将matrix[i][j]置零，因为这样会导致后续的判断错误。例如继续遍历matrix[i][j+1]时，matrix[i][j+1]的元素被置零了，所以可能导致对应的列原本不应该被置为零的也被置零了。
列表推导式
# 语法：[表达式 for 变量 in 可迭代对象]
# 你的代码：
col_has_zero = [0 in col for col in zip(*matrix)]
# 等价于：
result = []
for col in zip(*matrix):
result.append(0 in col)
矩阵转置速查
matrix = [[1,2,3], [4,5,6]]
# 方法1：zip(*matrix) ⭐ 推荐
list(zip(*matrix)) # [(1,4), (2,5), (3,6)]
# 方法2：列表推导式
[[row[i] for row in matrix] for i in range(len(matrix[0]))]
# 方法3：NumPy
import numpy as np
np.array(matrix).T
# 原理：*解包行 → zip打包对应位置 → 列变行
优化解法
如何使用常量空间解决该问题？
class Solution:
def setZeroes(self, matrix: List[List[int]]) -> None:
"""
Do not return anything, modify matrix in-place instead.
"""
# 判断第一行和第一列是否有0
first_row_has_zero = 0 in matrix[0]
first_col_has_zero = any(row[0] == 0 for row in matrix) # 记录第一列是否包含 0
m = len(matrix)
n = len(matrix[0])
for i in range(1, m):
for j in range(1, n):
if matrix[i][j] == 0:
matrix[0][j] = matrix[i][0] = 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 first_row_has_zero:
for i in range(n):
matrix[0][i] = 0
if first_col_has_zero:
for i in range(m):
matrix[i][0] = 0
不使用额外数组，考虑将数据直接保存到 matrix 的第一行和第一列中，类似于表格的第一行和第一列，至于原本第一行和第一列是否含有0，我们用两个额外变量存储记录即可。
any()用法
1. 详解 any() 语法与生成器表达式
代码行：
first_col_has_zero = any(row[0] == 0 for row in matrix)
A. any() 函数的作用
any(iterable) 是 Python 的内建函数。
- 功能：判断可迭代对象（iterable）中是否存在至少一个为
True的元素。 - 返回值：
- 如果有任何一个元素为真，返回
True。 - 如果所有元素都为假，或者可迭代对象为空，返回
False。
- 如果有任何一个元素为真，返回
- 特性（重要）：它具有 短路（Short-circuit） 特性。一旦遇到第一个
True，它就会立即停止遍历并返回True，不会继续处理剩下的元素。
B. 括号内的部分：生成器表达式
row[0] == 0 for row in matrix 是一个 生成器表达式（Generator Expression）。
- 语法：
(表达式 for 变量 in 可迭代对象)。注意这里最外层的括号被any()的括号省略了。 - 与列表推导式的区别：
- 列表推导式：
[row[0] == 0 for row in matrix]会立即在内存中创建一个包含所有布尔值的新列表。 - 生成器表达式：
(row[0] == 0 for row in matrix)不会立即创建列表。它返回一个迭代器，每次只计算并产出下一个值。
- 列表推导式：
C. 结合后的执行流程
any()开始请求生成器的第一个值。- 生成器执行
row = matrix[0]，计算matrix[0][0] == 0。 - 如果结果是
True，any()立即返回True，生成器停止，后续的行根本不会被访问。 - 如果结果是
False，any()请求下一个值，生成器继续处理matrix[1]，以此类推。 - 如果遍历完所有行都没发现
0，any()返回False。
D. 为什么这样写很好？
- 空间 \(O(1)\)：因为是生成器，没有创建额外的列表存储中间结果。
- 时间最优：因为短路机制，如果第一列很早就出现了 0，后面的行就不需要检查了。
2. 如果使用 list(zip(*matrix)) 判断第一列的空间分析
你提到的替代方案可能是想通过转置矩阵，把“第一列”变成“第一行”，然后判断第一行是否有 0。代码可能长这样：
# 不推荐的写法
transposed = list(zip(*matrix))
first_col_has_zero = 0 in transposed[0]
A. zip(*matrix) 做了什么？
*matrix是解包操作，将矩阵的每一行作为独立参数传给zip。zip会将这些行的对应位置元素打包。- 效果：它实现了矩阵的 转置（Transpose）。
- 原矩阵：\(M\) 行 \(N\) 列。
zip结果：\(N\) 行 \(M\) 列（实际上是 \(N\) 个元组，每个元组长度为 \(M\)）。- 原矩阵的“第一列”，变成了转置后矩阵的“第一行”（即
transposed[0]）。
B. 空间复杂度分析 这是最关键的部分。
zip(*matrix)本身：在 Python 3 中，zip返回的是一个迭代器，此时空间开销很小。list(...)包裹：当你使用list()强制转换时，Python 会遍历整个迭代器并将所有结果存入内存。- 这意味着你创建了一个全新的、包含原矩阵所有数据的新结构。
- 原矩阵有 \(M \times N\) 个元素。
- 转置后的列表也有 \(M \times N\) 个元素。
- 结论：
- 额外空间复杂度：\(O(M \times N)\)。
- 原代码空间复杂度：\(O(1)\)。
C. 为什么这是“杀鸡用牛刀”且违规的？
"矩阵置零" 这道题的核心难点通常要求 \(O(1)\) 额外空间复杂度（即不能使用与矩阵大小成正比的额外内存）。
- 如果你使用
list(zip(*matrix))，你为了判断第一列（\(M\) 个元素）是否有 0，竟然在内存中复制了整个矩阵（\(M \times N\) 个元素）。 - 如果矩阵是 \(1000 \times 1000\)，你只是为了检查 1000 个数，却额外开辟了存储 1,000,000 个数的内存。
- 这不仅浪费了空间，还浪费了时间（因为
list()必须遍历完所有元素才能完成构建，无法像any()那样短路）。
螺旋矩阵
给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:
return []
result = []
top, bottom = 0, len(matrix) - 1
left, right = 0, len(matrix[0]) - 1
while top <= bottom and left <= right:
# 1. 从左到右遍历上边
for col in range(left, right + 1):
result.append(matrix[top][col])
top += 1 # 上边界下移
# 2. 从上到下遍历右边
for row in range(top, bottom + 1):
result.append(matrix[row][right])
right -= 1 # 右边界左移
# 3. 从右到左遍历下边（需检查是否还有有效行）
if top <= bottom:
for col in range(right, left - 1, -1):
result.append(matrix[bottom][col])
bottom -= 1 # 下边界上移
# 4. 从下到上遍历左边（需检查是否还有有效列）
if left <= right:
for row in range(bottom, top - 1, -1):
result.append(matrix[row][left])
left += 1 # 左边界右移
return result
直接模拟即可，使用 top, bottom, left, right 四个边界指针，每遍历完一条边就收缩边界，并在遍历"回程"边时检查是否还有有效区域。
- 边界检查：遍历下边和左边前，用
if top <= bottom和if left <= right确保不会重复遍历单行/单列 - 边界收缩：每完成一条边立即收缩对应边界，逻辑更清晰
- 无需特殊处理中心点：循环条件
top <= bottom and left <= right自动处理所有情况
旋转图像
给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。
你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
# 转置 + 转为列表
matrix[:] = [list(row) for row in zip(*matrix)]
# 每行反转（用切片，更简洁）
for i in range(len(matrix)):
matrix[i] = matrix[i][::-1]
🕳️ 核心坑点
# ❌ 错误：zip 产出的是 tuple，tuple 不可修改
matrix[:] = list(zip(*matrix)) # → [(1,4,7), (2,5,8), ...] 内层是元组
matrix[0][0] = 100 # TypeError: 'tuple' object does not support item assignment
# ✅ 正确：转成 list 再赋值
matrix[:] = [list(row) for row in zip(*matrix)] # → [[1,4,7], [2,5,8], ...]
📌 一句话：
zip(*matrix)转置后，记得把内层 tuple 转成 list，否则无法原地修改。
🎨 优雅翻转写法
水平翻转（每行反转）
# 方法1：切片反转（最简洁 ✅）
for i in range(n):
matrix[i] = matrix[i][::-1]
# 方法2：reverse() 方法（原地修改）
for i in range(n):
matrix[i].reverse()
# 方法3：双指针交换（传统写法）
for i in range(n):
for j in range(n//2):
matrix[i][j], matrix[i][n-1-j] = matrix[i][n-1-j], matrix[i][j]
完整旋转90°（转置 + 翻转）
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
# 转置 + list转换
matrix[:] = [list(row) for row in zip(*matrix)]
# 每行水平翻转
for i in range(len(matrix)):
matrix[i] = matrix[i][::-1] # ✨ 优雅！
纯原地算法（空间 O(1)）
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
# 1. 沿主对角线转置
for i in range(n):
for j in range(i+1, n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
# 2. 每行反转
for row in matrix:
row.reverse() # ✨ 直接对 row 操作，更简洁
🧠 记忆口诀
旋转90° = 转置 + 水平翻转
转置用 zip 记得转 list
翻转用 [::-1] 或 reverse()
搜索二维矩阵
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
- 每行的元素从左到右升序排列。
- 每列的元素从上到下升序排列。
下面是我自己的一种思路，其实也就是比直接暴力枚举好一些。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
m0, n0 = m-1, n-1 # 初始化搜索边界：最大行/列索引
# Step 1: 遍历第一列，缩小行的搜索范围
# 如果某行首元素 > target，说明target不可能在该行及之后的行
for i in range(m):
if matrix[i][0] > target:
m0 = i - 1 # 更新最大行号
break
elif matrix[i][0] == target: # 命中直接返回
return True
# Step 2: 遍历第一行，缩小列的搜索范围
# 如果某列首元素 > target，说明target不可能在该列及之后的列
for i in range(n):
if matrix[0][i] > target:
n0 = i - 1 # 更新最大列号
break
elif matrix[0][i] == target:
return True
# Step 3: 在缩小后的范围 [0..m0][0..n0] 内暴力搜索
# ⚠️ 从右下角往左上角遍历，但仍是 O(m*n)
for i in range(m0, -1, -1):
for j in range(n0, -1, -1):
if matrix[i][j] == target:
return True
return False # 未找到
优化
从右上角进行搜索。
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
i, j = 0, n - 1 # 从右上角开始
while i < m and j >= 0: # 还有剩余元素
if matrix[i][j] == target:
return True # 找到 target
if matrix[i][j] < target:
i += 1 # 这一行剩余元素全部小于 target，排除
else:
j -= 1 # 这一列剩余元素全部大于 target，排除
return False
上述代码由于要么对列进行缩小，要么对行进行扩大，因此时间复杂度是 \(O(m+n)\)。
为什么可以这么做？其实就跟我上面暴力法优化的思路是一样的。利用了自上而下，自左向右递增的矩阵特性。
链表
相交链表
给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
p, q = headA, headB
while p is not q:
p = p.next if p else headB
q = q.next if q else headA
return p
利用了一个技巧：\((a + c) + b = (b + c) + a\)，则都走\(a + b + c\)时，p和q同时到达链表相交的起始节点，要么就是都走\(a + b + 2c\)同时最终走到空节点。
具体算法如下：
- 初始化两个指针 p=headA, q=headB。
- 不断循环，直到 p=q。
- 每次循环，p 和 q 各向后走一步。具体来说，如果 p 不是空节点，那么更新 p 为 p.next，否则更新 p 为 headB；如果 q 不是空节点，那么更新 q 为 q.next，否则更新 q 为 headA。
- 循环结束时，如果两条链表相交，那么此时 p 和 q 都在相交的起始节点处，返回 p；如果两条链表不相交，那么 p 和 q 都走到空节点，所以也可以返回 p，即空节点。
is not 与 != 的本质区别
核心考点：对象身份（内存地址）vs 对象值。
is/is not：比较身份。判断是否是同一个对象（内存地址相同）。- 适用场景：判断
None、判断链表节点是否重合。 - 示例：
while p is not q:（判断是否指向同一个节点对象）。
- 适用场景：判断
==/!=：比较值。调用对象的__eq__方法。- 风险：如果链表节点值相同但对象不同，
!=可能误判为相等从而提前终止循环。
- 风险：如果链表节点值相同但对象不同，
- 最佳实践：
- 判断
None：✅if x is None:/ ❌if x == None: - 判断节点相遇：✅
if p is q:/ ❌if p == q:
- 判断
反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 虚拟头节点
dummy = ListNode()
p = head
while p:
node = ListNode(p.val, dummy.next)
dummy.next = node
p = p.next
return dummy.next
我这里虚拟头节点的思路，最后新建了一条链表。
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre # 把 cur 插在 pre 链表的前面（头插法）
pre = cur
cur = nxt
return pre
也可以直接在原链表上进行操作，改变指针即可。
回文链表
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def isPalindrome(self, head: Optional[ListNode]) -> bool:
def middleNode(head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
def reverseList(head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
cur = head
while cur:
nxt = cur.next
cur.next = pre # 把 cur 插在 pre 链表的前面（头插法）
pre = cur
cur = nxt
return pre
mid = middleNode(head)
head2 = reverseList(mid)
while head2:
if head.val != head2.val:
return False
head = head.next
head2 = head2.next
return True
比较简单的想法就是借由上一题的翻转链表，将链表翻转，然后比较翻转后的链表和原链表是否相同。只不过这样的方法时间复杂度是 \(O(n)\)，空间复杂度是 \(O(n)\)。
转换思路：利用快慢指针，找到链表的中点，然后对中点之后的链表进行翻转，最后比较两个链表是否相同，如此也不需要额外的空间。
环形链表
给你一个链表的头节点 head ，判断链表中是否有环。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。
如果链表中存在环 ，则返回 true 。 否则，返回 false 。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def hasCycle(self, head: Optional[ListNode]) -> bool:
slow = fast = head
while fast and fast.next:
slow = slow.next # 走 1 步
fast = fast.next.next # 走 2 步
if slow == fast: # 相遇
return True
return False
依旧快慢指针，如果有环的链表，快慢指针最终会相遇。
环形链表Ⅱ
给定一个链表的头节点 head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
不允许修改 链表。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
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 fast is slow:
slow = head
while slow is not fast:
slow = slow.next
fast = fast.next
return slow
return None
依旧快慢指针，只是这次需要确定入口位置，有点麻烦。
- 慢指针走 b 步，则快指针就走了 2b 步。\(2b - b = kc\)，其中 k 是环的周数，c 是环的长度，于是有\(b = kc\)。假设自头节点到入环口有 a 步，\(b - a = kc - a\)。
- 注 1：kc−a 是从入环口开始的步数。因为 (kc−a)+a=kc，所以从 kc−a 开始，再走 a 步，就可以走满 k 圈。
- 注 2：慢指针从相遇点开始，移动 a 步后恰好走到入环口，但在这个过程中，可能会多次经过入环口。
- 注 3：这个算法叫做 Floyd 判圈算法。
合并两个有序链表
将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
p = dummy
while list1 and list2:
if list1.val <= list2.val:
p.next = list1
list1 = list1.next
else:
p.next = list2
list2 = list2.next
p = p.next
# if list1:
# p.next = list1
# if list2:
# p.next = list2
p.next = list1 or list2
return dummy.next
创建一个虚拟节点 dummy，然后创建一个指针 p 指向 dummy。然后，比较 list1 和 list2 的值，将较小的节点连接到 p 的 next，并更新指针 p 和对应链表的指针。重复这个过程，直到某个链表为空。最后，将 p 的 next 指向剩余的链表。
1. or 运算符的真实返回值
A or B 确实返回操作数本身，而不是 True/False。
# 验证返回值类型
result = 3 or 5
print(result) # 输出：3
print(type(result)) # 输出：<class 'int'>，不是 bool！
result = None or "hello"
print(result) # 输出："hello"
print(type(result)) # 输出：<class 'str'>，不是 bool！
result = [] or [1, 2]
print(result) # 输出：[1, 2]
print(type(result)) # 输出：<class 'list'>，不是 bool！
2. 条件语句中的"隐式转换"
当 or 表达式用在 if / while 中时，Python 会自动对返回值做真值测试：
# 这两行代码的实际执行过程：
if list1 or list2: # ① 先计算 list1 or list2，返回某个对象
... # ② 再对这个对象做 bool() 隐式转换
# 等价于：
temp = list1 or list2 # 返回操作数本身
if bool(temp): # 隐式调用 bool() 做真值测试
...
真值测试规则：
| 对象 | bool() 结果 |
在条件中视为 |
|---|---|---|
None |
False |
假 |
0 |
False |
假 |
"" (空字符串) |
False |
假 |
[] (空列表) |
False |
假 |
| 非空对象 | True |
真 |
3. 对比演示
list1 = ListNode(1) # 非空节点
list2 = None # 空
# --- 场景 1：直接打印返回值 ---
result = list1 or list2
print(result) # 输出：ListNode 对象本身
# --- 场景 2：用在条件语句中 ---
if list1 or list2: # ① 返回 ListNode 对象
print("进入分支") # ② Python 隐式调用 bool(ListNode) → True
完整执行流程：
if list1 or list2:
↓
计算表达式 → 返回 list1 (ListNode 对象)
↓
隐式转换 → bool(ListNode 对象) → True
↓
进入 if 分支
4. 危险陷阱示例
这就是为什么我说"需谨慎"——如果操作数是其他假值：
# 链表场景（安全✅）
list1 = None
list2 = ListNode(0) # 节点值为 0，但对象本身非空
p.next = list1 or list2 # 返回 ListNode 对象 ✅
# 数字场景（危险❌）
a = 0
b = 10
result = a or b # 返回 10，而不是 0！
if a or b: # 进入分支（因为 10 是真值）
print("有值")
# 但你原本可能想保留 0 这个有效值！
5. 总结对比表
| 场景 | or 的行为 |
返回值类型 |
|---|---|---|
x = A or B |
返回操作数本身 | A 或 B 的原类型 |
if A or B: |
返回操作数 → 隐式 bool() 转换 |
条件判断用 |
x = bool(A or B) |
显式转换为布尔值 | bool |
一句话理解：
or永远返回操作数本身；条件语句中是 Python 隐式调用bool()做了二次转换。
两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
dummy = p = ListNode()
sign = 0
while l1 or l2:
val1 = l1.val if l1 else 0
val2 = l2.val if l2 else 0
sum0 = val1 + val2 + sign
val = sum0 % 10
sign = sum0 // 10
p.next = ListNode(val)
p = p.next
l1 = l1.next if l1 else l1
l2 = l2.next if l2 else l2
if sign:
p.next = ListNode(sign)
return dummy.next
简单模拟即可，就是简单的加法运算模拟。
三元表达式
value = A if condition else B
执行逻辑：
- 如果 condition 为 True → 返回 A
- 如果 condition 为 False → 返回 B
确实是一个很常用的语法，可以简化代码。
删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
dummy = ListNode()
dummy.next = head
slow = fast = dummy
for i in range(n):
fast = fast.next
while fast and fast.next:
slow = slow.next
fast = fast.next
slow.next = slow.next.next
return dummy.next
链表操作题，最简单的解法是使用两个指针，一个指针先走 n 步，然后两个指针同时走，当第一个指针到达末尾时，第二个指针指向的节点就是倒数第 n 个节点。
两两交换链表中的节点
给定一个链表，两两交换其中相邻的节点，并返回交换后的链表。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
if not head:
return head
dummy = ListNode()
dummy.next = head
pre = dummy
fast, slow = head.next, head
while fast and slow:
slow.next = fast.next
fast.next = slow
pre.next = fast
pre = slow
slow = slow.next
if slow:
fast = slow.next
return dummy.next
本题也就是一前一后两个快慢指针不停移动，交换两个节点。
随机链表的复制
给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
例如，如果原链表中有 X 和 Y 两个节点，其中 X.random --> Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random --> y 。
返回复制链表的头节点。
用一个由 n 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 [val, random_index] 表示：
- val：一个表示 Node.val 的整数。
- random_index：随机指针指向的节点索引（范围从 0 到 n-1）；如果不指向任何节点，则为 null 。 你的代码 只 接受原链表的头节点 head 作为传入参数。
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
cache = {} # 核心：原节点 -> 新节点
cur = head
# 第一次遍历：创建所有新节点，建立映射
while cur:
cache[cur] = Node(cur.val)
cur = cur.next
# 第二次遍历：连接 next 和 random 指针
cur = head
while cur:
# 通过映射找到对应的新节点，设置指针
cache[cur].next = cache.get(cur.next) # cur.next 可能为 None
cache[cur].random = cache.get(cur.random) # cur.random 可能为 None
cur = cur.next
return cache[head]
我想到的最直接的方法就是建立哈希表的映射关系，然后根据映射关系建立新链表。如此，对应的next以及random指针都指向了正确的节点。
交错链表
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# 复制每个节点，把新节点直接插到原节点的后面
cur = head
while cur:
cur.next = Node(cur.val, cur.next)
cur = cur.next.next
# 遍历交错链表中的原链表节点
cur = head
while cur:
if cur.random:
# 要复制的 random 是 cur.random 的下一个节点
cur.next.random = cur.random.next
cur = cur.next.next
# 删除交错链表中的原链表节点，剩下的节点即为新链表
cur = dummy = Node(0, head)
while cur.next:
# 删除原链表的节点，即当前节点的下一个节点
# 如果要恢复原链表，见另一份代码【Python3 写法二】
cur.next = cur.next.next
cur = cur.next
return dummy.next
一次复制每个节点，创建新节点并复制val和next指针。将新节点直接查到原节点的后面，形成一个交错链表，如此一来，原链表节点的下一个节点，就是其对应的新链表节点。
然后遍历这个交错链表，假如节点 1 的random指针指向节点 2 ，那么节点 1 的对应新链表节点 1' 的random指针指向节点 2 的对应新链表节点，也就是节点 2 的下一个节点 2'。
排序链表
给定链表的头结点 head ，请将其按升序排序并返回排序后的链表。
class Solution:
# 876. 链表的中间结点（快慢指针）
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
slow = fast = head
while fast and fast.next:
pre = slow # 记录 slow 的前一个节点
slow = slow.next
fast = fast.next.next
pre.next = None # 断开 slow 的前一个节点和 slow 的连接
return slow
# 21. 合并两个有序链表（双指针）
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() # 用哨兵节点简化代码逻辑
while list1 and list2:
if list1.val < list2.val:
cur.next = list1 # 把 list1 加到新链表中
list1 = list1.next
else: # 注：相等的情况加哪个节点都是可以的
cur.next = list2 # 把 list2 加到新链表中
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2 # 拼接剩余链表
return dummy.next
def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
# 如果链表为空或者只有一个节点，无需排序
if head is None or head.next is None:
return head
# 找到中间节点 head2，并断开 head2 与其前一个节点的连接
# 比如 head=[4,2,1,3]，那么 middleNode 调用结束后 head=[4,2] head2=[1,3]
head2 = self.middleNode(head)
# 分治
head = self.sortList(head)
head2 = self.sortList(head2)
# 合并
return self.mergeTwoLists(head, head2)
使用归并排序的思路，分治，然后合并。
- 找到链表的中间节点，并断开中间节点与前一个节点的连接。如此，我们就把原来的链表均分成了两段更加短的链表。
- 分治，递归调用函数对两段链表进行排序。
- 排序后，我们得到了两个有序链表，此刻可以合并这两个有序链表，从而得到排序后的链表。
LRU 缓存
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key, last=False)
return self.cache[key]
def put(self, key: int, value: int) -> None:
self.cache[key] = value
self.cache.move_to_end(key, last=False)
if len(self.cache) > self.capacity:
self.cache.popitem()
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
🔹 OrderedDict 是什么？
OrderedDict 是 Python collections 模块中的一个子类，它在普通 dict 的基础上额外维护了一个双向链表，用于记录键值对的插入顺序。
from collections import OrderedDict
# 普通 dict（Python 3.7+ 也保持插入顺序，但功能有限）
d = dict()
d['a'] = 1; d['b'] = 2; d['c'] = 3
# OrderedDict（功能更强大，支持顺序操作）
od = OrderedDict()
od['a'] = 1; od['b'] = 2; od['c'] = 3
| 特性 | 普通 dict | OrderedDict |
|---|---|---|
| 保持插入顺序 | ✅ (3.7+) | ✅ (所有版本) |
move_to_end() |
❌ | ✅ |
popitem(last=?) |
只能删最后 | 可删头/尾 ✅ |
| 顺序相等性比较 | 值相等即可 | 顺序+值都需相等 |
🔹 核心方法详解
✅ move_to_end(key, last=True)
将指定 key 移动到有序字典的末尾（last=True）或开头（last=False）。
od = OrderedDict([('a', 1), ('b', 2), ('c', 3)])
# 移到末尾（默认）
od.move_to_end('a')
# OrderedDict([('b', 2), ('c', 3), ('a', 1)])
# 移到开头（LRU 常用！）
od.move_to_end('b', last=False)
# OrderedDict([('b', 2), ('c', 3), ('a', 1)])
✅ popitem(last=True)
删除并返回一个 (key, value) 对：
last=True（默认）：删除最后插入的项（FIFO/队列尾）last=False：删除最早插入的项（LRU 淘汰关键！）
od = OrderedDict([('x', 10), ('y', 20), ('z', 30)])
# 删除末尾（最新）
od.popitem(last=True) # ('z', 30)
# 删除开头（最旧）← LRU 淘汰策略核心
od.popitem(last=False) # ('x', 10)
✅ 其他常用操作
# 初始化
OrderedDict([('a', 1), ('b', 2)])
OrderedDict(a=1, b=2)
# 遍历（按顺序）
for k, v in od.items(): ...
# 反向遍历
for k, v in reversed(od.items()): ...
# 判断顺序相等
OrderedDict(a=1, b=2) == OrderedDict(b=2, a=1) # False!
🔹 在 LRU Cache 中的工作原理
最近使用的 → 放在链表头（last=False）
最久未使用的 → 沉在链表尾 → 超容时淘汰
# 假设 capacity = 2
cache = OrderedDict()
# put(1, 1): [ (1,1) ]
# put(2, 2): [ (2,2), (1,1) ] ← 新元素放头部
# get(1): [ (1,1), (2,2) ] ← 访问1，移到头部
# put(3, 3): [ (3,3), (1,1) ] ← 淘汰尾部(2,2)
# get(2): 返回 -1（已被淘汰）
🔑 关键逻辑：
- 访问/插入 →
move_to_end(key, last=False)提到头部（标记为"最近使用"） - 超容淘汰 →
popitem(last=True)删除尾部（"最久未使用"）
💡 为什么
last参数在get和put中都用False，但popitem用默认True？
因为：我们把头当作"最新"，尾当作"最旧"，淘汰时自然删尾部。
🔹 完整优化版 LRU Cache 实现
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
# 访问后移到头部（标记为最近使用）
self.cache.move_to_end(key, last=False)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
# 更新值时也需移到头部
self.cache.move_to_end(key, last=False)
self.cache[key] = value
self.cache.move_to_end(key, last=False) # 新元素放头部
# 超容：淘汰尾部（最久未使用）
if len(self.cache) > self.capacity:
self.cache.popitem(last=True) # ✅ 注意这里是 last=True!
⚠️ 你原始代码中的小问题：
self.cache.popitem() # 默认 last=True，是对的 ✅
last=True，避免他人误解。
🔹 进阶：不用 OrderedDict 的手动实现（面试加分项）
如果面试官问"不用 OrderedDict 怎么实现？"，可以用哈希表 + 双向链表：
class DLinkedNode:
def __init__(self, key=0, value=0):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cache = {} # key -> Node
self.capacity = capacity
# 伪头尾节点，简化边界处理
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def _add_to_head(self, node):
# 在 head 后插入 node（头插法）
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def _move_to_head(self, node):
self._remove_node(node)
self._add_to_head(node)
def _pop_tail(self):
# 删除 tail 前的节点（最久未使用）
node = self.tail.prev
self._remove_node(node)
return node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._move_to_head(node) # 标记为最近使用
return node.value
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 = DLinkedNode(key, value)
self.cache[key] = node
self._add_to_head(node)
if len(self.cache) > self.capacity:
removed = self._pop_tail()
del self.cache[removed.key]
🎯 总结：
OrderedDict是 Python 内置的"哈希表+双向链表"封装，用 5 行代码搞定手动实现 50 行的逻辑，实际开发首选；但理解底层原理对面试至关重要！
class Node:
# 提高访问属性的速度，并节省内存
__slots__ = 'prev', 'next', 'key', 'value'
def __init__(self, key=0, value=0):
self.key = key
self.value = value
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dummy = Node() # 哨兵节点
self.dummy.prev = self.dummy
self.dummy.next = self.dummy
self.key_to_node = {}
# 获取 key 对应的节点，同时把该节点移到链表头部
def get_node(self, key: int) -> Optional[Node]:
if key not in self.key_to_node: # 没有这本书
return None
node = self.key_to_node[key] # 有这本书
self.remove(node) # 把这本书抽出来
self.push_front(node) # 放到最上面
return node
def get(self, key: int) -> int:
node = self.get_node(key) # get_node 会把对应节点移到链表头部
return node.value if node else -1
def put(self, key: int, value: int) -> None:
node = self.get_node(key) # get_node 会把对应节点移到链表头部
if node: # 有这本书
node.value = value # 更新 value
return
self.key_to_node[key] = node = Node(key, value) # 新书
self.push_front(node) # 放到最上面
if len(self.key_to_node) > self.capacity: # 书太多了
back_node = self.dummy.prev
del self.key_to_node[back_node.key]
self.remove(back_node) # 去掉最后一本书
# 删除一个节点（抽出一本书）
def remove(self, x: Node) -> None:
x.prev.next = x.next
x.next.prev = x.prev
# 在链表头添加一个节点（把一本书放到最上面）
def push_front(self, x: Node) -> None:
x.prev = self.dummy
x.next = self.dummy.next
x.prev.next = x
x.next.prev = x
K个一组翻转链表
class Solution:
# 辅助函数：翻转从 head 开始的 k 个节点，返回新的头节点
def reverseKNodes(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
pre = None
cur = head
for _ in range(k):
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
return pre # 返回翻转后的新头
def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
group_prev = dummy # 记录每一组的前一个节点
while True:
# 1. 检查剩余节点是否足够 k 个
group_end = group_prev
for _ in range(k):
group_end = group_end.next
if not group_end: # 不足 k 个，直接结束
return dummy.next
# 2. 记录关键节点（用于断开和重连）
group_head = group_prev.next # 当前组的头（翻转后将变尾）
group_next = group_end.next # 下一组的头
# 3. 断开当前组，准备翻转
group_end.next = None
# 4. 翻转当前组
new_head = self.reverseKNodes(group_head, k)
# 5. 重连：前一组 -> 新头，新尾 -> 下一组
group_prev.next = new_head
group_head.next = group_next # group_head 现在是尾节点
# 6. 移动指针，准备处理下一组
group_prev = group_head
return dummy.next
合并K个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
分治
class Solution:
# 21. 合并两个有序链表
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
cur = dummy = ListNode() # 用哨兵节点简化代码逻辑
while list1 and list2:
if list1.val < list2.val:
cur.next = list1 # 把 list1 加到新链表中
list1 = list1.next
else: # 注：相等的情况加哪个节点都是可以的
cur.next = list2 # 把 list2 加到新链表中
list2 = list2.next
cur = cur.next
cur.next = list1 if list1 else list2 # 拼接剩余链表
return dummy.next
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
m = len(lists)
if m == 0:
return None
if m == 1:
return lists[0] # 无需合并，直接返回
left = self.mergeKLists(lists[:m // 2]) # 合并左半部分
right = self.mergeKLists(lists[m // 2:]) # 合并右半部分
return self.mergeTwoLists(left, right) # 最后把左半和右半合并
利用了分治的思路，将问题分解为子问题，最后合并结果。我们将lists数组分为左右两部分，分别处理，最后合并结果。如何分别合并一半的链表呢？我们可以继续一分为二，如此分下去直到只有一个链表，此时就无需合并了，直接返回。
最小堆
其实也就是每次同时比较 k 个链表，但是我们可以利用最小堆来优化。由于题目已经明确的要求，链表是升序排列的，那么最小的节点就是链表的头节点。每次找出这些头节点的最小值，并添加到新链表中，同时将下一个节点入堆。这样，每次取出的节点就是最小的节点，然后添加到新链表中，同时将下一个节点入堆。这样，我们最终得到一个有序的链表。
ListNode.__lt__ = lambda a, b: a.val < b.val # 让堆可以比较节点大小
class Solution:
def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:
cur = dummy = ListNode() # 哨兵节点，作为合并后链表头节点的前一个节点
h = [head for head in lists if head] # 把所有非空链表的头节点入堆
heapify(h) # 堆化
while h: # 循环直到堆为空
node = heappop(h) # 剩余节点中的最小节点
if node.next: # 下一个节点不为空
heappush(h, node.next) # 下一个节点有可能是最小节点，入堆
cur.next = node # 把 node 添加到新链表的末尾
cur = cur.next # 准备合并下一个节点
return dummy.next # 哨兵节点的下一个节点就是新链表的头节点
🔹 核心难点：ListNode.__lt__ 是什么？
这行代码是 Python 特有的“魔法”写法，目的是让优先队列（堆）知道如何比较两个链表节点的大小。
ListNode.__lt__ = lambda a, b: a.val < b.val
__lt__含义：它是 Python 的魔术方法（Magic Method），代表 Less Than（小于号<）。- 底层机制：当你写
a < b时，Python 底层实际调用的是a.__lt__(b)。 - 这行代码作用：动态地给
ListNode类挂载了一个比较规则：“比较节点时，请比较它们的val值”。
🔹 为什么要写这行？
Python 的 heapq 模块是一个 最小堆。为了维持堆的性质，它必须能够比较元素的大小（判断谁更小，谁应该浮到堆顶）。
- 基本类型（如
int,float）：Python 天生知道1 < 2。 - 自定义对象（如
ListNode）：Python 默认不知道 怎么比较。如果你直接写node1 < node2，会报错：TypeError: '<' not supported between instances of 'ListNode' and 'ListNode' - 解决方案：必须告诉 Python 如何比较
ListNode。这行代码就是最简短的解决方案。
🔹 这种写法叫什么？
这叫 Monkey Patching（猴子补丁）。
- 含义：在运行时动态修改类或模块的行为。
- 优点：代码极短，无需额外定义包装类，刷题神器。
- 缺点：污染全局环境。一旦修改，当前程序中所有的
ListNode比较都会按这个规则来。在工程开发中需谨慎，但在算法竞赛/刷题中非常实用。
🔹 如果不写这行，该怎么写？
在正式工作中，我们通常不修改原类，而是创建包装类或使用元组。
✅ 方案 A：使用元组（最常用）
将 (值，节点) 放入堆。Python 比较元组时，会先比第一个元素（值）。
# 不需要修改 ListNode
h = []
for head in lists:
if head:
# (值，节点) 元组入堆
heapq.heappush(h, (head.val, head))
while h:
val, node = heapq.heappop(h) # 解包
# ... 处理 node ...
if node.next:
heapq.heappush(h, (node.next.val, node.next))
💡 注意：如果
val相同，元组会比较第二个元素（节点对象），可能再次报错。但在本题中val相同不影响逻辑，或者可以加一个唯一索引(val, i, node)。
✅ 方案 B：包装类（最规范）
class Wrapper:
def __init__(self, node):
self.node = node
def __lt__(self, other):
return self.node.val < other.node.val
h = [Wrapper(head) for head in lists if head]
heapq.heapify(h)
# 使用时取 wrapper.node
🔹 代码逻辑全流程解析
抛开 __lt__ 的魔法，这段代码的算法逻辑非常清晰：
1️⃣ 哨兵节点（Dummy Node）
cur = dummy = ListNode()
- 作用：
dummy是一个假头节点，cur是移动指针。 - 好处：避免判断“结果链表是否为空”，最后直接返回
dummy.next即可。
2️⃣ 初始化堆
h = [head for head in lists if head]
heapify(h)
- 筛选：只把非空链表的头节点放入列表。
- 堆化：
heapify将列表在 \(O(K)\) 时间内变成最小堆。此时堆顶是所有头节点中val最小的。
3️⃣ 循环“摘取 - 补充”
while h:
node = heappop(h) # 1. 摘取：拿走当前最小节点
if node.next: # 2. 补充：如果该节点后面还有节点
heappush(h, node.next) # 把下一个节点放入堆中
cur.next = node # 3. 连接：接到结果链表后面
cur = cur.next # 4. 移动：指针后移
- 核心思想：堆里永远维护着 K 个链表的当前头节点。
- 每次从堆里拿出一个最小的，把它所在链表的下一个节点补进堆里。
- 就像 K 个赛跑队伍，每次只让每个队伍跑在最前面的人比赛，谁赢了谁加入总队伍，然后该队伍的下一个人补上。
🔹 复杂度分析
| 指标 | 复杂度 | 说明 |
|---|---|---|
| 时间 | \(O(N \log K)\) | \(N\) 是总节点数。每个节点进堆出堆一次，堆操作耗时 \(\log K\)。 |
| 空间 | \(O(K)\) | 堆中最多同时存储 \(K\) 个节点（每个链表一个代表）。 |
🔹 总结：如何理解这段代码？
ListNode.__lt__：是“规则定义”。告诉堆：“别比对象地址，比val值！”（刷题捷径，工程慎用）。heapify+heappop：是“调度中心”。始终从 K 个候选者中挑出最小的。if node.next：是“动态补位”。保证堆里始终有来自各链表的最新候选节点。dummy+cur：是“组装线”。负责把挑出来的节点串成新链表。
💡 一句话记忆：
给节点定好比较规则（lt），建个最小堆（heapq），每次挑最小的出来，把它后面的补进去，直到堆空。