LeetCode Hot100 复习索引

这份索引只保留答案，按专题重组，适合二刷和回顾时快速定位。个别题名按 LeetCode 常用名称做了轻微修正，但仍与原题号一一对应。

1. 两数之和
2. 字母异位词分组
3. 最长连续序列
4. 移动零
5. 盛最多水的容器
6. 三数之和
7. 接雨水
8. 无重复字符的最长子串
9. 找到字符串中所有字母异位词
12. 最小覆盖子串
14. 合并区间
15. 轮转数组
16. 除了自身以外数组的乘积
17. 缺失的第一个正数

哈希 / 数组 / 双指针 / 滑动窗口

1. 两数之和

核心思路：哈希表记录“已经见过的数字 -> 下标”，边遍历边找补数。
解题步骤：遍历 nums；先查 target - x 是否已出现；如果出现就返回对应下标和当前下标；否则把当前值和下标存入哈希表。
为什么这样做：原本双重枚举的第二层查找，被 O(1) 的哈希查找替代了。
复杂度：时间 O(n)，空间 O(n)。
易错点：要先查后存，避免把同一个元素用两次。

2. 字母异位词分组

核心思路：把每个字符串转换成统一的“签名”，签名相同的放到同一组。
解题步骤：遍历 strs；对每个字符串排序后得到键；把原串追加到 dict[key] 中；最后返回哈希表的所有值。
为什么这样做：异位词排序后字符顺序一致，因此可以直接拿排序结果当分组依据。
复杂度：设单词平均长度为 k，时间 O(n * k log k)，空间 O(nk)。
易错点：Python 的 sorted(s) 返回字符列表，作为键时要记得 ''.join(...)。

3. 最长连续序列

核心思路：把数组放进集合，用“只从连续段起点开始扩展”的方式统计长度。
解题步骤：先转成 set(nums)；遍历集合中的每个 x；如果 x - 1 存在，说明它不是起点，直接跳过；否则不断检查 x + 1, x + 2...，更新最长长度。
为什么这样做：每个连续段只会被完整扫描一次，避免排序带来的 O(n log n)。
复杂度：时间 O(n)，空间 O(n)。
易错点：不要先排序；必须只从起点扩展，否则会重复计数。

4. 移动零

核心思路：双指针维护“下一个非零元素应该放的位置”。
解题步骤：left 指向待放非零数的位置，right 从左到右扫描；遇到非零数就和 left 交换，并把 left 右移；扫描结束后数组前面全是非零，后面自然是零。
为什么这样做：每个元素最多被访问或交换一次，能在原地完成稳定移动。
复杂度：时间 O(n)，空间 O(1)。
易错点：left == right 时交换也没问题；不要额外开数组，否则空间复杂度不合题意。

5. 盛最多水的容器

核心思路：左右双指针夹逼，每次移动较短的那一边。
解题步骤：l=0, r=n-1；每次计算面积 (r-l) * min(height[l], height[r])；更新答案；移动较短边对应的指针。
为什么这样做：面积受短板限制，移动较高的一边不可能让当前短板变高，只会让宽度变小。
复杂度：时间 O(n)，空间 O(1)。
易错点：相等时移动任意一边都可以；循环条件是 l < r。

6. 三数之和

核心思路：排序后固定一个数，把剩下问题变成双指针版“两数之和”。
解题步骤：先排序；枚举 i；令 l=i+1, r=n-1；根据三数之和与 0 的关系移动指针；等于 0 时记录答案，并跳过重复值。
为什么这样做：排序后左右移动有单调性，双指针能在线性时间内完成一轮查找。
复杂度：时间 O(n^2)，空间 O(1) 或排序栈空间。
易错点：i 重复要跳过；找到一个答案后 l 和 r 都要继续跳过重复元素；可以用最小值/最大值剪枝。

7. 接雨水

核心思路：双指针同时维护左右最大值，较小的一侧可以先结算。
解题步骤：l=0, r=n-1；维护 left_max 和 right_max；若 left_max < right_max，说明当前位置 l 的接水量已确定，为 left_max - height[l]；否则结算右侧。
为什么这样做：某一侧的有效高度由“两边最大值的较小者”决定，当较小侧已经确定时，该侧结果就不会再变。
复杂度：时间 O(n)，空间 O(1)。
易错点：结算前先更新当前侧最大值；不要逐格去重新找左右最大值，那会退化成 O(n^2)。

8. 无重复字符的最长子串

核心思路：滑动窗口维护一个“没有重复字符”的区间。
解题步骤：右指针扩张窗口，把字符加入计数表；只要某个字符计数大于 1，就不断移动左指针并减少计数；每次更新窗口最大长度。
为什么这样做：窗口始终保持合法，因此每个字符至多进窗口一次、出窗口一次。
复杂度：时间 O(n)，空间 O(字符集大小)。
易错点：重复时不是直接清空窗口，而是一步步收缩到重新合法为止。

9. 找到字符串中所有字母异位词

核心思路：固定长度滑动窗口，比较窗口字符计数和目标串计数。
解题步骤：先统计 p 的字符频次；右指针向右扩，加入新字符；当窗口长度超过 len(p) 时移出左端字符；每次窗口长度等于 len(p) 且频次表相等，就记录左端下标。
为什么这样做：异位词只关心字符出现次数，不关心顺序。
复杂度：时间 O(n)，空间 O(字符集大小)。
易错点：窗口必须是定长；若用 Counter 直接比较，要注意移出后计数为 0 的键值处理。

12. 最小覆盖子串

核心思路：滑动窗口先扩到“覆盖所有需要字符”，再尽量缩小。
解题步骤：先统计 t 的需求频次；右指针不断加入字符；当窗口已经满足所有需求时，尝试移动左指针缩小窗口，并更新最短答案；直到窗口再次不满足需求，再继续扩张。
为什么这样做：这是典型的“先找到一个可行解，再在保持可行的前提下压缩”的最短子串问题。
复杂度：时间 O(n)，空间 O(字符集大小)。
易错点：不要用 cnt_s >= cnt_t 这种整体比较去硬判断，最好维护 need / missing 或满足字符种类数；没有答案时返回空串。

14. 合并区间

核心思路：按左端点排序后，能否合并只看当前区间和结果末尾区间是否重叠。
解题步骤：先按起点升序排序；遍历每个区间；如果结果为空或当前起点大于结果末尾终点，就直接加入；否则更新末尾区间的终点为两者较大值。
为什么这样做：排序后，可能与当前区间重叠的只会是结果数组最后一个区间。
复杂度：时间 O(n log n)，空间 O(n)。
易错点：重叠条件是 start <= last_end；别忘了更新的是终点最大值。

15. 轮转数组

核心思路：最常用的是“三次反转”，把右移变成局部反转组合。
解题步骤：先令 k %= n；整体反转；反转前 k 个；反转后 n-k 个。
为什么这样做：整体反转后，原本应该去前面的那段已经到了前面，但内部顺序反了，再各自反转一次即可恢复。
复杂度：时间 O(n)，空间 O(1)。
易错点：k 可能大于数组长度；切片法虽然简单，但严格来说不是原地 O(1) 空间。

16. 除了自身以外数组的乘积

核心思路：答案等于“左边所有数的乘积 × 右边所有数的乘积”。
解题步骤：先用一趟从左到右计算前缀积并写入答案数组；再用变量维护后缀积，从右到左把后缀积乘进答案。
为什么这样做：这样不用除法，也能在 O(n) 内把每个位置左右两部分信息合并出来。
复杂度：时间 O(n)，额外空间 O(1)，不计输出数组。
易错点：前缀和后缀顺序不要写反；多个零的情况这种写法也能自然处理。

17. 缺失的第一个正数

核心思路：原地哈希，把值 x 放到索引 x-1 的位置上。
解题步骤：遍历数组，对每个位置不断交换，直到当前值不在 1..n 范围内，或已经放到正确位置，或目标位置已有相同值；第二次遍历时，第一个 nums[i] != i+1 的位置答案就是 i+1。
为什么这样做：长度为 n 的数组，答案只可能落在 1..n+1，因此可以把数组本身当作哈希桶。
复杂度：时间 O(n)，空间 O(1)。
易错点：交换条件要写成 nums[nums[i]-1] != nums[i]，否则重复值会陷入死循环。

子数组 / 前缀和 / 单调结构 / 堆

10. 和为 k 的子数组

核心思路：前缀和 + 哈希计数，把“子数组和为 k”转成“两个前缀和之差为 k”。
解题步骤：初始化 cnt[0] = 1；遍历数组时累计当前前缀和 s；把 cnt[s-k] 加入答案；再令 cnt[s] += 1。
为什么这样做：若 pre[i] - pre[j] = k，则 j+1..i 就是一个合法子数组。
复杂度：时间 O(n)，空间 O(n)。
易错点：哈希表里存的是“出现次数”，不是单个索引；cnt[0] = 1 不能漏。

11. 滑动窗口最大值

核心思路：单调队列维护当前窗口内“可能成为最大值”的元素下标。
解题步骤：右指针加入新元素前，先把队尾所有比它小的下标弹出；再把当前下标入队；若队首已滑出窗口则弹出；当窗口形成后，队首就是最大值。
为什么这样做：队列始终保持值单调递减，队首永远是窗口最大值，而且每个元素只进出一次。
复杂度：时间 O(n)，空间 O(k)。
易错点：队列里存下标，不存值；判断过期元素时要和窗口左边界比较。

13. 最大子数组和

核心思路：本质是“以当前位置结尾的最大和”递推，也就是 Kadane 算法。
解题步骤：遍历数组，维护 cur = max(nums[i], cur + nums[i])；同时维护全局最大值 ans。
为什么这样做：以 i 结尾的最优解，只可能是“单独从 i 开始”或“接在前一个最优后面”两种情况。
复杂度：时间 O(n)，空间 O(1)。
易错点：不要只记总和，必须记录“以当前位置结尾”的状态；全负数时答案是最大那个负数。

69. 有效的括号

核心思路：栈记录未匹配的左括号。
解题步骤：遍历字符串；遇到左括号就入栈；遇到右括号时检查栈顶是否是对应的左括号，不匹配则直接返回 False；遍历结束后栈空才合法。
为什么这样做：括号匹配天然符合“后开先闭”的栈结构。
复杂度：时间 O(n)，空间 O(n)。
易错点：右括号出现时若栈空，应立即返回 False。

70. 最小栈

核心思路：栈内每个元素同时记录“当前值”和“压入它以后栈中的最小值”。
解题步骤：压栈时把 (x, min(x, 当前最小值)) 一起存；弹栈正常弹；取最小值时直接看栈顶的第二项。
为什么这样做：每次都把历史最小值带在身上，查询时就不需要回溯。
复杂度：所有操作时间 O(1)，空间 O(n)。
易错点：初始化时最好放一个哨兵最小值，或者压入第一个元素时单独处理。

71. 字符串解码

核心思路：遇到嵌套结构时，要么用递归按层解析，要么用栈保存“进入新层前的状态”。
解题步骤：扫描字符串；遇到数字累计倍数；遇到 [ 就把当前字符串和倍数入栈并重置；遇到 ] 就弹栈，把当前层结果重复若干次后拼回上一层；普通字符直接追加。
为什么这样做：k[encoded] 的结构天然是分层嵌套的，进入括号和退出括号就是压栈/出栈时机。
复杂度：时间 O(n)，空间 O(n)。
易错点：倍数可能是多位数；[ 后要清空当前倍数，避免串层。

72. 每日温度

核心思路：单调栈维护“还没找到更高温度”的下标。
解题步骤：从左到右遍历；当前温度若高于栈顶下标对应温度，就不断弹栈并结算答案为下标差；然后把当前下标入栈。
为什么这样做：对每一天来说，第一次遇到比它高的温度时就可以结算，之后不再关心。
复杂度：时间 O(n)，空间 O(n)。
易错点：栈里存的是下标，这样才能计算间隔天数。

73. 柱状图中最大的矩形

核心思路：单调递增栈维护“以某根柱子为高时，它能向左右扩到哪里”。
解题步骤：遍历高度数组，并在末尾补一个更小的哨兵；当当前高度小于等于栈顶高度时，持续弹栈并计算以弹出柱子为高的最大矩形面积；最后把当前下标压栈。
为什么这样做：柱子一旦被弹出，就意味着它右边第一个更矮柱子已经找到了，而栈内前一个元素就是左边第一个更矮柱子。
复杂度：时间 O(n)，空间 O(n)。
易错点：通常要在头尾加哨兵，方便统一处理边界。
代码：原笔记中的单调栈模板如下。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        heights.append(-1)
        st = [-1]
        ans = 0
        for right, h in enumerate(heights):
            while len(st) > 1 and heights[st[-1]] >= h:
                i = st.pop()
                left = st[-1]
                ans = max(ans, heights[i] * (right - left - 1))
            st.append(right)
        return ans

74. 数组中的第 k 个最大元素

核心思路：用快速选择，把问题转成“找升序下标为 n-k 的元素”。
解题步骤：随机选择基准值做一次分区；若基准最终位置正好是目标下标就返回；否则只递归或迭代处理目标所在半边。
为什么这样做：快速选择只会继续处理一边，平均复杂度优于完整排序。
复杂度：平均时间 O(n)，最坏 O(n^2)；空间取决于递归深度。
易错点：题目找的是“第 k 大”，对应升序下标 n-k；分区写法要先统一好“大于还是小于放左边”。

75. 前 k 个高频元素

核心思路：先统计频次，再按“频次”做桶排序或用堆。
解题步骤：用哈希表统计每个数字出现次数；建立以频次为下标的桶；把数字放入对应桶中；从高频到低频取出前 k 个。
为什么这样做：频次最大不超过 n，所以桶排序可以把“按频次排序”降成线性。
复杂度：时间 O(n)，空间 O(n)。
易错点：题目不要求结果有序；若用堆写法，要注意维护的是最小堆还是最大堆。

76. 数据流的中位数

核心思路：两个堆分半边，左边最大堆存较小一半，右边最小堆存较大一半。
解题步骤：插入新数时先入某一边，再做平衡，让两个堆元素个数差不超过 1，且左边所有元素都不大于右边；求中位数时看两堆大小关系。
为什么这样做：中位数本质上只和“中间两边的边界元素”有关，不需要整体有序。
复杂度：插入 O(log n)，查询 O(1)。
易错点：Python 没有最大堆，通常用相反数模拟；平衡条件要统一。

90. 最长有效括号

核心思路：栈里保存“最后一个还不能参与匹配的位置”，这样一旦形成合法段就能直接算长度。
解题步骤：初始化栈为 [-1]；遇到 ( 就压下标；遇到 ) 时先尝试弹栈；若弹后栈空，说明当前 ) 无法匹配，把它的下标作为新基线压回去；否则用 i - 栈顶 更新答案。
为什么这样做：栈顶始终表示“当前合法区间左边最近的断点”，所以一减就得到长度。
复杂度：时间 O(n)，空间 O(n)。
易错点：-1 这个初始哨兵很关键；遇到无法匹配的 ) 时要重置基线。
代码：这段代码就是最常见的栈写法。

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        stk = [-1]
        ans = 0
        for i, ch in enumerate(s):
            if ch == '(':
                stk.append(i)
            elif len(stk) > 1:
                stk.pop()
                ans = max(ans, i - stk[-1])
            else:
                stk[0] = i
        return ans

矩阵

18. 矩阵置零

核心思路：第一行和第一列可以充当标记数组，把空间从 O(m+n) 压到 O(1)。
解题步骤：先单独记录第一行、第一列是否本来就有零；再遍历其余位置，若 matrix[i][j] == 0，就把 matrix[i][0] 和 matrix[0][j] 置零；随后根据标记清零内部区域；最后再单独处理第一行和第一列。
为什么这样做：某行某列是否需要清零，只需要一个布尔标记，而矩阵本身就能存这些标记。
复杂度：时间 O(mn)，空间 O(1)。
易错点：matrix[0][0] 同时属于第一行和第一列，所以这两者必须额外用变量区分。

19. 螺旋矩阵

核心思路：按“右、下、左、上”四个方向模拟行走，越界或撞到已访问位置就转向。
解题步骤：定义四个方向数组；从左上角开始走 m*n 步；每次记录当前值并标记已访问；预判下一步是否越界或重复，若是则切换方向。
为什么这样做：螺旋顺序本质上是一个确定的模拟过程，不需要复杂数学推导。
复杂度：时间 O(mn)，空间 O(1) 或 O(mn)，取决于是否直接修改原矩阵。
易错点：如果直接把访问过的位置改成特殊值，要确保该值不会和原数据混淆。

20. 旋转图像

核心思路：顺时针旋转 90 度可以拆成“先转置，再左右翻转每一行”。
解题步骤：先交换 matrix[i][j] 和 matrix[j][i] 完成主对角线转置；再把每一行原地反转。
为什么这样做：坐标变换 (i, j) -> (j, n-1-i) 恰好等价于这两个操作的组合。
复杂度：时间 O(n^2)，空间 O(1)。
易错点：转置时只遍历上三角区域，避免交换两次。

21. 搜索二维矩阵 II

核心思路：从右上角或左下角出发，每次都能排除一整行或一整列。
解题步骤：从右上角开始；若当前值等于目标就返回 True；若当前值大于目标，向左移；若小于目标，向下移；越界仍未找到则返回 False。
为什么这样做：右上角左边更小、下边更大，比较一次就能确定下一步方向。
复杂度：时间 O(m+n)，空间 O(1)。
易错点：从左上角出发不具备这种单调排除性质。

64. 搜索二维矩阵

核心思路：因为每行首元素都大于上一行尾元素，所以整个矩阵可以视作一个升序一维数组。
解题步骤：把总长度视作 m*n；在区间 [0, m*n-1] 上二分；通过 mid // n 和 mid % n 映射回二维坐标。
为什么这样做：题目给的全局有序条件比“矩阵 II”更强，可以直接用标准二分。
复杂度：时间 O(log(mn))，空间 O(1)。
易错点：二维下标映射别写反；标准二分要统一闭区间或开区间模板。

链表

22. 相交链表

核心思路：双指针各走两条链表，走过的总长度相同后会在交点相遇。
解题步骤：指针 a 从 headA 出发，走到头后切到 headB；b 从 headB 出发，走到头后切到 headA；当 a == b 时返回该节点。
为什么这样做：两人都会走完 A+B 的长度，长度差会在“换轨”后被抵消。
复杂度：时间 O(m+n)，空间 O(1)。
易错点：比较的是节点地址，不是节点值。

23. 反转链表

核心思路：迭代写法就是不断改变 next 指向；递归写法本质也一样，只是把“回头连边”放到了回溯阶段。
解题步骤：迭代时维护 prev、cur、nxt；先保存 nxt，再让 cur.next = prev，最后整体前进。
为什么这样做：链表反转的核心只有一件事，就是把每条边的方向改过来。
复杂度：时间 O(n)，空间 O(1)；递归版额外有调用栈。
易错点：先保存 next 再改指针，否则后续链表会丢。

24. 回文链表

核心思路：快慢指针找中点，反转后半段，再和前半段逐个比较。
解题步骤：用快慢指针找到中点；把后半链表反转；用两个指针从头和中点后开始比较值。
为什么这样做：回文的前半段和后半段逆序后应该完全相同。
复杂度：时间 O(n)，空间 O(1)。
易错点：奇数长度时中间节点不用参与比较；如需恢复原链表，要再反转一次后半段。

25. 环形链表

核心思路：Floyd 快慢指针判圈。
解题步骤：慢指针一次走一步，快指针一次走两步；若存在环，两者最终会相遇；若快指针或其下一节点为空，则无环。
为什么这样做：在环里快指针每轮都会多走一步，迟早会追上慢指针。
复杂度：时间 O(n)，空间 O(1)。
易错点：循环条件要同时判断 fast 和 fast.next。

26. 环形链表 II

核心思路：第一次相遇后，再让一个指针从头出发，两个指针同步走，会在入环点相遇。
解题步骤：先用快慢指针找到第一次相遇点；新开一个指针从头节点出发；它和慢指针每次都走一步；再次相遇的位置就是入环点。
为什么这样做：设头到入环点距离为 a，环内相遇点距离为 b，可推得从头和从相遇点同步前进都会走到入环口。
复杂度：时间 O(n)，空间 O(1)。
易错点：只有在确认存在环之后，第二阶段推导才成立。

27. 合并两个有序链表

核心思路：尾插法逐步把较小节点接到结果链表后面。
解题步骤：创建哨兵节点 dummy；比较 list1 和 list2 当前节点值，小的接到 cur.next 后并移动对应指针；某一边为空后，直接接上另一边剩余部分。
为什么这样做：两条链表本来就有序，只要每次取当前较小值即可维持有序。
复杂度：时间 O(m+n)，空间 O(1)。
易错点：使用哨兵节点可以统一处理头结点变化问题。

28. 两数相加

核心思路：按位相加并维护进位，和手算加法完全一致。
解题步骤：同时遍历两条链表；取当前位值和进位相加；创建新节点存 sum % 10；把 sum // 10 作为新的进位；遍历结束后若进位仍为 1，再补一个节点。
为什么这样做：链表就是倒序存数字，所以从头开始刚好对应从低位向高位加。
复杂度：时间 O(max(m,n))，空间 O(max(m,n))，不计答案链表则为 O(1)。
易错点：遍历条件要考虑 l1、l2、carry 三者任一非空。

29. 删除链表的倒数第 N 个结点

核心思路：前后指针保持 n 个节点距离，当前指针走到末尾时，前指针恰好停在待删节点前一个。
解题步骤：先让 fast 走 n 步；然后 fast、slow 同时移动，直到 fast 到尾；删除 slow.next 即可；为了统一处理删除头结点，前面加哨兵。
为什么这样做：链表无法倒着走，所以用“距离差”模拟倒数定位。
复杂度：时间 O(n)，空间 O(1)。
易错点：一定要加哨兵，否则删除头结点会单独分类。

30. 两两交换链表中的节点

核心思路：一次只处理两个节点，再用前驱节点把已经交换好的部分和后面连接起来。
解题步骤：用哨兵节点指向头部；每轮取出 a = cur.next 和 b = a.next；调整指针顺序为 cur -> b -> a -> next_pair；最后把 cur 移到 a。
为什么这样做：有了前驱节点后，局部交换不会丢掉链表其余部分。
复杂度：时间 O(n)，空间 O(1)。
易错点：改指针前先保存下一段的起点；不要只交换值，题目要求交换节点。

31. K 个一组翻转链表

核心思路：每次先确认剩余节点是否达到 k 个，够的话就局部反转这一组，再和前后两段重新连接。
解题步骤：用哨兵节点定位每一组的前驱 p0；先向后走 k 步检查是否够一组；对这一组做标准链表反转；反转后让组前驱连到新头，让原头连到下一组开头；继续处理后续分组。
为什么这样做：题目要求不足 k 个时保持原样，所以每轮翻转前必须先做长度确认。
复杂度：时间 O(n)，空间 O(1)。
易错点：反转后原组头会变成组尾，它要负责和下一段重新连接。
代码：原笔记里留下的是“翻转后重新接回去”的关键连接语句。

nxt = p0.next
nxt = cur
p0.next = pre
p0 = nxt

32. 随机链表的复制

核心思路：常见做法有两种，哈希表映射旧节点到新节点，或“旧新节点交错插入再拆开”。
解题步骤：交错法更省空间。第一趟在每个旧节点后插入对应新节点；第二趟根据 old.random 去设置 new.random = old.random.next；第三趟把新旧链表拆开。
为什么这样做：新节点就紧跟在旧节点后面，所以任何旧节点想找到自己对应的新节点，只要看 next。
复杂度：时间 O(n)，空间 O(1)，不计新链表。
易错点：拆链表时要同时恢复原链表和提取新链表，顺序别写乱。

33. 排序链表

核心思路：链表适合做归并排序，因为可以在 O(1) 额外空间内拆分和合并。
解题步骤：快慢指针找中点并断开链表；递归排序左右两半；再按“合并两个有序链表”的方式合并。
为什么这样做：链表不支持随机访问，不适合快排那类需要频繁跳位置的算法。
复杂度：时间 O(n log n)，递归栈空间 O(log n)。
易错点：找中点后要把前半段尾节点的 next 断开，否则递归无法收敛。
代码：原笔记中的递归骨架如下。

def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]:
        if head is None or head.next is None:
            return head
        
        head2 = self.middleNode(head)

        head = self.sortList(head)
        head2 = self.sortList(head2)

        return self.mergeTwoLists(head, head2)

34. 合并 k 个升序链表

核心思路：最小堆始终维护当前所有链表头中的最小节点。
解题步骤：把每条非空链表的头节点放入最小堆；每次弹出堆顶接到答案链表后面；如果该节点还有 next，就把 next 再压回堆中。
为什么这样做：每次只需要从 k 个候选头节点里挑最小值，堆正好适合处理这种动态最值问题。
复杂度：时间 O(n log k)，空间 O(k)。
易错点：Python 的 heapq 不能直接比较链表节点，通常要自定义比较或放入三元组。
代码：原笔记保留的是自定义节点比较的关键细节。

ListNode.__lt__ = lambda a, b: a.val < b.val

35. LRU 缓存

核心思路：哈希表负责 O(1) 找节点，双向链表负责 O(1) 删除和移动节点。
解题步骤：哈希表存 key -> node；链表按最近使用顺序维护节点，头部表示最近使用；get 时找到节点并移动到头部；put 时若键存在就更新并移到头部，若不存在就插入新节点，超过容量则删除尾部节点。
为什么这样做：LRU 的核心是“既要快速查，又要快速淘汰最久未使用项”，单靠哈希表或链表都不够。
复杂度：get 和 put 都是 O(1)，空间 O(capacity)。
易错点：删除节点和插入头部要封装成独立函数，逻辑会清晰很多。
代码：原笔记中的双向链表基本操作如下。

# 删除一个节点（抽出一本书）
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

二叉树 / 图 / 回溯

36. 二叉树的中序遍历

核心思路：中序遍历顺序固定为“左 -> 根 -> 右”。
解题步骤：递归写法先递归左子树，再记录当前节点值，最后递归右子树；迭代写法用栈一路把左节点压到底，再回头访问。
为什么这样做：中序遍历天生就是 BST 从小到大输出的顺序。
复杂度：时间 O(n)，空间 O(h)。
易错点：迭代写法不是只压一层左节点，而是要不断往左走到底。

37. 二叉树的最大深度

核心思路：当前节点深度等于左右子树最大深度的较大值再加一。
解题步骤：空节点返回 0；递归求左右深度；返回 max(left, right) + 1。
为什么这样做：树的高度天然就是一个“由子问题向上汇总”的递归定义。
复杂度：时间 O(n)，空间 O(h)。
易错点：空树深度是 0，不是 1。

38. 翻转二叉树

核心思路：每个节点都交换左右子树即可。
解题步骤：访问当前节点时交换 left 和 right；再递归处理左右子树。
为什么这样做：整棵树的翻转就是局部交换在每个节点上的重复。
复杂度：时间 O(n)，空间 O(h)。
易错点：先交换后递归或先递归后交换都可以，但要统一写法。

39. 对称二叉树

核心思路：不是看每棵子树各自是否对称，而是同时比较“左子树的左边”和“右子树的右边”。
解题步骤：定义递归函数 dfs(p, q)；若两者都空则对称；若一空一非空或值不同则不对称；继续比较 p.left 对 q.right，以及 p.right 对 q.left。
为什么这样做：镜像关系是成对出现的，不是单个子树内部独立判断。
复杂度：时间 O(n)，空间 O(h)。
易错点：入口不是 dfs(root)，而是 dfs(root.left, root.right)。

40. 二叉树的直径

核心思路：某个节点的“穿过它的最长路径”是左深度加右深度，全局取最大即可。
解题步骤：递归函数返回当前节点的最大向下深度；在回溯时用 left_depth + right_depth 更新全局直径。
为什么这样做：最长路径未必经过根节点，所以要把每个节点都当成“拐点”试一遍。
复杂度：时间 O(n)，空间 O(h)。
易错点：返回给父节点的是单边最大深度，不是左右之和。

41. 二叉树的层序遍历

核心思路：标准 BFS，按层推进。
解题步骤：把根节点入队；每轮先记录当前队列长度，这个长度就是本层节点数；依次弹出并把左右子节点入队；把本层值收集成数组加入答案。
为什么这样做：队列天然符合“先进先出”的层次访问顺序。
复杂度：时间 O(n)，空间 O(n)。
易错点：空树要返回空列表；按层处理时不要直接遍历一个会增长的队列。

42. 将有序数组转换为二叉搜索树

核心思路：每次取中点做根，左右两侧分别递归构造子树。
解题步骤：若区间为空返回空节点；取中间下标 mid 创建根节点；递归构造左半区间和右半区间。
为什么这样做：有序数组的中点能保证左右子树大小尽量平衡，同时满足 BST 有序性。
复杂度：时间 O(n)，空间 O(log n)，递归栈。
易错点：区间写法要统一，推荐用闭区间或左闭右开。

43. 验证二叉搜索树

核心思路：判断 BST 不能只看父子关系，要看每个节点是否落在合法区间内。
解题步骤：递归函数传入当前节点可取的上下界 (low, high)；若节点值不在区间内则返回 False；左子树区间变为 (low, node.val)，右子树变为 (node.val, high)。
为什么这样做：某个节点虽然比父节点小，但也可能违反更高层祖先给出的约束。
复杂度：时间 O(n)，空间 O(h)。
易错点：BST 要求严格小于和严格大于，不能写成 <= / >= 的宽松比较。

44. 二叉搜索树中第 k 小的元素

核心思路：BST 的中序遍历就是从小到大顺序。
解题步骤：做一次中序遍历；每访问一个节点就把 k -= 1；当 k == 0 时当前节点值就是答案。
为什么这样做：中序顺序刚好等于 BST 的有序序列。
复杂度：时间 O(h + k)，最坏 O(n)；空间 O(h)。
易错点：如果想提前返回，递归函数要注意把结果一路向上传递。

45. 二叉树的右视图

核心思路：层序遍历时，每层最后一个节点就是从右侧看到的节点。
解题步骤：做 BFS；每层处理完时把该层最后一个节点值加入答案；或者 DFS 时先访问右子树，并记录每个深度第一次出现的节点。
为什么这样做：右视图只和每层最靠右的可见节点有关。
复杂度：时间 O(n)，空间 O(n)。
易错点：如果用 BFS，加入答案的是节点值，不是整个节点。

46. 二叉树展开为链表

核心思路：把树按先序遍历顺序拉平成“只用右指针”的链表。
解题步骤：可以倒着做先序，即按“右 -> 左 -> 根”递归；维护一个 prev 指针，表示已经展开好的链表头；回溯时让当前节点的 right = prev、left = None，再更新 prev = node。
为什么这样做：倒序先序能让当前节点很自然地接到已经处理好的后继链表前面。
复杂度：时间 O(n)，空间 O(h)。
易错点：原地展开后所有 left 必须置空。

47. 从前序与中序遍历构造二叉树

核心思路：前序的第一个值是根，中序里根左边是左子树，右边是右子树。
解题步骤：预处理一个“中序值 -> 下标”的哈希表；递归时根据前序根节点在中序中的位置确定左右子树大小，再切分前序区间递归构造。
为什么这样做：前序决定谁是根，中序决定左右边界，两者结合就能唯一还原树。
复杂度：时间 O(n)，空间 O(n)。
易错点：不要在每次递归里线性查根节点在中序中的位置，否则会退化到 O(n^2)。

48. 路径总和 III

核心思路：树上的路径和问题也能做前缀和，只不过前缀和沿递归路径维护。
解题步骤：用 cnt 记录“当前根到父节点路径上，每个前缀和出现了多少次”；到达节点时更新当前前缀和 s；把 cnt[s-target] 加入答案；递归左右子树；回溯时把 cnt[s] 减回去。
为什么这样做：如果两段前缀和之差是 target，对应的中间那段路径和就是 target。
复杂度：时间 O(n)，空间 O(h) 到 O(n)。
易错点：回溯时必须恢复哈希表状态，不然会污染兄弟子树。

49. 二叉树的最近公共祖先

核心思路：递归从下往上返回“当前子树里有没有找到 p 或 q”。
解题步骤：若当前节点为空或等于 p/q，直接返回；递归左右子树；若左右都非空，说明当前节点就是最近公共祖先；否则返回非空的一边。
为什么这样做：当两个目标第一次在不同方向被找到时，分叉点就是最近公共祖先。
复杂度：时间 O(n)，空间 O(h)。
易错点：只要当前节点等于 p 或 q，就应该直接返回当前节点，不能继续往下找。

50. 二叉树中的最大路径和

核心思路：每个节点都尝试做一次“路径拐点”，向上返回时只能带走单边最大贡献。
解题步骤：递归求左右子树能提供的最大向下路径和，若为负就当作 0；用 left + right + node.val 更新全局最大值；向父节点返回 max(left, right) + node.val。
为什么这样做：完整路径可以在当前节点左右两边同时展开，但返回给父节点时只能选一条边继续向上延伸。
复杂度：时间 O(n)，空间 O(h)。
易错点：返回值和更新全局答案的值不是同一个概念。
代码：原笔记中的关键状态转移正是这两行。

ans = max(ans, l_val + r_val + node.val)
return max(max(l_val, r_val) + node.val, 0)

51. 岛屿数量

核心思路：遍历网格，遇到陆地就做一次 DFS/BFS，把整块岛淹没掉。
解题步骤：双层循环扫描矩阵；看到 '1' 就答案加一，并向四个方向扩展，把所有连通的 '1' 改成 '0'。
为什么这样做：每块岛只会在第一次遇到时被完整访问一次。
复杂度：时间 O(mn)，空间 O(mn) 或递归栈 O(mn)。
易错点：可以直接修改原网格，不一定非要再开 visited。

52. 腐烂的橘子

核心思路：多源 BFS，所有初始腐烂橘子同时向外扩散。
解题步骤：先把所有腐烂橘子入队，并统计新鲜橘子数；按层做 BFS，每一层代表一分钟；把相邻新鲜橘子变腐烂并入队；最终若新鲜橘子归零就返回分钟数，否则返回 -1。
为什么这样做：多个起点同时扩散时，最自然的模型就是多源最短路，也就是多源 BFS。
复杂度：时间 O(mn)，空间 O(mn)。
易错点：只有真正腐烂了新鲜橘子时，时间才应该增加。

53. 课程表

核心思路：检测有向图里是否存在环。
解题步骤：建图；用 0/1/2 表示未访问、访问中、已完成；DFS 到某个节点时先标成访问中；若递归到访问中的节点说明有环；整棵 DFS 完成后标成已完成。
为什么这样做：拓扑排序存在当且仅当图中无环。
复杂度：时间 O(V+E)，空间 O(V+E)。
易错点：颜色 1 表示当前递归路径上，遇到它才算成环。

54. 实现 Trie（前缀树）

核心思路：每个节点保存若干子节点和一个“是否为单词结尾”的标志。
解题步骤：insert 逐字符向下，不存在就创建；search 逐字符查找并最终判断结尾标志；startsWith 只要路径存在即可返回 True。
为什么这样做：Trie 专门用来复用公共前缀，前缀查询效率高。
复杂度：单次操作时间 O(L)，L 为字符串长度。
易错点：search 和 startsWith 的区别只在最后是否要求 is_end == True。

55. 全排列

核心思路：回溯逐位填数，每层决定当前位置放哪个未使用元素。
解题步骤：维护 path 和 used；每层遍历所有数字，选一个没用过的加入路径；递归到长度为 n 时记录答案；回溯时撤销选择。
为什么这样做：排列的本质就是依次做 n 次互斥选择。
复杂度：时间 O(n * n!)，空间 O(n)，不计输出。
易错点：记录答案时要拷贝 path。

56. 子集

核心思路：每个元素都只有“选”或“不选”两种决策。
解题步骤：递归到位置 i 时，先走“不选 nums[i]”的分支，再走“选 nums[i]”的分支；当 i == n 时记录当前路径。
为什么这样做：子集问题天然对应一棵二叉决策树。
复杂度：时间 O(n * 2^n)，空间 O(n)，不计输出。
易错点：这题不需要 used 数组，因为每个元素只会被处理一次。

57. 电话号码的字母组合

核心思路：每个数字对应一个字符集合，回溯枚举每一位的选择。
解题步骤：建立数字到字母的映射；从第 i 位数字开始，遍历它对应的所有字母，加入路径后递归处理下一位；路径长度等于数字串长度时记录答案。
为什么这样做：每一位的选择相互独立，本质上是笛卡尔积枚举。
复杂度：时间约 O(4^n)，空间 O(n)。
易错点：空字符串要返回空列表；最终加入答案时是 ''.join(path)。

58. 组合总和

核心思路：回溯时对每个数字都考虑“当前继续选它”还是“跳到下一个数”。
解题步骤：可以先排序方便剪枝；递归参数包含当前下标和剩余目标值 left；如果 left == 0 就记录答案；若 left < 0 或下标越界则返回；分支一是不选当前数去下一个下标，分支二是选当前数并保持下标不变。
为什么这样做：同一个数字可以重复使用，所以选了之后下标不前进。
复杂度：与答案规模相关，通常写作指数级。
易错点：如果用了排序，可以在当前值已经大于 left 时直接剪枝。

59. 括号生成

核心思路：合法括号串的约束只有两个，左括号总数不能超过 n，任意前缀中右括号数不能超过左括号数。
解题步骤：递归维护已经放了多少个左括号和右括号；若左括号数小于 n，可以放左括号；若右括号数小于左括号数，可以放右括号；右括号数达到 n 时记录答案。
为什么这样做：这两个约束已经完全刻画了合法括号串。
复杂度：与 Catalan 数相关，输出规模级别。
易错点：不是所有长度为 2n 的串都生成后再筛掉，而是边生成边保证合法。

60. 单词搜索

核心思路：从每个起点做 DFS，沿四个方向匹配目标单词，同时避免重复使用同一个格子。
解题步骤：枚举每个格子作为起点；递归匹配第 k 个字符；当前字符不匹配或越界就返回 False；匹配成功后临时标记已访问，再向四个方向继续搜索；回溯时恢复现场。
为什么这样做：路径依赖于上一步位置，属于标准网格回溯。
复杂度：时间 O(mn * 4^L)，空间 O(L)。
易错点：访问过的格子要在回溯时恢复，否则会影响其他分支。

61. 分割回文串

核心思路：回溯枚举切割位置，只在当前子串是回文时继续向下。
解题步骤：从起点 start 出发，枚举结束位置 end；如果 s[start:end+1] 是回文串，就把它加入路径并递归处理 end+1；到达字符串末尾时记录答案。
为什么这样做：每一次切割都对应“选择一个回文前缀”，路径天然构成答案。
复杂度：与答案规模相关，最坏指数级。
易错点：回文判断若每次都现算会较慢，二刷时可以考虑预处理回文 DP 表。

62. N 皇后

核心思路：按行放皇后，列和两条对角线都不能冲突。
解题步骤：递归处理第 row 行；尝试每一列 col；若列、主对角线 row-col、副对角线 row+col 都未被占用，就放置皇后并递归下一行；回溯时撤销标记。
为什么这样做：每行恰放一个皇后，所以按行搜索最自然，冲突检测也最简单。
复杂度：指数级。
易错点：对角线下标可能为负，通常用集合记录，或在数组中做偏移。

二分

63. 搜索插入位置

核心思路：找“第一个大于等于 target 的位置”。
解题步骤：标准二分；若 nums[mid] < target，去右边；否则保留左半部分；最终 left 就是插入位置。
为什么这样做：插入后数组仍要有序，所以位置定义就是左侧都小于、当前位置及右侧都大于等于目标。
复杂度：时间 O(log n)，空间 O(1)。
易错点：这题和“精确查找一个值”不完全一样，更接近 lower_bound 模板。

65. 在排序数组中查找元素的第一个和最后一个位置

核心思路：做两次二分，分别找 target 的左边界和 target+1 的左边界。
解题步骤：第一次二分求第一个大于等于 target 的位置 L；若越界或 nums[L] != target，直接返回 [-1, -1]；第二次求第一个大于等于 target+1 的位置 R，最终右边界是 R-1。
为什么这样做：一个连续相等区间可以用左右边界的 lower_bound 表示。
复杂度：时间 O(log n)，空间 O(1)。
易错点：右边界不要再单独写一套完全不同的模板，容易出错。

66. 搜索旋转排序数组

核心思路：虽然数组被旋转，但每次二分时总有一半仍然是有序的。
解题步骤：取中点 mid；判断左半还是右半有序；再看 target 是否落在有序半边的范围内，决定往哪边继续找。
为什么这样做：旋转数组本质是两个升序段拼接而成，二分时总能识别出一个正常升序段。
复杂度：时间 O(log n)，空间 O(1)。
易错点：判断区间时要带上等号，特别是 target == nums[mid] 的直接返回分支。

67. 寻找旋转排序数组中的最小值

核心思路：最小值就是旋转点，二分比较 mid 和右端点即可定位。
解题步骤：若 nums[mid] > nums[right]，说明最小值在右半边；否则最小值在左半边或就是 mid；不断缩小区间直到 left == right。
为什么这样做：右半段一定包含数组最后的升序尾部，和右端点比较能判断旋转点在哪侧。
复杂度：时间 O(log n)，空间 O(1)。
易错点：无重复元素时这个判定最稳定；不要和“搜索旋转数组”的模板混用。

68. 寻找两个正序数组的中位数

核心思路：在较短数组上二分“切分位置”，让左右两半总长度合适，且左半最大值不大于右半最小值。
解题步骤：设切分后左半总长度为 (m+n+1)//2；在较短数组中二分切分点 i，另一数组切分点 j 由总长度决定；检查 A[i-1] <= B[j] 且 B[j-1] <= A[i] 是否成立；成立后根据总长度奇偶计算中位数。
为什么这样做：中位数只取决于“左右两半是否平衡”和“两边边界大小关系”。
复杂度：时间 O(log(min(m,n)))，空间 O(1)。
易错点：边界要用 -inf 和 inf 兜底；一定在较短数组上二分。

贪心

77. 买卖股票的最佳时机

核心思路：遍历过程中维护历史最低价，并用当前价格尝试更新最大利润。
解题步骤：初始化 min_price = +inf，ans = 0；每次先用 price - min_price 更新答案，再更新 min_price。
为什么这样做：若只允许买卖一次，最佳卖点的利润只取决于它前面出现过的最低买点。
复杂度：时间 O(n)，空间 O(1)。
易错点：顺序上通常先算利润再更新最低价，可读性更强。

78. 跳跃游戏

核心思路：维护当前能到达的最远位置。
解题步骤：遍历下标 i；若 i 已经大于当前最远可达位置 mx，说明断了，返回 False；否则更新 mx = max(mx, i + nums[i])；遍历结束返回 True。
为什么这样做：能否到终点只取决于中途有没有出现“到不了的下标”。
复杂度：时间 O(n)，空间 O(1)。
易错点：一旦 mx >= n-1 可以提前返回。

79. 跳跃游戏 II

核心思路：按层贪心，当前步数能覆盖一个区间，在这个区间里找下一步能覆盖的最远位置。
解题步骤：遍历到 n-2 即可；维护当前层的右边界 end 和下一层能到的最远位置 far；每次更新 far；当走到 end 时，说明必须再跳一步，并把 end = far。
为什么这样做：每跳一步就像 BFS 扩展一层，层数就是最少步数。
复杂度：时间 O(n)，空间 O(1)。
易错点：最后一个位置不用再跳，所以循环只到 n-2。

80. 划分字母区间

核心思路：先知道每个字符最后一次出现的位置，再线性扫描合并区间。
解题步骤：预处理每个字符的最后下标；遍历字符串时维护当前区间右端点 end = max(end, last[s[i]])；当 i == end 时，说明一个分段结束，记录长度并开启下一段。
为什么这样做：某段里只要还有字符的最后一次出现落在更后面，这段就不能切开。
复杂度：时间 O(n)，空间 O(字符集大小)。
易错点：记录区间长度时是 end - start + 1。

动态规划

81. 爬楼梯

核心思路：到第 i 阶只能从 i-1 或 i-2 走来。
解题步骤：设 f[i] = f[i-1] + f[i-2]；从小到大递推；也可以直接用两个变量滚动保存前两项。
为什么这样做：最后一步只有两种选择，所以状态转移就是 Fibonacci。
复杂度：时间 O(n)，空间 O(1)。
易错点：n = 1 和 n = 2 要正确初始化。

82. 杨辉三角

核心思路：每个内部位置都等于上一行左上和右上的和。
解题步骤：初始化每行全为 1；从第三行开始填内部位置 ans[i][j] = ans[i-1][j-1] + ans[i-1][j]。
为什么这样做：组合数的递推关系就是这样定义的。
复杂度：时间 O(n^2)，空间 O(n^2)。
易错点：每行首尾永远是 1，不需要额外计算。

83. 打家劫舍

核心思路：当前位置只有“偷”或“不偷”两种选择。
解题步骤：设 f[i] 为前 i 间房的最大收益，则 f[i] = max(f[i-1], f[i-2] + nums[i])；可用两个变量滚动优化。
为什么这样做：偷当前房子就不能偷前一间，不偷当前就继承前一间的最优解。
复杂度：时间 O(n)，空间 O(1)。
易错点：注意状态含义和下标偏移，推荐用滚动变量简化边界。

84. 完全平方数

核心思路：把每个完全平方数看成一种“可重复使用的物品”，做完全背包。
解题步骤：初始化 f[0]=0，其余为无穷大；枚举每个平方数 x = i*i；再枚举金额 j 从 x 到 n，转移 f[j] = min(f[j], f[j-x] + 1)。
为什么这样做：题目要求最少数量，本质是标准最短完全背包。
复杂度：时间 O(n * sqrt(n))，空间 O(n)。
易错点：内层循环要正向遍历，表示“同一物品可重复使用”。

85. 零钱兑换

核心思路：同样是完全背包，状态表示凑出某金额所需的最少硬币数。
解题步骤：f[0]=0，其余初始化为大数；枚举硬币 x；再枚举金额 c 从 x 到 amount，转移 f[c] = min(f[c], f[c-x] + 1)；最后看 f[amount] 是否仍为无穷大。
为什么这样做：每种硬币都可以无限使用，和完全平方数是同一模型。
复杂度：时间 O(n * amount)，空间 O(amount)。
易错点：最后无解时返回 -1，不是无穷大。

86. 单词拆分

核心思路：f[i] 表示前缀 s[:i] 能否被词典切分出来。
解题步骤：初始化 f[0] = True；遍历终点 i；再枚举切分点 j，如果 f[j] 为真且 s[j:i] 在词典中，则 f[i] = True。
为什么这样做：最后一段单词从哪里开始是不确定的，所以需要枚举切分点。
复杂度：时间取决于枚举方式，常见写法 O(n^2)；空间 O(n)。
易错点：为了减枝，可以先记录词典中单词最大长度。

87. 最长递增子序列

核心思路：朴素 DP 中，f[i] 表示以 nums[i] 结尾的 LIS 长度。
解题步骤：初始化所有 f[i]=1；枚举 i 时再枚举 j < i；如果 nums[j] < nums[i]，就尝试用 f[j] + 1 更新 f[i]；最后取最大值。
为什么这样做：任何以 i 结尾的递增子序列，都必须从某个更小的前驱状态转移过来。
复杂度：时间 O(n^2)，空间 O(n)。
易错点：二刷时可以进一步记一下贪心 + 二分的 O(n log n) 做法，但 Hot100 里先把 DP 想清楚最重要。

88. 乘积最大子数组

核心思路：乘积会受负号影响，所以要同时维护“当前最大乘积”和“当前最小乘积”。
解题步骤：遍历数组；当前数若为负，会让最大最小角色互换；更新 mx = max(x, mx*x, mn*x)，mn = min(x, mx_old*x, mn*x)；全局维护最大值。
为什么这样做：最小负积乘上一个负数，可能瞬间变成最大的正积。
复杂度：时间 O(n)，空间 O(1)。
易错点：更新时要先保存旧的 mx，避免连带污染 mn 的计算。

89. 分割等和子集

核心思路：若总和为偶数，问题就变成“能否选出若干数，使和恰好等于总和一半”。
解题步骤：先求数组总和，若为奇数直接返回 False；设目标值 target = sum // 2；做 0/1 背包，f[j] 表示能否凑出和 j；每个数只能用一次，所以内层金额倒序遍历。
为什么这样做：两组和相等，等价于从数组中挑一部分凑出一半总和。
复杂度：时间 O(n * target)，空间 O(target)。
易错点：这是 0/1 背包，不是完全背包，内层必须倒序。

91. 不同路径

核心思路：机器人走到某格只能从上边或左边过来。
解题步骤：设 f[i][j] = f[i-1][j] + f[i][j-1]；第一行和第一列都只能直走，所以初始化为 1。
为什么这样做：最后一步只有向下或向右两种来源。
复杂度：时间 O(mn)，空间 O(mn) 或 O(n)。
易错点：边界初始化很关键，第一行第一列都为 1。

92. 最小路径和

核心思路：到达某格的最小代价等于上方和左方最小代价中的较小者，再加当前格权值。
解题步骤：设 f[i][j] 为到 (i,j) 的最小路径和；第一行只能从左边来，第一列只能从上边来；其余位置按 min(f[i-1][j], f[i][j-1]) + grid[i][j] 转移。
为什么这样做：路径只能向右或向下，最后一步来源固定只有两种。
复杂度：时间 O(mn)，空间 O(mn) 或原地 O(1) 额外空间。
易错点：第一行和第一列要单独初始化，不能直接套通式。

93. 最长回文子串

核心思路：从中心向两边扩展，分别处理奇数长度和偶数长度回文。
解题步骤：把每个字符和每对相邻字符都当作中心；向左右扩展，直到字符不同或越界；记录最长区间。
为什么这样做：回文串的结构完全由中心决定，扩展时能在线性中心数内找到所有候选。
复杂度：时间 O(n^2)，空间 O(1)。
易错点：奇数中心是 (i,i)，偶数中心是 (i,i+1)。

94. 最长公共子序列

核心思路：二维 DP，f[i][j] 表示 s[:i] 和 t[:j] 的 LCS 长度。
解题步骤：若当前字符相同，则 f[i][j] = f[i-1][j-1] + 1；否则 f[i][j] = max(f[i-1][j], f[i][j-1])；最终答案是右下角。
为什么这样做：最后一个字符要么配对成功一起贡献 1，要么至少有一个字符不参与最优解。
复杂度：时间 O(nm)，空间 O(nm)。
易错点：状态通常定义成前 i 个字符和前 j 个字符，这样第一行第一列可以自然初始化为 0。
代码：原笔记中这段实现是标准模板。

class Solution:
    def longestCommonSubsequence(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        for i, x in enumerate(s):
            for j, y in enumerate(t):
                f[i + 1][j + 1] = f[i][j] + 1 if x == y else max(f[i][j + 1], f[i + 1][j])
        return f[n][m]

95. 编辑距离

核心思路：二维 DP，f[i][j] 表示把 s[:i] 变成 t[:j] 的最少操作数。
解题步骤：初始化第一行和第一列，表示空串和前缀之间的插入/删除次数；若当前字符相同，f[i][j] = f[i-1][j-1]；否则在删除、插入、替换三种操作里取最小值再加一。
为什么这样做：最后一步只可能是删一个、插一个或替换一个。
复杂度：时间 O(nm)，空间 O(nm)。
易错点：f[0][j] 和 f[i][0] 的初始化不能漏。
代码：这段代码保留了最典型的状态转移。

class Solution:
    def minDistance(self, s: str, t: str) -> int:
        n, m = len(s), len(t)
        f = [[0] * (m + 1) for _ in range(n + 1)]
        f[0] = list(range(m + 1))
        for i, x in enumerate(s):
            f[i + 1][0] = i + 1
            for j, y in enumerate(t):
                f[i + 1][j + 1] = f[i][j] if x == y else min(
                    f[i][j + 1], f[i + 1][j], f[i][j]
                ) + 1
        return f[n][m]

技巧题

96. 只出现一次的数字

核心思路：相同数字成对出现时，异或后会抵消为 0。
解题步骤：把所有数字依次异或起来，最后剩下的就是只出现一次的数字。
为什么这样做：a ^ a = 0，0 ^ x = x，且异或满足交换律和结合律。
复杂度：时间 O(n)，空间 O(1)。
易错点：这题的前提是“其余元素都恰好出现两次”。

97. 多数元素

核心思路：Boyer-Moore 投票算法，把不同元素两两抵消。
解题步骤：维护候选值 candidate 和计数 hp；hp == 0 时更新候选；当前数等于候选就加一，否则减一；遍历结束后候选值就是多数元素。
为什么这样做：多数元素数量超过一半，不可能在配对抵消后被完全消掉。
复杂度：时间 O(n)，空间 O(1)。
易错点：如果题目不保证一定存在多数元素，最后还需要再验证一次。

98. 颜色分类

核心思路：荷兰国旗问题，三指针把数组划成 0 区、1 区、未处理区、2 区。
解题步骤：l 指向下一个放 0 的位置，r 指向下一个放 2 的位置，i 在中间扫描；遇到 0 就和 l 交换并同时前进；遇到 2 就和 r 交换并让 r 左移，但 i 先别动；遇到 1 直接跳过。
为什么这样做：每次交换都能把某个元素放进最终区间，因此只需一趟扫描。
复杂度：时间 O(n)，空间 O(1)。
易错点：和右边 2 区交换后，i 不能立刻右移，因为换回来的数还没处理。

99. 下一个排列

核心思路：从右往左找第一个下降位置，把它换成右边刚好比它大的数，再把后缀反转成最小升序。
解题步骤：先找最大下标 i 使 nums[i] < nums[i+1]；若存在，再从右往左找第一个大于 nums[i] 的 j 交换；最后反转 i+1 到末尾的后缀。
为什么这样做：为了得到“刚刚大一点”的下一个排列，前缀要尽量晚地变大，后缀要变成最小。
复杂度：时间 O(n)，空间 O(1)。
易错点：如果整个数组单调不增，说明当前已经是最大排列，直接整体反转即可。
代码：原笔记里的代码就是这个标准流程。

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left, right = i + 1, n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

100. 寻找重复数

核心思路：把数组看成“下标指向下一个下标”的链表，重复数就是环的入口。
解题步骤：先用快慢指针找到相遇点；再让一个指针从 0 出发，另一个从相遇点出发，同时每次走一步；再次相遇的位置就是重复数。
为什么这样做：由于数值范围在 1..n，一定会出现某个下标被多个位置指向，从而形成环。
复杂度：时间 O(n)，空间 O(1)。
易错点：这是 Floyd 判圈的变形，重复数不是“值重复次数”，而是“入环口编号”。
代码：原笔记中的实现可以直接作为模板记忆。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = fast = 0
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if fast == slow:
                break

        head = 0
        while slow != head:
            slow = nums[slow]
            head = nums[head]
        return slow

LeetCode Hot100 复习索引

目录

哈希 / 数组 / 双指针 / 滑动窗口

子数组 / 前缀和 / 单调结构 / 堆

矩阵

链表

二叉树 / 图 / 回溯

二分

贪心

动态规划

技巧题

哈希 / 数组 / 双指针 / 滑动窗口

1. 两数之和

2. 字母异位词分组

3. 最长连续序列

4. 移动零

5. 盛最多水的容器

6. 三数之和

7. 接雨水

8. 无重复字符的最长子串

9. 找到字符串中所有字母异位词

12. 最小覆盖子串

14. 合并区间

15. 轮转数组

16. 除了自身以外数组的乘积

17. 缺失的第一个正数

子数组 / 前缀和 / 单调结构 / 堆

10. 和为 k 的子数组

11. 滑动窗口最大值

13. 最大子数组和

69. 有效的括号

70. 最小栈

71. 字符串解码

72. 每日温度

73. 柱状图中最大的矩形

74. 数组中的第 k 个最大元素

75. 前 k 个高频元素

76. 数据流的中位数

90. 最长有效括号

矩阵

18. 矩阵置零

19. 螺旋矩阵

20. 旋转图像

21. 搜索二维矩阵 II

64. 搜索二维矩阵

链表

22. 相交链表

23. 反转链表

24. 回文链表

25. 环形链表

26. 环形链表 II

27. 合并两个有序链表

28. 两数相加

29. 删除链表的倒数第 N 个结点

30. 两两交换链表中的节点

31. K 个一组翻转链表

32. 随机链表的复制

33. 排序链表

34. 合并 k 个升序链表

35. LRU 缓存

二叉树 / 图 / 回溯

36. 二叉树的中序遍历

37. 二叉树的最大深度

38. 翻转二叉树

39. 对称二叉树

40. 二叉树的直径

41. 二叉树的层序遍历

42. 将有序数组转换为二叉搜索树

43. 验证二叉搜索树

44. 二叉搜索树中第 k 小的元素

45. 二叉树的右视图

46. 二叉树展开为链表

47. 从前序与中序遍历构造二叉树

48. 路径总和 III

49. 二叉树的最近公共祖先

50. 二叉树中的最大路径和

51. 岛屿数量

52. 腐烂的橘子

53. 课程表

54. 实现 Trie（前缀树）