代码模板手册：C++

要点

1. 写指针 w 左边是已经确定保留的结果；读指针只往前扫，两个指针都只走一遍。
2. 判断能不能保留时和 nums[w-k] 比，也就是和「结果」比，而不是和上一个读到的原始元素比。
3. 原地合并两个有序数组时从尾部往前写，就不会覆盖还没读到的数据。

易错点

• 题目要的是新长度，判题只看前 k 个位置；返回数组本身或者去比较 k 之后的内容都会出错。
• 边遍历边删除（Python 的 list.remove、Java 的 ArrayList.remove）是 O(n²)，还会跳过元素。
• 排序比较器写成 a - b，值接近 ±2^31 时会溢出；用 Integer.compare 或直接比较大小。

要点

1. 先查补数、再存自己：一遍扫描就能找到「之前出现过」的配对，也不会把同一个元素用两次。
2. 存什么取决于问什么：要位置就存下标，要个数就存次数，要最早出现的位置就只在第一次出现时存。
3. 键可以组合出来：排序后的字符串、计数元组、(行, 值) 对，都能把「同一类」放进同一个桶。

易错点

• 先插入再查询，target 恰好等于 2x 时会把同一个元素和自己配成一对。
• C++ 的 map[key] 读一个不存在的键会插入默认值；只想判断存在时用 find 或 count。
• Java 里两个 Integer 用 == 比较，超过 127 时可能不相等；用 equals 或先拆箱成 int。

要点

1. pi[i] 是 pat[0..i] 中「既是真前缀又是真后缀」的最长长度；失配时 j 退回 pi[j-1]，文本指针从不回头。
2. 建 pi 表和在文本里匹配是同一段循环：建表就是模式串和自己匹配。
3. 解析类题目用一个下标手动往前读数字、符号和括号，边界比 split 好处理。

易错点

• 匹配成功后要令 j = pi[j-1] 继续，否则会漏掉重叠出现（"aaaa" 里的 "aa" 出现 3 次）。
• 在循环里用 + 拼字符串是 O(n²)；Python 先收集到列表再 join，Java 用 StringBuilder。
• Go 里 s[i] 是字节、len(s) 是字节数；处理中文等多字节字符要先转成 []rune。

要点

1. 右端每步前进一格，左端只在窗口不合法时收缩；两个指针都只前进，总共 O(n)。
2. 求最长窗口：收缩完再更新答案；求最短窗口：在「仍然合法」的收缩循环里更新答案。
3. 有序数组上求两数之和、去重、反转用相向双指针；判环、找中点用快慢指针。

易错点

• 收缩时忘了把移出窗口的元素计数减一，窗口状态就和实际内容对不上。
• 数组里有负数时，「和超过 k 就收缩」不再单调，滑动窗口失效，要改用前缀和。
• 「恰好 k 个」很难直接滑，用「至多 k 个」减去「至多 k-1 个」。

要点

1. 区间和等于两个前缀和之差：sum(l..r) = pre[r+1] - pre[l]；前缀数组多开一位，pre[0] = 0。
2. 统计「和为 k 的子数组」时，哈希表先放 {0: 1}，代表从下标 0 开始的子数组。
3. 多次区间加值用差分数组：diff[l] += v，diff[r+1] -= v，最后求一遍前缀和；合并区间先按左端点排序。

易错点

• 忘了放 {0: 1}，会漏掉所有从下标 0 开始的子数组。
• 前缀和很容易超过 32 位整数，C++ 用 long long，Java 用 long。
• 先把当前前缀和存进表再查询，k = 0 时会把空子数组也算进去。

要点

1. 先把问题改写成单调的判定 ok(x)：前面全是假、后面全是真，然后二分找第一个真。
2. 区间 [lo, hi) 左闭右开：ok(mid) 时 hi = mid，否则 lo = mid + 1；循环条件 lo < hi，结束时 lo 就是答案。
3. 答案范围已知、给定一个答案能 O(n) 验证时，直接对答案二分：最小速度、最大化最小值都是这一类。

易错点

• lo = mid 配合向下取整的 mid 会死循环；用这个模板时只写 lo = mid + 1。
• (lo + hi) / 2 在 C++、Java、Go 里可能溢出，写成 lo + (hi - lo) / 2。
• hi 本身不会被检查：上界要取到一定可行的值，否则返回的 hi 会被误当成答案。

要点

1. 栈里存下标而不是值：既能取到值，也能算距离（比如「还要等几天才升温」）。
2. 每个元素只进栈、出栈各一次，所以虽然套了 while，总复杂度仍是 O(n)。
3. 求前 k 大用大小为 k 的小根堆；滑动窗口最值用单调双端队列，队头过期就弹出。

易错点

• 有重复值时 < 和 <= 结果不同，先想清楚要「严格更大」还是「大于等于」。
• Python 的 heapq 只有小根堆，要大根堆就存相反数。
• Java 的 Stack 类又慢又是同步的，栈和队列都用 ArrayDeque；比较器不要写成 a - b。

要点

1. 总是选结束最早的区间，给后面留的空间最多。交换论证：任何最优解的第一个区间都能换成它而不变差。
2. 最少删除数 = 总数 - 最多保留数；「最少几支箭」也是同一个循环，只是端点相接也算重叠。
3. 写贪心之前先说清楚「为什么局部最优不吃亏」；说不清楚时，多半要换成动态规划。

易错点

• 按开始时间排序再贪心，会被一个开始很早、持续很长的区间卡住。
• 端点相接算不算重叠由题意决定：>= 和 > 只差一个字符，答案就不一样。
• 比较器写成 a[1] - b[1]，端点接近 ±2^31 时会溢出。

要点

1. 改指针之前先存下 next。反转只有三步：存 next、指回前驱、整体前移。
2. 头结点可能被删除或替换时，先建一个哑结点 dummy 指向 head，最后返回 dummy.next。
3. 快指针一次两步、慢指针一次一步，用来找中点和判环；找倒数第 k 个结点则让前指针先走 k 步，再和后指针同速前进。

易错点

• 先改了 head.next 再去取 next，后面的链表就丢了。
• 访问 fast.next.next 之前要确认 fast 和 fast.next 都不为空。
• 把链表拆成两段后忘了把前半段的尾部置空，合并或遍历时会成环。

要点

1. 每一轮先记下队列长度，正好处理这么多个结点，层与层就分开了。
2. 写递归 DFS 前先想清楚「子树返回什么」：深度、是否平衡、结点数，都是把左右两边的结果合并。
3. 前序、中序、后序的区别只在于「处理当前结点」放在两次递归的前面、中间还是后面。

易错点

• 用一直在变化的队列长度当循环上界，会把下一层的结点也算进这一层。
• Python 用 list.pop(0) 当队列是 O(n) 的，要用 collections.deque。
• 树退化成链时递归深度能到 10^5，Python 会爆栈；改成迭代或调高 recursionlimit。

要点

1. 递归函数返回「从当前结点往下走的最好单边路径」，因为要继续往上接的路径只能选一边。
2. 在当前结点拐弯的路径（左 + 根 + 右）只用来更新全局答案，不返回给父结点。
3. 根到叶的路径题用「进入时加、离开时减」维护当前路径；任意起点的路径和用前缀和 + 哈希表。

易错点

• 全局答案初始化成 0，所有值都是负数的树会得到错误的 0。
• 子树贡献为负时要截成 0（这一边不接），否则会把答案拖低。
• 把拐弯路径也返回给父结点，等于让一条路径分叉，结果会偏大。

要点

1. 前序的第一个值是根；在中序里找到它，左边是左子树，右边是右子树。
2. 用哈希表存「值 → 中序下标」，每次切分 O(1)，整体 O(n)。
3. 按「先左后右」递归时，前序指针顺序往后取就是下一个根，不用计算子数组长度；后序 + 中序则从后往前取、先右后左。

易错点

• 值有重复时中序位置不唯一，这个方法就不成立了。
• 每层递归都切片复制数组（Python 切片、Java copyOfRange），会退化成 O(n²)。
• 后序 + 中序时如果仍然先建左子树，取到的根的顺序就错了。

要点

1. BST 的中序遍历是升序的：第 k 小、验证 BST、找前驱后继，都能转成中序问题。
2. 验证 BST 要把上下界 (lo, hi) 往下传，每个结点都必须落在祖先给出的开区间里。
3. 查找和插入只走一条路径，复杂度是 O(h)：平衡时 O(log n)，退化成链时 O(n)。

易错点

• 只拿结点和它的左右孩子比较，发现不了「右子树深处有比根还小的值」。
• 用 INT_MIN / INT_MAX 当边界，结点值恰好是极值时会误判；用 long 或空值表示「无界」。
• 迭代中序里忘了转向 node.right，会重复弹出同一批结点或者提前结束。

要点

1. 所有起点一开始就一起入队，相当于从一个虚拟的超级源点出发；BFS 的层数就是最短距离。
2. 入队时就标记已访问，同一个格子不会被重复加入。
3. 只问连通块（岛屿个数、面积）时 DFS、BFS 都可以；问最少步数必须用 BFS。

易错点

• 出队时才标记，同一个格子会被多个邻居重复入队，大网格上会超时。
• 一开始就没有新鲜橘子时答案是 0，既不是 -1，也不是层数。
• 递归 DFS 在 1000×1000 的网格上会爆栈；大网格用 BFS 或显式栈。

要点

1. find 时做路径压缩，union 时把小树挂到大树下；两者一起用，单次操作几乎是常数时间。
2. union 返回 false 说明两点本来就连通：无向图判环、找冗余连接都靠它。
3. 连通块个数、块的大小这类信息只记在根上，合并时累加。

易错点

• 用 parent[a] == parent[b] 判断连通是错的，必须比较 find(a) == find(b)。
• 合并时写成 parent[a] = b，而不是把两个根连起来，会破坏树的结构。
• 结点是字符串或坐标时，先映射成 0..n-1 的编号，或者用哈希表存 parent。

要点

1. 入度为 0 的点没有未完成的前置依赖，可以先放；放下之后把它指向的点入度减一。
2. 输出的点数少于 n，说明剩下的点都在环上：「能不能修完所有课」就是这样判断的。
3. 要求字典序最小的拓扑序时，把队列换成小根堆。

易错点

• 边的方向读反（「a 依赖 b」应该建 b → a），整个顺序就倒过来了。
• 只把一开始入度为 0 的点入队，后面减到 0 的点忘了入队。
• DFS 写拓扑排序时只有「访问过 / 没访问」两种状态是判不出环的，还需要「访问中」这第三种状态。

要点

1. 每次从堆里取出当前距离最小的点，它的距离就确定了；前提是所有边权非负。
2. 不做 decrease-key：直接把新距离压进堆，弹出时发现比 dist 大就跳过（懒删除）。
3. 边权只有 0 和 1 时用双端队列 BFS；有负权用 Bellman-Ford；状态里带「已用次数」时，把 (点, 次数) 当成一个新结点。

易错点

• 不跳过过期的堆元素，同一个点会被反复松弛，稠密图上会超时。
• 距离累加超出 32 位整数；用 INT_MAX 当无穷大时，d + w 还会溢出成负数。
• 有向图当成无向图建边（或者反过来），所有距离都会错。

要点

1. 按边权从小到大看每条边：能连起两个不同连通块就选，否则跳过（选了会成环）。
2. 选够 n-1 条边就是一棵生成树；最后不够 n-1 条，说明图不连通。
3. 点少边多的稠密图（比如坐标点两两相连）用 O(n²) 的 Prim，往往比给所有边排序更快。

易错点

• 没检查是否连通，直接返回累加的边权。
• 坐标点两两连边有 n²/2 条，内存和排序时间都可能超限。
• 点的编号从 1 开始，并查集却只开了 n 个位置。

要点

1. 模板只有三步：做选择、递归、撤销选择；path 是整个搜索共用的一份。
2. 先排序，再用 i > start && nums[i] == nums[i-1] 跳过：同一层不重复选相同的值，更深的层可以。
3. 组合从 start 往后选，避免 {1,2} 和 {2,1} 同时出现；排列每次从头选，用 used 数组标记。

易错点

• 结果里直接存 path 的引用，回溯结束后所有结果都变成同一个空列表。
• 把 i > start 写成 i > 0，更深层里合法的重复值也会被跳过。
• 忘了先排序，相同的值不相邻，去重判断就失效了。

要点

1. 回溯的每一层决定「下一段切到哪里」，start 走到 n 就得到一种完整的切法。
2. 先用 O(n²) 的区间 DP 算出每个子串是不是回文，回溯里的判断就是 O(1)。
3. 复原 IP 地址、单词拆分也是同一个框架，只是「这一段是否合法」的判断不同。

易错点

• 在回溯里每次都重新用双指针判断回文，重复计算会让常数大很多。
• 只要求方案数或最少切几刀时，不要枚举，改用 DP。
• 子串下标是左闭右开还是左闭右闭要统一；s[start:end+1] 和 substring(start, end+1) 很容易差一位。

要点

1. 每行只放一个皇后，搜索树只在列上分叉；列、主对角线 r-c、副对角线 r+c 各用一个数组标记。
2. 剪枝越早越好：递归之前就判断冲突，而不是放满整个棋盘再检查。
3. 数独、组合总和这类题先排序，在「剩下的值已经不可能满足」时用 break，比 continue 省得多。

易错点

• 主对角线下标 r-c 会是负数，要加上 n-1 的偏移。
• 回溯返回前忘了把标记改回去，后面的分支全被误剪。
• 需要输出棋盘时，用可变的字符数组逐格修改，最后再转字符串，不要每一步都复制整盘。

要点

1. 先用一句话定义状态，比如 dp[i] = 只看前 i 个元素时的最优值；状态说清楚了，转移通常就出来了。
2. 转移只看「最后一步做了什么」：第 i 个选还是不选，最后一跳是 1 步还是 2 步。
3. dp[i] 只依赖前一两项时，用两个变量滚动，空间从 O(n) 降到 O(1)。

易错点

• dp 和输入的下标错位：dp 多开一位时 dp[0] 表示「什么都没选」，答案在 dp[n]。
• 滚动更新时先覆盖了 prev1 再拿它算新值，用到的已经是新数据了。
• 方案数很快会超出 64 位；题目要求取模时，每一步都要取模。

要点

1. dp[r][c] 只依赖上方和左方，按行从左到右填，一行数组就够：更新前 dp[c] 是上方，dp[c-1] 是左方。
2. 第一行、第一列只有一个来源，要么单独处理，要么用无穷大哨兵统一写法。
3. 路径计数就把 min 换成加法；有障碍的格子直接置 0。

易错点

• 哨兵用 INT_MAX 再加上格子值会溢出，要保证只在有限值上做加法。
• 允许往四个方向走时没有填表顺序，DP 不成立，要用 BFS 或 Dijkstra。
• 压成一行之后，如果转移还需要左上角的值，要在它被覆盖前先存到变量里。

要点

1. 0/1 背包倒序遍历容量，保证 dp[s-x] 还是「没用过 x」的旧值；完全背包正序遍历，允许同一件物品重复使用。
2. 物品在外层、容量在内层，数的是组合（不计顺序）；容量在外层、物品在内层，数的是排列。
3. 很多题要先转化成背包：「分成两个和相等的子集」= 能否凑出 sum/2；「目标和」= 凑出 (sum+target)/2。

易错点

• 0/1 背包写成正序，同一件物品会被用很多次。
• 计数问题 dp[0] = 1（什么都不选也是一种方案）；求最值问题 dp[0] = 0，其余初始化为无穷。
• 转化成 (sum+target)/2 之前没检查奇偶性和正负，会得到错误的下标。

要点

1. tails[k] 是长度为 k+1 的递增子序列可能的最小结尾；它本身是递增的，所以可以二分。
2. 严格递增用 lower_bound（第一个 ≥ x），非递减用 upper_bound（第一个 > x）。
3. 二维的「信封嵌套」先按宽升序、宽相同时按高降序排序，再对高做 LIS。

易错点

• tails 数组不是真实存在的最长子序列，只有长度是对的；要输出方案得另外记录前驱。
• 严格和非严格用错了二分函数，重复元素多的用例会差 1 甚至更多。
• 要求「最长子序列有几个」时，O(n log n) 写法不够，要回到 O(n²) 的 dp 加计数数组。

要点

1. dp[i][j] 定义在前缀上：a 的前 i 个字符和 b 的前 j 个字符；多开一行一列表示空串。
2. 末尾字符相等就继承 dp[i-1][j-1]；不相等时，替换、删除、插入分别对应左上、上、左三个格子。
3. 最长公共子序列、不同的子序列、通配符匹配都是这张表，只是转移不同。

易错点

• dp 的下标是前缀长度，对应的字符是 a[i-1]；写成 a[i] 会错一位。
• 忘了初始化第 0 行和第 0 列（变成空串需要删 i 次，从空串变来需要插 j 次）。
• 压成一行时，左上角的值会被本行覆盖，需要额外一个变量保存。

要点

1. dp[i][j] 只依赖更短的区间 dp[i+1][*] 和 dp[*][j-1]，所以 i 倒序、j 正序填表。
2. 两端字符相等就向内收缩并加 2，否则去掉一端，取两种情况的较大值。
3. 只问回文子串（必须连续）时，中心扩展法 O(n²) 时间、O(1) 空间，更简单。

易错点

• i 正序枚举时 dp[i+1][*] 还没有算出来，结果全错。
• 子序列（可以不连续）和子串（必须连续）是两道题，转移不能混用。
• 中心扩展要同时试奇数中心 (i, i) 和偶数中心 (i, i+1)。

要点

1. 状态定义成「以 i 结尾」，连续子数组的转移就只有两种：接在前一段后面，或者从 i 重新开始。
2. 乘法遇到负数时最大会变成最小，所以要同时维护最大和最小两个状态。
3. 状态机 DP 就是给每个位置多设几个状态（持有 / 不持有、上一个选没选），把状态之间的每条转移都写出来。

易错点

• 先更新了 hi 再用新的 hi 去算 lo，用到的是同一轮已经改过的值。
• 答案初始化成 0，全是负数的数组就会出错。
• 最大子数组和（Kadane）的转移是 cur = max(x, cur + x)，不要漏掉「重新开始」这一项。

要点

1. 先写清楚每天结束时可能处于哪几种状态，再写「昨天的哪种状态 + 今天的什么动作」能到达它。
2. 同一天的几个新值都要用前一天的旧值计算，所以要同时赋值或者先存临时变量。
3. 最多 k 次交易就加一维 k；手续费在每次卖出（或买入）时扣一次；只交易一次就是「记录历史最低价」。

易错点

• 持有状态初始化成 0，相当于第 0 天白送了一股。
• 用负无穷做初值时，C++ / Java 里 hold + p 会溢出；取 MIN / 2 这样的值。
• 有冷却期时，买入只能从「空仓」状态转过来，不能从「刚卖出」状态直接买。

要点

1. 按结束时间排序后，dp[i] = 前 i 个任务的最优值；第 i 个任务要么不选，要么接在最后一个不冲突的任务后面。
2. 「最后一个不冲突的任务」在结束时间数组里二分查找，整体 O(n log n)。
3. 「把数组分成 k 段」这类题，状态通常是 dp[段数][结尾位置]，转移时枚举最后一段从哪里开始。

易错点

• 首尾相接算不算冲突，决定了用 upper_bound 还是 lower_bound。
• 按开始时间排序、每次贪心选利润最高的，在带权的版本里不成立。
• 排序时只排了结束时间，开始时间和利润没有跟着一起动。

要点

1. 树形 DP 用后序遍历：先拿到左右子树的结果，再算当前结点，每个结点返回一个小元组。
2. 按「当前结点选不选」拆状态，比在父结点里往下看两层更简单，也不会重复计算。
3. 两人博弈题常用「当前先手比对手多拿多少」作为状态：dp[i][j] = max(nums[i] - dp[i+1][j], nums[j] - dp[i][j-1])。

易错点

• 不返回元组，而是用「祖父 + 孙子」的写法又不做记忆化，会指数级重复计算。
• 不选当前结点时，孩子也不一定要选，每个孩子都要取 max(选, 不选)。
• 博弈题如果按「我的得分」建状态，往往还得再记对手的得分；用差值更省事。

要点

1. 把「跳过空行、走到下一个有效元素」放进 hasNext，next 只负责取值；这样连续调用多次 hasNext 也没有副作用。
2. 只保存位置（行号、列号），不要在构造函数里把所有元素复制成一个大数组。
3. 任意深度的嵌套列表用一个栈保存各层的位置；Python 里用生成器 yield from 最自然。

易错点

• 中间或末尾有空行时，hasNext 只看下一行就会返回错误的 true。
• next 里不先调用 hasNext，直接取值会越界。
• 迭代过程中修改了原容器：Java 会抛 ConcurrentModificationException，其他语言则是悄悄出错。

要点

1. 哈希表负责 O(1) 找到结点，双向链表负责 O(1) 把结点移到头部、删除尾部。
2. get 也算一次「使用」，要把结点移到最新的一端；put 一个已存在的键要更新值并移动，而不是再插一份。
3. 面试要求手写链表时，用头尾两个哨兵结点，插入删除就不用判断空指针。

易错点

• 淘汰尾结点时只删了链表、没删哈希表里的键（或者反过来）。
• 先插入再淘汰还是先淘汰再插入要统一，并想清楚容量为 0 这种边界。
• 链表结点里不存 key，淘汰时就不知道该删哈希表里的哪一项。

要点

1. 每个结点代表一个前缀；插入和查询都是顺着字符往下走，耗时只和单词长度有关。
2. 结点上存计数（有多少单词经过、有多少单词在此结束），前缀计数和删除都能 O(L) 完成。
3. 序列化二叉树用前序遍历加空结点标记（如 "#"），反序列化时按同样的顺序递归读回来。

易错点

• 把 search（完整单词）和 startsWith（前缀）混为一谈，忘了检查结束标记。
• 固定 26 叉数组默认只有小写字母；有大写、数字或 Unicode 时，孩子改用哈希表存。
• 序列化时值之间不加分隔符，多位数和负数就没法还原。

要点

1. x & (x-1) 去掉最低位的 1，x & -x 取出最低位的 1；异或满足 a ^ a = 0，可以找出只出现一次的数。
2. 快速幂把指数按二进制拆开：每轮把底数平方，指数这一位是 1 就乘进结果，O(log exp)。
3. 不超过 20 个元素的集合可以用一个整数当掩码，for (s = mask; s; s = (s-1) & mask) 枚举它的所有非空子集。

易错点

• 两个 10^9 量级的数相乘会超出 32 位，取模乘法之前先转成 long / long long。
• Java 的 >> 会保留符号位，处理负数用无符号右移 >>>；Python 整数无限长，负数要先 & 0xFFFFFFFF。
• C++ 里位运算优先级低于比较：x & 1 == 0 实际是 x & (1 == 0)，一定要加括号（Java 会直接编译报错）。