1. 第5期刷题手记这个系列到底在记录什么牛客上的刷题记录写到了第5期我越来越觉得这个系列的真正价值不是存档题号而是把每次卡壳的过程留下来。前4期我都在记今天过了几题、错的什么知识点等翻回去看的时候发现同类错误反复犯光有数量没有沉淀。所以第5期开始改走复盘路线每道卡过的题都记录思考链路、边界坑和模板要点这篇就当这一期的汇总整理。1.1 从数量优先到模板沉淀的转变第5期之前我的习惯是每天硬刷6到8道以为刷得多就能产生肌肉记忆。结果很快被打脸一道动态规划题我换了个背景写居然连续四遍出现不同的错法。这说明我根本没有把解法转成自己的东西只是在机械地对照题解把代码抄完再标记一个已AC。第5期我把节奏改成每天3道但要求每道题都写复盘笔记。复盘笔记必须回答三句话这题在考什么我卡在哪一步下次遇到同类题怎么避免。一开始觉得这很费时间一道题加笔记要花一个多小时但后期效果非常明显。后面我做新题时脑子里的第一个反应不是急着写代码而是先把题型归类比如这是带约束的最优化问题大概率上动态规划或者这是字符串子串连续性问题双指针窗口优先。这种识别能力是靠数量堆不出来的。1.2 这一期圈定的三个训练重点我统计了一下前4期的错题记录错误率最高且笔试高频的集中在三类动态规划状态定义不清晰、转移方向搞反、一维滚动数组遍历顺序错。滑动窗口与双指针窗口收缩时机不对、固定长度与可变长度混用。二叉树递归返回值设计语义混乱经常把局部答案和向上层报告的信息搞混。这三类在牛客笔试里几乎每个公司都会换着考而且特别喜欢把两个考点揉在一起比如大根堆滑动窗口前缀树递归剪枝。所以第5期的主线就是集中火力收拾这三块顺带把笔试环境下的输入输出处理、复杂度估算、边界用例检查这些隐性得分点一起补上。2. 动态规划复盘状态定义错了后面全是白做动态规划是真正让我体会过看题解觉得简单自己写就翻车的题型。第5期我把常见状态定义方式重新梳理了一遍发现大部分错误不是转移方程不会而是第一步就错了——状态定义不够准确导致后面每一步都在将就。2.1 最长有效括号栈解法之外为什么要写DP给定一个只包含 ( 和 ) 的字符串要求返回最长的有效括号子串长度。比如 )()()) 的答案是 4。这道题一般第一反应是栈确实能用 O(n) 做出来。但我坚持写了几遍 DP 版本原因在于很多括号类变体题在栈解法上没法直接扩展但 DP 的状态迁移逻辑是通用的。我使用的状态定义是dp[i] 表示以 i 结尾的最长有效括号子串长度。为什么用以 i 结尾而不是前 i 个字符因为子串要求连续以某个位置结尾的状态可以精确描述从哪个位置到 i 连续合法方便做区间拼接。转移分两种情况如果 s[i] 是 (dp[i] 一定是 0这很好理解合法括号串不可能以左括号结尾。如果 s[i] 是 )看 s[i-1]s[i-1] 是 (那么直接配对dp[i] (i 2 ? dp[i-2] : 0) 2。s[i-1] 是 )说明这里可能是一串已合法括号的尾部。设 j i - dp[i-1] - 1如果 j 0 且 s[j] (那么当前 ) 可以和 s[j] 配对把 dp[i-1] 那段合法串包起来再尝试接上更前面的合法串。代码写出来长这样def longest_valid_parentheses(s: str) - int: n len(s) dp [0] * n ans 0 for i in range(1, n): if s[i] ): if s[i - 1] (: dp[i] (dp[i - 2] if i 2 else 0) 2 else: j i - dp[i - 1] - 1 if j 0 and s[j] (: dp[i] dp[i - 1] 2 if j - 1 0: dp[i] dp[j - 1] ans max(ans, dp[i]) return ans这里最容易错的地方是第二种情况的最后一步很多人算完dp[i-1] 2就收工了忘了再拼上 dp[j-1]。比如 ()(()) 这个用例最后一个 ) 的正确结果应该是整个串长度 6如果你不加上 dp[j-1]就会算出 4。我就是在这个地方连续错了两次才把整个转移逻辑刻进脑子里。2.2 打家劫舍系列两个滚动变量背后的决策表打家劫舍这题标准做法是 dp[i] max(dp[i-1], dp[i-2] nums[i])含义是偷到前 i 个房间时的最大金额。我一开始不太理解为什么可以只用前一个和前两个两种状态后来自己画决策表才算真正想通第 i 个房间只有偷或不偷两种选择不偷就是继承 dp[i-1]偷了就只能在 dp[i-2] 基础上加上当前房间的价值。牛客笔试里这题通常不会直接给数组而是套一个场景比如环形小区、树上房间。环形的处理方式我这次记下来了把数组拆成 [0, n-2] 和 [1, n-1] 两个区间分别跑一遍取大的。原因是首尾不能同时偷那就把一定要偷首和一定不偷首两种情况拆开。空间优化版本也很值得写一遍def rob(nums): prev, cur 0, 0 for x in nums: prev, cur cur, max(cur, prev x) return cur这里的 prev 和 cur 对应的是 dp[i-2] 和 dp[i-1]。每次迭代后cur 变成新的 dp[i]旧的 cur 退化成 dp[i-1] 给下一轮当 prev 用。很多教程直接丢出这段代码但不解释变量含义导致读者只会抄不会改。实际上理解了这两个变量的语义环形版本和树形版本你都能自己推出来。2.3 背包变体一维滚动数组为什么必须逆序遍历0-1 背包的二维转移是 dp[i][c] max(dp[i-1][c], dp[i-1][c-w] v)。优化成一维数组后很多新手包括我自己一开始都写成这样def wrong_zero_one(items, capacity): dp [0] * (capacity 1) for w, v in items: for c in range(w, capacity 1): dp[c] max(dp[c], dp[c - w] v) # 错正序是错误的 return dp[capacity]这个写法的问题在于当 c 从小到大遍历时dp[c-w] 可能已经在当前物品的处理轮次中被更新过也就是说同一件物品被反复使用了这等价于完全背包。第5期我在刷等和子集这道题时就被这个坑坑到了——判断数组能不能分成两个和相等的子集用错序版本跑出来几乎所有用例都是 True因为每个数都被重复用了无限次。正确写法是容量倒序遍历def zero_one_knapsack(items, capacity): dp [0] * (capacity 1) for w, v in items: for c in range(capacity, w - 1, -1): dp[c] max(dp[c], dp[c - w] v) return dp[capacity]理解逆序的关键是一维数组在每一轮外层循环里必须让当前位置更新时用到的 dp[c-w] 还是上一轮物品的旧值。倒序保证了我们在计算大容量时小容量还没被当前物品污染。这个经验我整理成了一个通用判断0-1 背包逆序完全背包正序其余变体在这个基础上改。我把第5期集中练的 DP 题整理成了一张简化对照表题目类型常用状态定义一维优化时的遍历方向关键易错点最长有效括号dp[i]以 i 结尾的最长合法长度无需优化漏接更前面一段合法串打家劫舍dp[i]前 i 个房间的最大收益滚动变量自左向右环形拆区间没有分首尾0-1 背包 / 等和子集dp[c]容量 c 下的最大价值容量倒序正序会变成完全背包完全背包dp[c]容量 c 下的最大价值容量正序和 0-1 背包混淆这张表不是什么万能解法但它让我做题前先问自己一句这题是件数受限的还是不限的一下子就能少走一半弯路。3. 滑动窗口与双指针边界条件才是真正的考场滑动窗口和双指针是牛客笔试里被包装得最花哨的一类题。表面上看代码量不大实际上每一个while的收缩条件都是送分题和送命题的分界线。3.1 最小覆盖子串窗口收缩的判断时机题目是给两个字符串 s 和 t要求返回 s 中包含 t 所有字符的最短子串。这类题的通用模板是右指针不断扩展窗口直到窗口已经覆盖 t 的所有字符然后左指针开始收缩收缩过程中一旦发现窗口不再覆盖就停止收缩继续让右指针前进。我用一个缺失计数器missing来维护覆盖状态。初始化missing len(t)当窗口里加入了还缺的字符时 missing 减 1收缩时反向操作。核心代码如下from collections import Counter def min_window(s: str, t: str) - str: if not t or not s: return need Counter(t) missing len(t) left 0 res for right, ch in enumerate(s): if need[ch] 0: missing - 1 need[ch] - 1 while missing 0: if not res or right - left 1 len(res): res s[left:right 1] left_ch s[left] need[left_ch] 1 if need[left_ch] 0: missing 1 left 1 return res这个模板最容易被忽略的细节是need计数器会变成负数。比如 s 里出现了很多次某个 t 中不存在的字符时need[ch]会一路减到负值。收缩时need[left_ch] 1只有当它从 0 变到 1 的时候才说明这个字符从有变成了缺此时 missing 才需要加 1。如果你简单地在收缩时让 missing 无条件加 1结果会完全错乱。我在第5期至少犯了三次这个错最后总结出一条口诀扩展时缺了就减收缩时补到正才加。凡是涉及到哈希计数和滑动窗口结合的题这个口诀能直接套。3.2 快慢指针与环形链表步长和入口判断的坑快慢指针的标准操作是 slow 每次走 1 步fast 每次走 2 步。如果链表中存在环它们必定会在环内相遇。判断环入口的经典做法是从 head 出发和从相遇点出发的两个指针同步走再次相遇的位置就是入口。原理不复杂从 head 到入口的距离等于相遇点到入口的距离加上若干个环长。真正容易出错的是边界条件链表为空或只有一个节点时fast或fast.next会为 None必须先判空。步长不能随便改成 fast 走 3 步走 4 步。步长一变相遇点分析、入口推导全变别为了一点常数性能去冒这个险。有些变体题把链表换成数组比如给定长度为 n1 的数组、元素范围在 1 到 n 之间、找重复的那个数。这时候指针的定义从next变成了nums[nums[i]]这种索引跳转非常容易把下表和值的关系弄混。我这次复盘时特意把环形链表入口检查的代码写成了关键路径备忘def detect_cycle(head): slow fast head while fast and fast.next: slow slow.next fast fast.next.next if slow fast: p head while p ! slow: p p.next slow slow.next return p return None这个 while 循环的写法建议直接背下来因为它的节拍几乎正好避开了空指针和单节点两种边界。3.3 窗口类题目的变体固定长度窗口与单调队列第3.1说可变长度窗口还有一种高频变体是固定长度窗口。比如滑动窗口最大值给定数组和窗口长度 k求每个窗口里的最大值。朴素解法每步都重新扫一遍窗口复杂度 O(nk)数据规模稍微一大就超时。正确做法是单调队列。队列里存的是数组下标而不是值这样才可以判断队头元素是否已经滑出窗口。维护原则只有一句话新元素入队前把队尾所有比它小的值全部弹出。这样队头永远是当前窗口最大值的下标。from collections import deque def max_sliding_window(nums, k): q deque() res [] for i, x in enumerate(nums): while q and nums[q[-1]] x: q.pop() q.append(i) if q[0] i - k: q.popleft() if i k - 1: res.append(nums[q[0]]) return res我特意把单调队列存下标而不是存值这个点标出来因为这是最容易被反过来写的。存下标有两个理由第一能精确判断过期第二当队列里有多个相同值时存下标不会把相同值的不同位置搞混。手动模拟一遍[1,3,-1,-3,5,3,6,7]你就能彻底理解为什么弹掉队尾所有更小值之后队头还是最大值。4. 二叉树递归返回信息设计不只会写前中后序遍历很多人对二叉树的掌握停留在遍历上一遇到求路径、求最大直径这类题就开始挣扎。第5期我集中刷了一波树形题目最大的突破是搞明白了返回值到底该带什么信息。4.1 自顶向下和自底向上怎么选递归处理二叉树有两种主流思路。自顶向下是指父节点先把参数传给子节点典型场景是从根到叶的路径和、判断路径总和是否存在。这类题的共同点是你不需要知道子树内部的完整信息只要从上往下带一个到目前为止的累计值就够了。自底向上则是先把左右子树的结果拿到手再在根节点汇总。典型场景是求最大路径和、判断平衡二叉树、求树的直径。这类题的共同点是答案必须由左右子树的局部结果组合而成只有递归到底再回溯才能拿到足够信息。判断用哪种我总结了一个问题如果我能从根往子的方向逐步累加出结果用自顶向下如果我无法在没有子树信息的情况下做出判断就必须自底向上。比如判断平衡二叉树只看当前节点的高度没有意义必须等到左右子树都返回高度才能算差值所以必然是自底向上。4.2 最长同值路径一次返回值语义错误引发的debug耗时最长同值路径这题我记忆非常深刻给定二叉树求最长的、路径上所有节点值相同的路径长度路径不需要经过根节点。我第一版代码的思路是让 dfs 返回当前子树内最长的已确认同值路径然后在父节点把左右返回值和当前节点拼接结果怎么 debug 都是偏差 1 或 2。花了不少时间才想明白返回值的语义完全搞错了。父节点只能利用从子节点出发、顺着相同值能向下延伸多长这个信息才可以拼接。而当前子树内全局最长路径这种答案应该用全局变量记录由每层递归顺手更新它而不是放在返回值里向上传递。修正后的核心逻辑是ans 0 def dfs(root): nonlocal ans if not root: return 0 left dfs(root.left) right dfs(root.right) left_arrow left 1 if root.left and root.left.val root.val else 0 right_arrow right 1 if root.right and root.right.val root.val else 0 ans max(ans, left_arrow right_arrow) return max(left_arrow, right_arrow)这里的left_arrow表示从当前节点向左延伸、节点值保持同值的最长边数。ans负责收集以当前节点为转折点、左右拼接的候选答案。返回值只向父节点报告较长的那个方向因为父节点不可能把左右两条都接上它只能续在一条路径后面。这个返回值只报告向上层能用的信息最终答案交给全局变量的原则解决了我后续碰到的大量树形 DP 题。4.3 返回信息不止一个值元组与全局变量的分工有些情况下一个返回值装不下所有信息因为父节点既需要知道子树高度又需要知道子树是否平衡。判断平衡二叉树时我会返回一个元组比如(height, is_balanced)def isBalanced(root): def check(node): if not node: return 0, True left_h, left_ok check(node.left) right_h, right_ok check(node.right) return max(left_h, right_h) 1, left_ok and right_ok and abs(left_h - right_h) 1 return check(root)[1]我的体会是返回的元组里的每个字段都要有明确语义最好在写代码前就用注释标注这里返回的是子树高度不然递归套递归很容易把两个值搞混。牛客笔试里树形题经常和二叉搜索树、最近公共祖先这类概念结合本质上都是让你想清楚这个节点应该向上报告什么、把什么留在本层处理。把返回值语义想明白了这类题基本就是套模板的事。5. 错题回炉与限时训练我在刷题效率上踩过的坑第5期最大的收获其实不在具体题上而在刷题方法本身。之前我只是刷了这一期我把复盘真正做成了流程。5.1 错题重做的时间点该怎么安排我以前对于错题顶多是把题号记在备忘录里然后就没有然后了。等到下一次遇到同类型题依然犯错才开始后悔。第5期我定了两条硬规则一道题卡了 30 分钟以上直接标记为错题不许只记个题号就完事。错题必须在 3 天后、1 周后各重做一次重做时不看任何笔记白板直接写直到能连续通过用例并且能说清楚当时为什么卡住才算真正消化。这个节奏执行一段时间后同类错误复发率肉眼可见地下降。原因在于记忆曲线3 天后重做靠的是一点模糊记忆如果此时还能独立做出来基本说明套路已经内化如果做不出来说明当时根本没有理解只是把题解抄了一遍。5.2 讲题输出法为什么比反复看题解有用只看题解容易产生一种假象好像自己懂了。很多题解区里写着秒杀一行解决我一度也喜欢收藏这种模板后来发现收藏完根本不看更别提用。第5期我换了一个方法每天挑一道已经做过的题不写代码先用自然语言把思路写在空白的文档里。写不出来或者写得磕磕绊绊的就是知识盲区。补完盲区再写代码代码一次通过的几率比以前大很多。这个方法尤其适合动态规划和贪心因为这两类题目代码往往只有十行真正的分量全在思路推导。你能把一个状态转移解释清楚才有资格说这题会了。牛客的题解区讨论质量很高很多人会给出不同的状态定义我的建议是别照收自己把每个状态定义代入题目跑两组用例选最顺的那个固定为自己的模板。别人的模板始终是别人的只有你自己讲得顺的逻辑才是考场里能救你的逻辑。5.3 按标签刷还是乱序刷学习阶段按标签刷是合理的因为人的注意力有限集中在同一类型里才能形成对比和模板。但冲刺阶段必须乱序因为笔试不会告诉你这题是 DP 还是滑动窗口题干会伪装成一堆业务场景。我的第5期安排是前两周按标签集中收拾弱项后两周开始做牛客的模拟卷乱序限时。模拟卷里遇到难题我给自己定了一个铁规矩单题超过 20 分钟没有完整思路就放下先把后面能拿的分拿住。笔试看的是总分不是谁做的题多。我某次模拟卷因为在树形 DP 题上死磕太久导致后面两道简单题几乎没时间写这个教训至今还在提醒我卡住的题标记了第二天再想比硬耗十几分钟高效得多。6. 牛客笔试环境里的翻车细节与应对策略第5期参加了几场模拟笔试我发现一个非常现实的问题很多人题目本身会做却因为输入输出、边界条件或者复杂度问题拿不到分。这些细节不是核心考点但往往就是通过率的生死线。6.1 多组测试数据的读入你错过的第一个隐藏分牛客笔试和常规刷题平台最大的不同在于很多题目要求自己处理标准输入输出而且常常包含多组测试用例。新手最容易犯的错是只做一次input()就收工遇到第二个用例直接程序结束判题结果自然是大面积错误。稳妥的做法是一次性读入全部数据再按索引切分。我常用的模板是import sys data sys.stdin.read().split() idx 0 while idx len(data): n int(data[idx]); idx 1 arr list(map(int, data[idx:idx n])); idx n # 处理当前这组数据打印结果输出方面也建议统一收集把答案放进一个 list最后用\n.join(...)一次输出。频繁print在数据量大时会带来 IO 开销虽然多数通过是没问题的但何必给判题系统留下超时的借口。6.2 复杂度的一根稻草切片、pop(0)与重复求和有人觉得自己主逻辑明明是 O(n)为什么一跑就是超时问题往往出在内部的小操作上。比如想在循环里取区间和有人会写sum(nums[i:j])表面看是一行实际上每次切片产生的临时数组就已经是 O(n) 开销整个算法直接变 O(n²)。类似地频繁使用list.pop(0)也是 O(n) 操作Python 列表在头部弹出之后需要把后续元素整体前移。要高频操作队列头部时应该用collections.deque或者干脆用双指针维护一个虚拟队列。上考场前我给自己定的检查清单就一句话循环里面是否只有 O(1) 操作如果出现了切片、pop(0)、sum 临时区间、count 大字符串这类操作说明代码还需要再优化一层。6.3 边界数据n0、n1、负数与极大值判题系统的边界数据是隐藏杀手。有一次我在做最长重复字符替换时题目的字符串可能为空我的代码直接访问了s[0]当场越界。这其实是可以提前避免的只要在写主逻辑前先跑几个边界用例。我第5期养成了一个习惯每道题写完后不再只看着 AC 就完事而是额外测这组最小边界集合——空输入、单元素输入、全部相同元素、全部逆序、最大值极限。这套用例搭起来大概只要两分钟但它能拦截掉至少三分之一的自测错误。Python 因为整型不溢出在极大值面前没有压力但用 C 或 Java 的同学一定要小心。牛客有些题的数据规模会到 10^9两个数加起来就可能爆 int。遇到这种题老老实实long long起步。6.4 单题超时死磕笔试最贵的沉没成本第5期模拟笔试给了我一个很痛的教训一道题卡了 30 分钟没有思路我不舍得放弃继续硬啃最后虽然勉强有了方案但没时间写完其他简单的题又没空做。从那以后我把策略改成两遍做题法。第一遍从头到尾快速过一遍把一眼能做的题先拿稳第二遍再回来啃卡住的题。这个策略让我在最近两次模拟里总分都更稳。平时的训练里也可以模拟这种状态给自己限时测试自己放弃难题的果断程度。毕竟真正到了笔试现场时间管理能力也是分数的一部分。6.5 一套可复用的复盘模板让每次翻车都变成经验第5期结尾时我把每天的复盘笔记固定成了一个模板分成四块题型归类、关键状态或指针设计、边界用例、一句话总结。写多了之后这些模板慢慢变成我的索引库。遇到新题时我脑子里会自动检索这不是上次那个状态定义逆序遍历的问题吗这个窗口收缩逻辑和最小覆盖子串一模一样。我会把每次翻车的原因也写进去。比如某天发现副本列表传进递归后数据被污染在模板里记下递归中尽量传 index 而不是切片副本再比如某天发现二分答案的左右边界写反了就在模板里记下确定 mid 时先确认上下界是用闭区间还是开区间。这些看起来都是小细节但积累到一定量之后它们比刷几十道新题都值钱因为它们直击的是你个人的薄弱环节。