📑 本页目录(点开跳转)
附录A · 速查
随用随查。用错误现象找一条排查线索,再跳回正文核对。
📌 只查当前卡住的地方。对照一条规则、跑一个输入,就可以回到手上的题。
🎯 一句话
记得现象就查恢复入口,有错误答案就查常见症状,忘了变量的作用就查不变量卡,要复跑就选一个边界输入。
第一次学或暂时不知道先读哪章,去 00 · 学习路线。这里的线索指向正文,代码和完整推导都在那里。
🧭 一、先认出题型:数据形状 → 你真正要解决的问题
按「眼前发生了什么」选一行。还没定位到问题时,再往下按数据形状找代表题。
| 我看到什么 | 先核哪件事 | 去哪一小节 |
|---|---|---|
| 反转后只剩头两个节点 | 先核旧 next 有没有在掉头前保存。 | 01 · 反转第一轮 |
| 递归回来时不知道还有什么没做 | 先写这层返回什么,再看父层如何接着算。 | 02 · 深度与调用栈 |
| 窗口已经右移,最大值还停在旧位置 | 先查队首下标是否已经过期。 | 03 · 窗口队首何时出队 |
| 二分找不到目标时读到了数组末尾之外 | 插入位置可能等于长度。实际读下标前先核区间。 | 04 · 插入边界 |
| 输入翻倍,想直接把运行时间也翻倍 | 先看实际增长模型和比较条件。 | 04 · 输入规模与耗时 |
| 最大子数组和把不相邻的数字接到一起 | 分开保存以当前位置结尾的最优和全局最优。 | 05 · 结尾状态 |
| 走错一条路后,明明可用的格子也找不到了 | 核对失败后是否恢复当前分支的格子。 | 06 · 六格回退反例 |
| 坐标数字和合法,机器人却到不了 | 核对是否存在一条从起点出发且逐格合法的路径。 | 06 · 合法与可达 |
| 负数位运算与预期的补码不同 | 先确定题目约定的位宽和有符号解释。 | 07 · 定宽与补码 |
| 最长无重复子串的左边界跳回去了 | 只有上次出现的位置还在窗口内,才移动左边界。 | 08 · 不回退的左边界 |
| 看起来一样的字符,长度或位置却不同 | 先约定数的是字节、Unicode 码点,还是用户看到的字素簇。 | 08 · 文本计数单位 |
| 模式失配后不知道该退到哪 | 先查匹配长度和可复用的前后缀。 | 08 · KMP 失配回退 |
再按数据形状找代表题
| 类别 | 你真正要解决的问题 | 本板块代表题 | 章 |
|---|---|---|---|
| 链表 | 节点没有下标,怎样不丢路 | 反转、合并、环入口 | 01 |
| 树 | 一层分成多条路,怎样把结果带回来 | 深度、层序、路径和、最近公共祖先 | 02 |
| 栈与队列 | 取最近、取最早,还是淘汰过期的候选 | 两栈队列、min 栈、滑动窗口最大值 | 03 |
| 搜索与排序 | 怎样缩小边界或只保留需要的候选 | 二分边界、旋转数组、最小 k 个数 | 04 |
| 动态规划 | 怎样从较小问题的状态得到当前答案 | 最大子数组和、跳台阶、正则匹配 | 05 |
| 回溯 | 有分叉时,怎样试完一条再干净地回来 | 矩阵路径、机器人范围、排列 | 06 |
| 位运算与模拟 | 规则很机械,怎样逐步翻译而不漏边界 | 异或分组、二进制加法、螺旋矩阵 | 07 |
| 字符串 | 输入很脏,怎样一格一格地吃进去 | atoi、最长无重复子串、字符流 | 08 |
🧩 二、⭐ 不变量卡:每题一句,忘了就看这一句
这里把循环中始终成立的关系、递归的返回约定和几个输入契约放在一起。记不起变量含义时,读对应一行再跳正文。
| 题 | 一句话不变量 | 章 |
|---|---|---|
| 反转链表 | 每轮结束后,prev 指向已反转的前缀,cur 指向尚未处理的后缀 |
01 · 反转链表 |
| 合并两个有序链表 | 有序结果的已选前缀到 tail 为止。a、b 各指向本链中还没取的首个节点。 |
01 · 合并链表 |
| 链表中环的入口 | 快慢相遇 ⇒ 有环;一个回头,两人同速再见就是入口 | 01 · 环入口 |
| 二叉树深度 | depth(node) 永远返回「以 node 为根的子树有多高」,父节点不必知道孩子内部怎么数 |
02 · 树的深度 |
| 层序打印 | 队列里排着的就是「先来的先处理」 | 02 · 层序打印 |
| 路径和 | path 始终是当前这条根到节点的路:进节点 append,离开节点 pop |
02 · 路径和 |
| 最近公共祖先 | 递归交回「在这棵子树里找到的目标节点,或已经确定的公共祖先」 | 02 · 公共祖先 |
| 前、中、后序 | 保持左右子树的访问次序。当前节点的记录位置决定前、中、后序。 | 02 · 三种 DFS |
| 两个栈实现队列 | outbox 非空时,顶部是最早进入且尚未出队的元素。只有它空了才整批搬运。 |
03 · 两栈队列 |
| min 栈 | mins 的每一层记「走到这一层为止的最小值」 |
03 · 最小值栈 |
| 滑动窗口最大值 | 队列里只留可能成为最大值的人;⭐ 存的是下标不是值 | 03 · 窗口最大值 |
lower_bound |
待检查的元素在 [left, right);插入边界可在 [left, right],包括数组末尾 len(nums)。 |
04 · 插入边界 |
| 旋转数组最小值 | 中点大于右端时去右侧,小于时保留中点及左侧。相等时,这个实现只将右边界左移一格,仍保留一个最小值。 | 04 · 旋转数组 |
| 最小的 k 个数 | 只维护 k 个候选,不必把全部排好 | 04 · 最小 k 个数 |
| 快排分区 | 分区后基准落在最终位置,只调度两侧尚未排好的区间。 | 04 · 区间调度 |
| 连续子数组最大和 | best_ending_here 是「必须以当前位置结尾」的最大和,它不等于全局答案 |
05 · 最大子数组和 |
| 跳台阶 | 允许每步跳 1 或 2 阶时,到第 n ≥ 2 阶的最后一步来自第 n−1 或 n−2 阶。 |
05 · 跳台阶 |
正则匹配(. 和 *) |
* 有两条路:跳过「字符+星号」,或吃一个字符后继续留在原模式 |
05 · 正则匹配 |
| 数字三角形 | 原地压成一行时,更新前确认两份孩子状态还在。 | 05 · 三角形路径 |
| 矩阵中的路径 | 一个格子在当前路径中不能重复使用:进来标记、离开还原 | 06 · 矩阵拼字 |
| 机器人的运动范围 | 从起点逐格扩展;行列坐标的十进制各位数字之和不得超过阈值。已经扩展的格子在本次搜索中不再扩展。 | 06 · 机器人范围 |
| 字符串的排列 | 每个递归调用为当前前缀填一位;它的局部 used 让这一位的相同候选只试一次。 |
06 · 字符串排列 |
| 只出现一次的两个数字 | 全部异或后只剩两个目标的异或;mixed & -mixed 取最低位的 1,两个目标在这一位必不同 |
07 · 两个单次数字 |
| 不用加减乘除做加法 | 异或是不进位的和,& 左移一位是进位;重复到没有进位 |
07 · 二进制加法 |
| 顺时针打印矩阵 | 按上、右、下、左的顺序走,输出一条边就收缩一条。写下边和左边前复查剩余边界。 | 07 · 螺旋矩阵 |
| atoi | 跳过 ASCII 空格,读可选正负号,连续读 0–9,遇其他字符停止扫描,再把结果限制到有符号 32 位范围。 |
08 · atoi |
| 最长无重复子串 | 只有上次出现的位置还在窗口内,才把左边界推到其后一格。 | 08 · 无重复子串 |
| 字符流第一个不重复 | 计数负责判断重复,队列负责保留先后;队首重复了就淘汰 | 08 · 字符流 |
| KMP 失配 | 文本当前位置不回退;按前缀表缩短已经匹配的模式长度。 | 08 · 前缀表 |
🧯 三、⭐ 写错了长什么样:症状 → 它到底在说什么
先找最相似的现象。每条给一个优先检查的位置,同一个症状也可能有其他原因。 ⚠️ 这类题最难的地方是多数错误不报异常,只是答案不对 —— 所以下面前半截是「症状」,后半截才是异常。
链表反转后只剩一两个节点,或者结果里出现 None
⭐ 先写了 cur.next = prev,再回头去找原来的 cur.next。 那时后路已经被覆盖,尚未处理的整个后缀就再也找不到了。
→ 顺序永远是:nxt = cur.next 先保住后路 → cur.next = prev 再掉头 → 两队伍一起向前。见 01 章题 1。
合并链表时要写「第一个节点」的特殊分支,越写越乱
→ 用 dummy 假头。⭐ 让第一个节点和后面的节点一样接,省掉首节点分支。见 01 章题 2。
💀 树的路径题:答案条数对,但内容全是空列表
⭐ answer.append(path) 写成了没有 [:] 的版本。 所有答案都指向同一个还会继续变化的列表,回溯弹完之后它们一起变空。
→ 保存当前路径的副本,例如 answer.append(path[:])。见 02 章题 3。
树的路径题:右子树的答案里混进了左边的节点
离开一个节点时没有 path.pop()。同一个 path 被左右子树共用,不复原现场,右子树会带着一段不属于它的旧路径继续走。见 02 章题 3。
滑动窗口最大值:窗口滑出去了,答案还是旧的那个最大值
⭐ 队列里存的是值而不是下标。 存下标不是细节 —— 只有知道下标,才判断得出队首是否已经离开窗口(queue[0] <= right - k)。见 03 章题 3。
IndexError: queue is empty(两个栈实现队列)
倒完 inbox 之后 outbox 仍然是空的 —— 队列本来就没有元素。⭐ 注意倒的时机:只有 outbox 空了才整批倒,中途倒会把顺序搅乱。见 03 章题 1。
二分:数组里没有目标时结果不对,或者目标比所有元素都大时越界
⭐ 右边界写成了 len(nums) - 1。 lower_bound 用的是半开区间 [left, right),right = len(nums) 才表达得出「目标比所有元素都大」时的插入位置,也让空数组和边界判断统一。见 04 章题 1。
ValueError: k out of range(最小的 k 个数)
k 不在 0 <= k <= len(nums) 里。⚠️ 这是故意加的边界检查,不是 bug —— 面试里被追问边界时,它就是你的答案。见 04 章题 3。
最大子数组和:把相隔的片段接到了一起
⭐ 只记全局最大和,丢掉了「以当前点结尾」的那个状态。 下一轮需要知道前缀能不能接上,而全局最大和可能结束在很早的位置,不能直接接。见 05 章题 1。
递归的正则匹配跑得非常慢
同一批子问题被反复算。⭐ 看见「很多子问题重复算」先考虑记忆化,它就是从递归过渡到动态规划的桥。见 05 章题 3。
矩阵路径:某条真实存在的路径找不到
⭐ 走完一个分支后没把 board[r][c] 恢复回去。 这个格子只是当前分支不能再用;别的起点或兄弟分支仍然应该可以用它。见 06 章题 1。
排列结果里有重复项
一个前缀的同一位置试了两个值相同的字符。给每次递归调用独立的 used,让同一前缀下的相同候选只试一次。见 06 章题 3。
螺旋打印:单行或单列的矩阵,某些元素被打印了两次
⭐ 走下边和左边之前少了那两次边界判断。 只有一行时上边已经把元素拿完了,只有一列时右边已经拿完了。见 07 章题 3。
二进制加法在负数上死循环 / 结果离谱
add_without_plus 的原例用于非负整数。Python 的负数位运算按无限符号扩展理解,直接套循环时进位可能一直左移。若题目要求定宽加法,先约定位宽和有符号解释,再据此选掩码。见 07 章题 2。
⭐ 反面在 NumPy · 08 整数 dtype 的真相:已有定宽整数数组的加法可以静默回绕;标量运算和类型转换要分开判断。
atoi:'words and 9' 返回了 9
开头既无可跳过的空格,也没有可读的数字或符号,读到的连续数字数目为 0。函数返回 0。见 08 章题 1。
最长无重复子串:abba 的答案算成了 3
处理第二个 b 后,左边界到了下标 2。最后一个 a 上次在下标 0,已离开窗口。若把左边界错误地退到 1,就会把 bba 算进去;正确长度是 2。先检查 last_seen[char] >= left。见 08 章题 2。
📦 四、这套题用到的标准库,一张表
按需求查常用库,再回正文看它处理的是哪一段工作。
| 用到的 | 干什么 | 出现在 |
|---|---|---|
collections.deque |
两端添加和删除用于层序队列、滑动窗口候选、字符流顺序。 | 02 · 层序 · 03 · 窗口 · 08 · 字符流 |
collections.Counter |
计数,用来判断「重复了没有」 | 08 · 字符流 |
heapq.nsmallest |
只要前 k 个最小元素,不必全排 | 04 · 最小的 k 个数 |
functools.lru_cache |
记忆化,缓存按下标划分的匹配子问题。 | 05 · 正则匹配 |
手写最小的 k 个数时,可用大小为 k 的最大堆保留候选。
需要频繁操作两端时可选 deque。列表在头部插入会搬动已有元素,细节见 Python 会咬你的地方 · 09 容器、哈希与顺序。
🧪 五、每题的小闭环,和「做完了」的标准
选一行能暴露当前问题的输入。先写预期,再去正文改一组输入核对。完整练习方法见 00 章。
| 类别 | 先试什么 | 去哪核对 |
|---|---|---|
| 链表 | 空链返回 None;区分单节点无环与自环。 | 01 · 反转、环入口 |
| 树 | 空树高度 0;斜树核栈深。最近公共祖先示例要求两个目标都在树里。 | 02 · 深度、公共祖先 |
| 栈与窗口 | 空队列取值要报错;固定长度窗口先核 1 ≤ k ≤ len(nums)。k 等于长度时只有一个窗口。 | 03 · 两栈队列、窗口 |
| 二分与堆 | 插入位置可等于数组长度;旋转数组空输入报错;最小 k 个数接受 k = 0。 | 04 · 插入边界、旋转数组、最小 k 个数 |
| 动态规划 | 跳到第 0 阶有 1 种空走法。全负数组仍需选非空子数组。 | 05 · 跳台阶、子数组 |
| 回溯与可达 | 单格不能用两次。原拼字代码要求非空矩形与不含占位符的目标。阈值为 0 的正尺寸机器人网格只到起点。 | 06 · 拼字、可达范围 |
| 位运算与模拟 | 先核负数位宽。螺旋矩阵试单行和单列。 | 07 · 位宽、矩阵边界 |
| 字符串 | 空串的最长无重复子串长 0;空模式的 KMP 返回 0。atoi 先核 ASCII 空格与数字的约定。 | 08 · 窗口、KMP、atoi |
🔗 这一页连到哪里
| 相关的地方 | 为什么 |
|---|---|
| 00 · 怎么刷代码题 | 先选学习顺序,再看完整的一题练习流程。 |
| Python 会咬你的地方 · 00 | 主线可运行示例使用 Python。对象共享与默认参数的细节见这套教程。 |
| Python 会咬你的地方 · 09 · 容器、哈希与顺序 | 查常见容器的复杂度,以及哪些操作提供顺序保证。 |
| 机器学习与深度学习基础 · 附录C · 手撕代码速查 | 相关的白板练习包括用 NumPy 写多头注意力。 |
| 不靠数据的 AI · 05 · 状态空间与搜索框架 | 从待展开集合的取出规则比较搜索。深度限制、重新启动、路径代价和启发式属于各算法自己的条件。 |
| 不靠数据的 AI · 14 · 回溯与约束传播 | 同一个回溯骨架往上加两件本板块没有的东西:前向检查、弧相容 |
| 强化学习基础 · 04 · 动态规划 | 这里的状态随题意定义。强化学习一章用已知的转移概率和奖励更新状态价值。 |
| NumPy 与向量化思维 · 08 · 整数 dtype 的真相 | 查固定宽度数组中的加法回绕,以及它与标量转换的区别。 |
速查链接依据正文示例与输入约定整理。各条与题库考点的直接对应待审核。
下一节 👉 回到板块索引