2020年牛客模考四模那会儿正是求职笔试最热的阶段。它本质上是一套模拟笔试的编程题集合题目难度贴着大厂校招笔试前两题的水准考的东西不偏全是字符串处理、排序、贪心、动态规划这些基本功。我当时把四套模考刷完最直观的感受是题目看着都见过但一到手写代码就容易翻车。这篇文章我按自己的复盘习惯把四模里有代表性的几道题整理出来讲清楚每道题的思考过程和落地实现适合正在准备校招笔试、或者刚开始刷 LeetCode 想检验一下基础的朋友。1. 这套模考的定位与价值拆解1.1 模拟笔试到底在模拟什么很多人觉得模拟笔试就是多刷几套题这个理解有偏差。牛客模考的核心价值不是题目本身而是它把真实笔试的环境和节奏复刻出来了机器判题、多组输入输出、限时提交、编译不过不给分。这些环节你平时在 IDE 里写代码根本意识不到只有切到在线评测系统里你才会发现自己连输入输出都有可能写不对。四模这套题给我的感觉是它特意把题目难度分布做成了“一题热手、两题核心、一题压轴”的结构。前面的题让你快速进入状态中间的题考察日常积累最后一题需要一点综合能力。这个结构本身就是在训练你分配考试时间的能力而不是单纯刷题的数量。另外模拟笔试还有一个容易被忽略的作用帮助你熟悉不同语言在判题环境下的行为差异。同一个题目用 C 写和用 Python 写输入读取方式、运行效率都不一样。四模里的题我都会尝试用 Python 先跑通再回头看 C 的关键写法这对以后面试手撕代码很有帮助。1.2 四模的题型分布与考点主线我回忆了一下那套题集合里的编程题大概覆盖了五类高频考点哈希表、双指针/滑动窗口、区间排序与贪心、动态规划、还有基础的二分查找。这些考点基本就是国内互联网公司笔试最喜欢考的主线内容不涉及什么冷门数据结构也没有什么奇技淫巧。从题型展开来看出题人明显在强调“用最朴素的算法解决问题”。比如字符串类题目本质上考的是哈希计数和指针移动排序类题目考的是比较规则和边界处理动态规划那道题考的是状态定义的合理性。只要你的基本功扎实哪怕没刷过原题也能顺利做出来反过来如果基础不牢光靠背模板或者记题解很容易在细节上翻车。我自己把四模的题目重新归类后发现一个规律大多数题都可以在 LeetCode 上找到同类的影子但牛客的题更贴近互联网公司的出题口味也就是数据范围给得很大、输入输出格式比较刁钻、题目描述里藏着条件。所以我建议有时间的读者把这套题集合当成查漏补缺的标尺而不是刷完就算的题库。2. 核心考点的思路拆解2.1 字符串处理哈希计数与双指针要结合起来用字符串题在笔试里出现频率极高几乎是必考的。四模里的字符串题表面看着是让你找一个子串或者字符实际上考察的是两类基本功哈希表统计和双指针维护窗口。拿“找字符串中第一个只出现一次的字符”来说最简单的思路就是两次遍历第一次用字典统计每个字符的出现次数第二次从头遍历找到第一个次数为 1 的字符直接返回它的下标。这个思路的时间复杂度是 O(n)空间复杂度也是 O(n)。很多第一次接触的同学会问能不能不用额外空间可以但代价是时间复杂度可能退化成 O(n^2)在笔试的数据规模下几乎铁定超时。所以我的习惯是先保证时间和空间的平衡再考虑优化。在笔试里能跑出正确结果永远比追求极致的内存占用更重要。字符串题还有一个容易踩的坑输入可能包含空格和换行。你的读取方式如果不对字符串的内容就已经和预期不一致了后面的逻辑再正确都是白搭。我第一次做牛客的字符串题就吃过这个亏输出结果总是对不上最后发现是读取的时候把换行符给带进去了。2.2 区间类问题贪心算法的核心是排序规则区间类问题也是技术笔试的常客四模里有一道合并区间的题。这类题的核心套路是先排序排序规则直接决定后续处理的复杂度。比如合并区间通常按区间的起点升序排序然后遍历判断当前区间和已有区间的终点谁更大以此决定是合并还是新增一个区间。为什么一定要先排序因为只有让区间按顺序排列你才能保证每次只需要和最后一个区间比较而不必回头扫描所有已合并的区间。这个点很多人不理解其实和生活里排队一个道理队伍排好了你只需要看相邻的前一个人不需要来回扫视整个队伍。贪心算法的难点不在代码而在证明贪心策略是对的。以“安排最多会议”那类题为例按会议结束时间从早到晚排序然后每次都选结束时间最早的会议这是经典做法。你需要说服自己最早结束的会议一定不会让结果变差因为它给后续会议留下的时间最多。想通了这一层代码写起来就是几行的事。2.3 动态规划状态定义对了题目就做了一半动态规划大概是笔试里区分度最高的考点。四模里那道动态规划题考的是计数类的方案总数问题。这种题型的解题路径非常固定先定义状态再写转移方程最后处理边界和初始化。而其中最容易出错的就是状态定义。以“给你若干面额的硬币问凑出目标金额有多少种方案”为例如果把状态 dp[i] 定义为“凑出金额 i 的方案总数”转移方程就是 dp[i] dp[i - coin]遍历所有硬币面额。这个定义很自然但是有一个细节循环的顺序决定了结果是否包含重复的组合。先遍历硬币面额再遍历金额得到的是“组合数”反过来先遍历金额再遍历硬币面额得到的是“排列数”。笔试时一旦顺序写反样例能过大数据的答案就会错得离谱。我见过很多同学背了很多 DP 模板一遇到变形题就不知道从哪里下手。我的建议是遇到任何 DP 题先在草稿纸上写清楚三件事状态是什么、转移是什么、初始值是什么。这三个问题想不清楚代码根本写不出来想清楚了代码其实就是把数学式子翻译成循环。3. 实操参考题目原貌与可运行代码3.1 题目一数组去重并按频率排序这道题我记得很清楚语言描述大概是给定一个整数数组请你按每个数字出现的次数从多到少排序出现次数相同的按数字本身从小到大排序最后输出去重后的序列。这道题放在第一题的位置难度不大但很考察综合运用哈希表和排序的能力。from collections import Counter def frequency_sort(arr): counter Counter(arr) # 先按出现次数降序再按数字本身升序 sorted_items sorted(counter.items(), keylambda x: (-x[1], x[0])) return [num for num, _ in sorted_items] if __name__ __main__: n int(input().strip()) arr list(map(int, input().split())) result frequency_sort(arr) print( .join(map(str, result)))这里有两个细节值得说。第一Python 的 Counter 可以直接统计频次比手写字典快很多也少出错。第二sorted 的 key 可以用元组来表示复合排序规则比如 (-x[1], x[0]) 表示先按次数降序、次数相同时按数值升序这个技巧在笔试里很常用。输入读取方面我建议所有做牛客题的朋友都用 input().strip() 再 split。千万别用 input().split() 直接读因为如果输入行末尾有空格split 本身能处理但 strip 能帮你排除换行符带来的潜在问题。这道题时间复杂度主要是排序O(n log n)数据量不是特别大的时候完全够用。3.2 题目二合并区间下面是区间合并的完整实现。输入若干行每行两个整数表示区间的起点和终点输出合并后区间的个数以及合并后的每个区间。def merge_intervals(intervals): if not intervals: return [] intervals.sort(keylambda x: x[0]) merged [intervals[0]] for start, end in intervals[1:]: last_start, last_end merged[-1] if start last_end: # 重叠更新终点 merged[-1][1] max(last_end, end) else: merged.append([start, end]) return merged if __name__ __main__: m int(input().strip()) intervals [] for _ in range(m): l, r map(int, input().split()) intervals.append([l, r]) result merge_intervals(intervals) print(len(result)) for l, r in result: print(l, r)这段代码里有个很容易被忽略的点合并时更新终点不是直接写成 merged[-1][1] end而是用 max(last_end, end)。为什么因为区间 [1, 5] 和 [2, 3] 合并之后终点仍然是 5直接用 end 会把它覆盖成 3整个逻辑就崩了。这种细节写代码的时候不觉得一跑样例就会发现错得莫名其妙。另外我在笔试中习惯用普通的两层列表保存区间而不是用 tuple原因是后面需要直接修改终点tuple 不可变会比较麻烦。这种小取舍为了代码简洁度是值得的。合并区间的关键在于排序后的线性扫描这也是经典解法。如果面试官问你复杂度要能答出排序 O(m log m)扫描 O(m)总体 O(m log m)。3.3 题目三最长无重复字符子串这道题字符串处理里非常经典。给定一个只包含小写字母的字符串请你找出其中不含有重复字符的最长子串的长度。这类题考的滑动窗口本质上就是维护一个左指针和一个右指针让窗口内的字符始终不重复。def length_of_longest_substring(s: str) - int: last_seen {} left 0 max_len 0 for right, ch in enumerate(s): if ch in last_seen and last_seen[ch] left: left last_seen[ch] 1 last_seen[ch] right max_len max(max_len, right - left 1) return max_len if __name__ __main__: s input().strip() print(length_of_longest_substring(s))理解这段代码的关键在于 left 指针什么时候移动。当遇到一个已经出现过的字符并且它的位置还在当前的窗口范围内说明窗口内有重复了这时候就要把 left 跳到上一次出现位置的下一个位置。这里的条件 last_seen[ch] left 如果漏掉会出现一个 bug同一个字符出现在窗口之外却把 left 往回拉窗口会先变小再变大案例数据偶尔能过但提交时就会翻车。这道题的时间复杂度是 O(n)因为 left 和 right 都只往右走。空间上哈希表存每个字符最近一次出现的位置也是 O(n)。很多人说滑动窗口靠天赋其实它就是两步右指针往右扩展发现不满足条件后左指针收缩。多写几道类似题目自然就熟练了。3.4 题目四零钱兑换的方案总数这道 DP 题和 LeetCode 的零钱兑换 II 几乎一样给一个总金额和几种面值的硬币问有多少种方式凑成该金额。注意是求方案总数不是最少硬币数这两个问题的状态转移方式完全不同。def change(amount: int, coins) - int: dp [0] * (amount 1) dp[0] 1 for coin in coins: for x in range(coin, amount 1): dp[x] dp[x - coin] return dp[amount] if __name__ __main__: amount, n map(int, input().split()) coins list(map(int, input().split())) print(change(amount, coins))这段代码我最想强调的是循环顺序。外层循环遍历硬币内层循环遍历金额得到的是组合数也就是说 [1, 2] 和 [2, 1] 只算一种方案。为什么要这么设计因为每枚硬币只被“使用一轮”相当于把面额 1 的所有转移做完再去做面额 2 的转移这样就不会出现同一组硬币因为顺序不同被重复计数。如果把两层循环反过来先遍历金额再遍历硬币dp 数组就会把不同顺序当成不同方案最后得到的是排列数。这个细节是 DP 题里一个非常经典的区分点我在多次模拟笔试中见过有人栽在上面。dp[0] 1 的初始化也很关键它表示的语义是“凑出 0 元有 1 种方式就是什么也不选”。边界条件想清楚这道题基本就通关了。4. 常见问题与排查技巧实录4.1 输入输出的坑多组数据与换行符牛客的判题风格和很多 OJ 不太一样它特别喜欢用多组测试数据而且没有明确的结束标志。这意味着你不能只写一个处理单组数据的 main而要考虑循环读取直到没有输入为止。用 Python 的话可以用 sys.stdin 逐行读取也可以用 try-except 捕获 EOF各有优劣。我踩过一次最冤的坑是读字符串的时候没做 strip结果把换行符也算进了字符串。比如读入 abc实际上字符串变成了 abc\n然后第一个不重复字符的下标就全错位了输出和样例完全对不上。后来我的习惯是所有 input().strip()不管是不是字符串、不需要 strip 也先带着防御性编程在笔试里不是多余。数字可以 int() 去掉换行但字符串一定记得 strip。4.2 超时的真实原因与优化手段笔试里的超时很多时候不是算法复杂度太高而是代码里的常数过大。比如 Python 在遍历大数组时频繁调用函数或使用 append 在列表头部插入insert(0, x)都会拖慢速度。在四模的一道题上我用 Python 跑大数据量时反复超时后来才发现自己在循环里不断做列表切片每切一次就产生一个新对象白白浪费了大量时间。优化方法很朴素能用索引就用索引能用集合就不用列表能用内置函数就不手写循环。Python 的 Counter、sort、defaultdict 这些内置实现都是经过高度优化的比你手写的版本快得多。只要算法复杂度已经是 O(n log n) 级别通常瓶颈就在常数上这时候优先审查代码里有没有不必要的对象创建。4.3 笔试现场的时间分配决策很多人试卷发下来就按照 1 到 4 的顺序猛做结果死在最后一道 DP 上前面的题反而没时间检查。我的策略是先把四道题都读一遍心里给每道题标一个难度分先做自己最有把握的题把能拿的分先拿到手。别觉得这是投机取巧笔试拼的就是分数把容易题的分保住比死磕难题有意义得多。具体到执行层面我给自己的规矩是一道题如果想了十五分钟没有任何思路先跳过去做下一道。做完后面容易的题之后如果还有时间再回头啃难题。这也是四模教我的一件事模拟考试的节奏比题目本身更值得复盘你的时间分配是否合理直接决定最终分数。写在最后四模这套题集合说实话题目难度放在今天看依然不虚。我后来刷了很多题再回头看这套题才意识到它帮我练出来的不是某个具体的解法而是面对题目时的第一反应先想复杂度再想用什么数据结构最后用代码验证思路。如果你也在准备笔试我建议别只看题解一定自己动手把代码敲一遍跑过样例再对着评测系统真实提交一次。手感和裸看完全是两回事这个习惯比多刷一百道题都值。