前两天整理电脑里的刷题笔记翻出一份2020年牛客模考四模的编程题记录。正好最近不少朋友在问笔试编程题到底该怎么刷、从哪里找有代表性的套题我就把这套题重新拿出来逐题过了一遍。这套题虽然年份有点久但题目结构在当年的模拟笔试里很有代表性字符串处理、滑动窗口、动态规划、并查集四类题型全占了难度分布也算合理非常适合用来做阶段性自测和复盘。需要先说明的是原始题面我没有完整保存下面涉及的具体题面是基于当时题型还原的核心考点与原始题一致细节上可能有出入重点看解题思路。我会按我整理题时的顺序来讲从整体结构到每道题的拆解再到容易翻车的边界条件最后讲复盘方法。这样你不仅能会做这几道题还能把这套思路迁移到其他笔试套题上。1. 先看整体2020四模题目结构与真正的考点分布1.1 模拟笔试的题目构成牛客模考的编程题部分通常一场是四道题左右难度从签到题到压轴题依次拉开。2020四模这套题的结构大概是这样的题号题型核心考点预估难度推荐用时第1题字符串处理括号合法性、贪心计数简单10分钟第2题双指针/滑动窗口哈希表、窗口收缩中等20分钟第3题动态规划分组背包、状态转移中等偏上25分钟第4题图论并查集、连通分量动态维护中等20分钟这个分布很典型前两道题是“大家都得拿分”的题考察的是对基础数据结构和常见算法的熟悉度后两道题开始拉开差距需要你能从题目描述里抽象出模型再套用对应算法。我后来复盘时发现这套题的区分度设计得相当好——第1题和第2题是基本功第3题和第4题是建模能力。1.2 为什么是这些考点很多人刷题只看题解不太琢磨“为什么考这个”但我刷多了以后发现笔试出题人的思路其实很固定他们想在有限的几个题目里快速筛出两类人——基本功扎实的人以及遇到陌生问题能拆解的人。字符串、双指针、动态规划、并查集这四类恰好覆盖了笔试中最常见的思维模式字符串题考察的是细节处理和贪心直觉。括号匹配这类题看起来简单但很容易在“顺序”和“数量”之间犯迷糊。滑动窗口考察的是“如何在O(n)时间内维护一个连续区间”的思维这是很多后续算法的基础。动态规划考察状态定义能力。能正确定义状态就成功了一半定义错了后面全是白费。并查集考察数据结构熟练度。它的模板很短但应用场景极广动态连通性问题是笔试和面试都爱用的考点。明白这一层你再去刷题就会有方向感不是背模板而是练思维。1.3 我选Python来复盘的原因这几年越来越多的人用Python刷题连不少入门级考试也在Python化所以拿Python来复盘这套题完全不过时。我自己的感受是Python写算法题的几个优势很明显代码量少。同样的滑动窗口逻辑C可能要写十几行Python几行就表达完了。内建数据结构好用。字典、集合、列表推导式可以让人把精力集中在算法本身而不是折腾底层实现。大整数不会溢出。在Python里算乘法、加法不用担心int范围这对第3题这种涉及价值累加的题很友好。当然Python也有劣势比如运行速度慢。但牛客这种在线笔试环境一般会充分考虑语言的执行效率差异只要你算法复杂度没写崩Python通过是没问题的。我下面的解法都以Python为准C/Java思路完全一致。2. 四道还原题的拆题、编码与踩坑过程2.1 第1题括号修改问题先看第一道题。还原后的题面是这样给定一个只包含(和)的字符串长度 n。可以修改任意位置的括号求让整个字符串变成合法括号序列的最少修改次数。合法括号序列的定义是左括号和右括号数量相等且任意前缀中左括号数不少于右括号数。我当时第一反应是数左右括号数量差差的一半就是答案。这个想法很快被推翻因为括号顺序同样会影响合法性。举个例子)())这个字符串左右括号数量都是2但它是非法的——第一个字符就是右括号前缀左括号数直接为负。如果只按数量差算答案会是0显然不对。正确思路是贪心维护一个变量balance代表当前未匹配的左括号数。遍历字符串遇到(时balance 1。遇到)时balance - 1。如果balance变成负数说明当前这个右括号是“多余的”它打破了前缀合法性。我们必须把它改成左括号修改次数加一同时balance 2修正回来。遍历结束后balance可能还大于0说明有多余的左括号。因为左括号数量合法时一定是偶数所以还需要把balance // 2个左括号改成右括号。最终修改次数是二者之和。def min_fix(s: str) - int: bal 0 ans 0 for ch in s: if ch (: bal 1 else: bal - 1 if bal 0: bal 2 ans 1 return ans bal // 2这里有个细节值得展开为什么最后是bal // 2而不是bal因为在扫描过程中每次把多余的右括号改成左括号时bal都会加上2。每个修改操作会让括号差值变化2所以最终剩余的bal一定是偶数除2就是需要把左括号改成右括号的次数。时间复杂度 O(n)空间复杂度 O(1)。这个解法在LeetCode和牛客的同类题目里都能应付属于非常经典的贪心题。踩坑点在于有些人会用栈来模拟括号匹配然后统计“匹配失败”的数量。栈的写法也能做但代码更长而且在“修改括号”这类需要动态调整的场景下栈不如计数法直观。我建议这类题优先用计数贪心。2.2 第2题至多包含K种不同字符的最长子串第二题是高频考点。还原后的题面给定字符串 s 和整数 k返回最多包含 k 种不同字符的最长子串的长度。要求 O(n) 时间复杂度。这个题一看就是滑动窗口。思路很直白右指针不断向右扩展把字符加入窗口窗口内用一个哈希表记录每种字符的出现次数当窗口内不同字符数超过 k 时左指针右移逐渐缩小窗口直到字符种类数回到 k 以内。窗口每扩展一步就尝试用当前长度更新答案。from collections import defaultdict def length_of_longest_substring_k_distinct(s: str, k: int) - int: if not s or k 0: return 0 left 0 cnt defaultdict(int) ans 0 for right, ch in enumerate(s): cnt[ch] 1 while len(cnt) k: left_ch s[left] cnt[left_ch] - 1 if cnt[left_ch] 0: del cnt[left_ch] left 1 ans max(ans, right - left 1) return ans代码不长但有几个地方容易踩坑。第一个坑是del cnt[left_ch]的时机。当某个字符出现次数减到0时必须显式删掉这个 key否则len(cnt)会一直把它算进去导致窗口永远无法收缩。很多初学者会忘记del结果len(cnt)用字典的 key 数量来判断时出错。我在本地调试时就遇到过这个 bug明明窗口已经合法了程序却一直进入 while 循环。第二个坑是左指针的更新方式。这里用 while 循环逐个缩窗口确保窗口内字符种类数降到 k 及以下。有人会问能不能直接跳到某个位置比如记录每个字符上次出现的位置然后一次性把左指针跳到最靠左的“必须移出窗口”的位置。理论上可以做但贪心地一次跳到位容易漏掉中间状态而且代码复杂度会陡然上升。笔试场景下while 循环虽然看起来慢一点但每个字符最多进窗口一次、出窗口一次整体均摊 O(n)完全够用。第三个坑是更新答案的时机。一定要在窗口收缩完成之后再用right - left 1更新否则窗口内字符种类数可能还是超标的拿一个非法长度去更新答案会出错。2.3 第3题互斥物品的分组背包第三题是这套题里比较有区分度的一道。还原后的题面有 N 个物品每个物品有重量 w 和价值 v背包容量为 C。部分物品之间存在互斥关系同一组内的物品最多只能选一个也可以都不选。求背包能装下的最大价值。刚看到这个题的时候我第一反应是01背包因为“互斥”看起来只是多个约束条件。但仔细一想互斥关系让物品被分成了若干组每组内只能挑一个这其实是分组背包模型。分组背包的转移逻辑是对于每一组你要决定“这一组选哪一个物品”或“这一组一个都不选”然后按照01背包的思路更新整个容量数组。为了保证“每组最多选一个”容量必须倒序遍历而且组内物品的遍历要放在容量循环的内部。def max_value(groups, C): dp [0] * (C 1) for group in groups: for j in range(C, -1, -1): for w, v in group: if j w: dp[j] max(dp[j], dp[j - w] v) return dp[C]这里有一个非常经典的错误把容量循环放在最外层组内物品循环放在内层或者把容量改成正序遍历。这样会导致同一组内的多个物品被当作不同物品重复选择完全违背“互斥”的约束结果会偏大。我第一次写的时候就把容量循环写成了正序结果样例里有一组两个相同重量的物品都被选中了总价值明显超标。排查了半天才发现分组背包里组内物品的循环必须放在容量循环里面这样才能保证当一个物品被选入后同组的其他物品无法再选第二次。另一个细节是如果组内的物品很多或者背包容量很大三层循环可能超时。这时候要结合数据范围做优化。比如某个组内如果有很多重量相同但价值低的物品可以只保留每个重量下价值最高的那个如果组的数量很多但每组的物品很少直接分组背包即可。2020四模的数据范围我记得没有设计得特别极端分组背包 O(组数 × 容量 × 每组物品数) 是能过的。2.4 第4题动态图的连通分量最后一题考并查集。还原后的题面有 n 个节点初始时没有任何边。按顺序给 m 条加边操作每次加边后要求输出当前整个图的连通分量数量。n 和 m 最大可达 2e5。这个题说实话模板背熟的人闭着眼睛都能写但真要写对还是有几个小坑。首先是“动态加边、实时查询连通分量”的含义每加入一条边就可能把两个连通分量合并成一个所以连通分量数会递减。初始连通分量数就是 n每次合并成功数量减 1如果两个节点本来就在同一个连通分量里数量不变。并查集的实现我建议直接用“路径压缩 按秩合并”的写法。路径压缩让 find 操作几乎摊成 O(1)按秩合并避免树退化成长链。class DSU: def __init__(self, n): self.parent list(range(n 1)) self.rank [0] * (n 1) self.count n def find(self, x): while self.parent[x] ! x: self.parent[x] self.parent[self.parent[x]] x self.parent[x] return x def union(self, a, b): ra self.find(a) rb self.find(b) if ra rb: return False if self.rank[ra] self.rank[rb]: ra, rb rb, ra self.parent[rb] ra if self.rank[ra] self.rank[rb]: self.rank[ra] 1 self.count - 1 return True n, m map(int, input().split()) dsu DSU(n) for _ in range(m): a, b map(int, input().split()) dsu.union(a, b) print(dsu.count)这里有几个容易踩的细节。第一find 函数我用的是迭代写法而不是递归写法。原因是并查集在某些极端情况下树的高度可能比较大递归深度太深会直接爆栈尤其是牛客这类在线环境不一定帮你调大递归限制。迭代写法的可读性差一点但绝对安全。第二union 时要注意方向。如果不做按秩合并直接把 rb 指向 ra在某些输入下树会变成一条长链find 就会退化。按秩合并的思路是“矮的树挂到高的树下”这样树的高度增长很慢。第三节点编号从 1 开始还是从 0 开始。我当时在牛客做题时差点踩坑题目如果说明节点编号从 1 开始并查集的 parent 数组就要开到 n1初始化 range(n1)否则遍历时会 IndexError。这类细节在笔试里就是5分钟的事但在现场很容易被忽略。3. 边界条件与极端用例反复翻车的几个点3.1 数组越界与空输入的防护刷这套题时我发现自己有个习惯不太好拿到题先写核心逻辑边界条件全靠“最后想一想”。这导致我经常在提交后才发现漏了某个用例。以这套题为例最容易漏的边界条件有这些第1题字符串可能为空。空串不需要任何修改直接返回0即可。如果代码里不防空串遍历时不会出错但如果你用了s[0]这类索引就会爆。第2题s 为空或 k 为 0。这两种情况最长子串长度都是0。很多人会漏掉 k0 的情况因为默认 k 是正数。第3题背包容量 C 可能为0或者没有任何物品。此时最大价值就是0。第4题n1 时连通分量数始终是1m0 时根本不会有输出或者说输出0次。我的建议是每写一道题先在本地列一个“输入边界清单”空输入最小规模输入n1或长度为1全同字符/全相同值输入最大规模输入用来检查是否会超时或溢出把这些 case 在核心逻辑跑一遍再提交比反复试错更省时间。3.2 数值溢出与取模细节Python用户在这块省心很多大整数不会溢出。但如果你平时也写 C 或 Java就要格外注意dp 数组中存的是价值总和如果 C 很大、物品很多int 可能会溢出。C 里该用 long long 就用 long longJava 里该用 long 就用 long。还有一个和取模相关的细节。如果题目要求答案对某个大素数取模常见的是 1e97那么所有涉及累加/求和的运算都要取模而且要注意负数取模的问题。在 C 里(a - b) % MOD的结果可能是负数需要写成((a - b) % MOD MOD) % MOD。Python 的取模结果是非负的所以不会踩这个坑但你要是把 Python 代码翻译成 C 时忘记了就会平白无故 WA。3.3 超时不是玄学复杂度估算方法很多选手在笔试时“觉得自己写对了但一直超时”根本原因是没根据数据范围反推复杂度。我一般拿到题先看数据范围心里大概有个预期复杂度表数据规模可接受复杂度n 10O(n!)暴力枚举n 20O(2^n)状态压缩n 500O(n^3)三重循环谨慎n 5000O(n^2)两重循环n 1e5O(n log n)n 1e6O(n)拿这套题举例第2题的 n 如果到 1e5用 O(n^2) 的双重循环必然超时所以必须用滑动窗口。第3题的组数和容量如果都到 1e5三层循环会非常危险可能要考虑把组内物品用单调栈或其他方式优化或者大部分情况下分组背包本身复杂度可接受。第4题的 n 和 m 到 2e5并查集 O(m α(n)) 毫无压力。一句话总结先看数据范围再定算法。不要上来就写写完才发现复杂度不对那才是最浪费时间的。4. 复盘这套题后总结的刷题与应试方法4.1 错题本的正确打开方式我知道很多人的错题本就是“把题解抄一遍”说实话这没什么用。我自己试过好几种方式最有效的是记录三件事我卡在哪个点。比如第3题我卡在“互斥关系怎么表达成状态转移”第1题我卡在“左右括号数量相等但不合法”。意识到哪一点后能做出来。这和第一件事紧密相关。比如第3题意识到可以按互斥关系分组然后套分组背包模板。这道题可以和哪些题归为一类。第1题的括号修改可以归为“括号序列计数贪心”第2题可以归为“窗口维护”第3题归为“分组背包模型”。第二天我会把错题当成新题重新写一遍不看任何提示。如果还能顺利写出并通过测试用例才算真正掌握。这一套流程下来比单纯刷五道新题都有效。4.2 时间分配与AC策略牛客模考这类模拟笔试通常时间在90分钟左右。我的做题策略是前5分钟把所有题目全部扫一遍标记题号、题型、预估难度。第1题必须在10到15分钟内完成它是送分题别在这上面犹豫。第2题和第3题各给25分钟左右如果卡了20分钟还没思路先跳到下一题。第4题如果前面三道都搞定了有充足时间来做如果时间不够至少把并查集模板写上哪怕只过部分用例也能拿分。这里有个心态问题很多笔试平台是“按通过的测试用例比例给分”的不是只有0分和满分。暴力解法、部分优化、甚至只输出个默认值都可能拿到部分分。所以不要轻易空题。比如第3题如果不会写分组背包可以把所有物品按组做二进制枚举枚举所有选择组合再用01背包判断可行性至少能过小数据。4.3 代码规范带来的隐性收益最后说一个很多人不在意但在考场上很实用的点代码规范。我在复盘这套题时发现把自己的代码写得足够清晰排错会容易很多。具体来说变量命名要有意义。cnt比c好balance比bal2好。核心逻辑抽成函数。比如并查集的find和union单独写不混在主流程里。在本地调试时用断言验证关键中间值。比如第2题可以在窗口收缩后断言len(cnt) k一旦不成立立刻报错省得对着输出猜。提交前把临时调试用的打印注释或删掉避免输出多余内容导致格式错误。这些看起来都是小事但在笔试时间紧张、大脑高负荷运转的状态下代码清晰度直接决定你能否快速定位bug。我见过不少选手算法思路没问题但因为变量名乱、逻辑混在一个大函数里最后 debug 了二十分钟才发现是下标写错。回看这套2020四模最大的感受是题目怎么包装最后都在考你能不能把一道陌生的题还原成熟悉模型。括号修改考贪心和前缀合法性滑动窗口考窗口边界的维护背包考状态定义和循环顺序并查集考数据结构熟练度。刷题不是为了押题而是练“拆解-建模-实现-验证”这套流程。如果你想检验自己的水平找一套牛客模考按真实笔试时间做一遍再对照这些复盘思路过一遍会比闷头刷几十道题更有收获。