2017年秋招季我在牛客网上把那套“四模”编程题从头到尾刷了一遍。说实话当时做完第一道题我就意识到这套题跟平时练的LeetCode风格不太一样——题目描述看似温和但边界条件埋得特别深稍不留神就掉进超时或者越界的坑里。现在回头看这套题恰恰是那时候大厂笔试套路的典型样本也是我后来整理刷题框架的重要起点。这篇博文不打算逐题粘贴标准答案而是想把这套题的考察逻辑、每类题目的推理路径、以及当年很多人在考场里踩过的细节坑聊透。无论你是准备校招的应届生还是想检验自己基础功底的工程师这篇文章的思路都能直接复用。1. 2017年牛客四模的题型画像这套题到底在考什么1.1 从四道题的分布看当时大厂的出题偏好2017年的牛客模考四模编程题整体上是四道题的结构覆盖了字符串处理、动态规划、数组模拟和数学推导这几大类。这个结构放在当年很有代表性因为那时候互联网公司的笔试普遍喜欢用“一字符串、一DP、一模拟、一数学”的组合来区分候选人层次。第一梯队是字符串题主要考察基本功和对API的熟练程度不会太为难人但代码写得干不干净、边界条件想没想全很容易拉开差距。第二梯队是动态规划这是区分“会写代码”和“会算法”的分水岭一般会藏在中等难度的包装下面需要你自己从问题里抽取出状态定义和转移方程。第三梯队是数组和模拟类的题看似简单但往往隐含了时间复杂度陷阱——比如用多层循环硬莽数据一大就直接超时。第四道通常是数学题或者需要一点推导能力的综合题这道题往往决定你能不能拿满分。所以你看这套题表面上叫“模考”实际上就是一次“大厂笔试题型的全真模拟”。它不是在为难你而是在帮你在正式笔试前暴露问题。当年我做这套题的时候字符串题写了半小时DP题推导到一半卡住模拟题因为没注意数据范围超时了一次——这些问题如果在正式笔试前发现代价只会更大。1.2 为什么拼命背模板的人容易在这套题上翻车有一个现象很有意思2017年前后网上流行各种“笔试模板”什么“回溯法模板”“DP模板”“快排模板”很多同学背得滚瓜烂熟一到牛客模考就傻眼。原因在于这套题的设计者显然对所有经典模板做了“防呆处理”——题目不会直接让你“求最长递增子序列”而是会把它藏在“求最多能参加多少场不冲突的会议”这样的业务描述里。这种命题方式在真实的笔试环境中非常常见。公司的面试官不关心你会不会背模板他们关心的是你能不能理解问题本质然后选择合适的数据结构和算法。我从这套题里得到的最大教训就是模板是用来加速编码的不是用来替代思考的。如果只背模板而不理解背后的时间复杂度推导、状态转移逻辑遇到稍微换个包装的题目照样无从下手。这里我特别建议大家养成一个好习惯每做完一道题不要急着看下一道而是花30秒在脑子里把这道题归个类——它考的是哪一类核心方法如果我是出题人我会在哪个地方设一个陷阱这个习惯我从2017年坚持到现在非常管用。2. 字符串操作题看着简单失分点全在细节里2.1 单词翻转类题目的双指针思路字符串题里有一类特别经典的变形——单词翻转。题目一般会给你一个英文句子让你把单词顺序翻转但单词内部的字母顺序不变。很多人的第一反应是先把整个字符串反转再对每个单词做一次反转。这个思路是对的但实现起来却很容易翻车。当年我用C写这道题时先后踩了两个坑。第一个坑是没考虑多个连续空格的情况。普通做法是用cin s按空格切片但题目如果要求保留原始空格数量这种做法就直接废了。正确的做法是用双指针先跳过所有空格再找到一个完整单词翻转它然后再继续找下一个单词直到遍历完整个字符串。第二个坑是局部反转的边界判断。我在写初始版本时单词的右边界判断写成了while (j len s[j] ! )但漏了j len这个条件结果最后一个单词没有空格兜底导致数组越界。在本地测试时这个bug没暴露因为最后一个字符恰好不是空格但在牛客的极端用例里直接就Runtime Error了。所以关于字符串题我总结出一个铁律所有涉及下标移动的代码先想清楚“最后一次移动是否越界”再写while循环。这个习惯真的能救命。2.2 括号匹配的变体栈不是唯一的解法括号匹配是另一个高频考点。2017年牛客四模里有一道题虽然是括号匹配的变体但刻意降低了难度——只要求判断字符串中的括号是否合法并没有引入三种括号的优先级问题。我当时的第一反应是用Stack每个左括号入栈遇到右括号就弹栈最后判断栈是否为空。这个思路没有任何问题时间复杂度是O(n)空间复杂度也是O(n)。但有一个细节值得注意如果题目只涉及一种括号那么完全不用栈用一个计数器就能完成匹配。遇到左括号加一遇到右括号减一任何时候计数器为负或者遍历结束后计数器不为零就说明不合法。这道题用计数器不仅空间复杂度降为O(1)而且代码量也少一半。这给我们的启发是做题不能只会套数据结构而要分析题目条件选择最简方案。能用计数器解决的何必引入栈当然一旦题目变成“同时匹配()、[]、{}三种括号”计数器就无能为力了这时候必须用栈。所以判断标准很简单单一符号用计数复合符号用栈。这个经验在面试时讲出来面试官会觉得你是真的理解问题而不是背题。2.3 字符频率统计里的数组映射技巧还有一类字符串题会给定一个字符串让你判断它能否通过重新排列变成回文串。这类题的本质是统计每个字符出现的次数如果超过一个字符的出现次数是奇数那么它就无法构成回文串。明白了这个本质解法其实就一行逻辑用一个长度为128的数组做字符到频率的映射遍历一次统计再遍历一次检查奇数次字符的数量。这里有个很多新手容易忽略的点直接用HashMap当然可以但在字符集很小的时候比如只有小写字母或ASCII码用数组比用HashMap更快、更省空间。2017年的时候Java的HashMap还没像现在这样优化得这么好笔试环境下用数组实现的代码性能优势是很明显的。即便是现在我也建议在允许的情况下优先用数组做映射——在牛客这种OJ环境下Java用int[128]代替HashMap能让你的代码在极端用例下少很多不确定性。字符串类题目的整体复盘不要只求“能过”要追求“过得很稳”。每写一个循环都要问自己三个问题初始条件对不对终止条件会不会越界循环体内的状态会不会意外改变这三个问题检查完字符串题基本就不会翻车了。3. 动态规划题从暴力递归到状态压缩的完整推导3.1 怎么识别一道题需要动态规划动态规划题有个共同特征那就是问题可以被拆分成“结构相同但规模更小”的子问题并且子问题的解会被反复使用。2017年牛客四模里那道典型的DP题表面上描述的是“从一个网格左上角走到右下角每次只能向右或向下求最小路径和”——这种题一眼就能识别出来。但更隐蔽的DP题会披着“看电影选场次”或者“安排会议”的外衣描述里全是业务术语这时候就需要你先把业务语义剥离掉找到它的数学结构。我的方法是问自己两个问题第一如果我已经知道规模为n-1的答案能不能在常数时间内推导出规模为n的答案第二这个推导过程是否只依赖有限个状态如果两个答案都是Yes那基本就是DP题。还有一个实用的排除法如果一道题可以用暴力搜索解出来但是搜索空间特别大指数级同时最优解又要求“最大/最小/最多/最少”这类词那十有八九是动态规划。2017年那会儿很多同学习惯“DFS暴搜加剪枝”遇到小数据能过但一旦数据范围超过20就超时。DP思想的价值就在于它能通过“空间换时间”把指数级的暴力降成多项式级的迭代。3.2 从递归到迭代一步一步推导而不是直接背方程动态规划的核心是状态转移方程但方程不是天上掉下来的而是一步步推出来的。当时我解网格最小路径和这道题用的思路是先定义一个函数f(i, j)表示从起点走到坐标(i, j)的最小路径和。因为只能向右或向下走所以f(i, j)只能从f(i-1, j)从上边来或者f(i, j-1)从左边来转移过来那答案自然是f(i, j) min(f(i-1, j), f(i, j-1)) grid[i][j]。很多初学者上来就直接背这个方程然后套两层循环实现。这虽然没错但一旦题目的状态维度增加比如加一个“最多只能走k步”的条件背方程的方法就失效了。我自己的习惯是第一次遇到这类题一定老老实实先写递归版本让代码去模拟“从终点回推起点”的过程。递归版本可能栈溢出、可能重复计算但它能帮我把状态定义和转移逻辑理解透彻。然后再写记忆化搜索最后再改成自底向上的迭代DP每一步都清楚自己在干什么。这套“递归→记忆化→迭代”的三步法是我在2017年那套模考里收获最大的东西。基础薄弱的读者一定要试一遍这个流程不要直接跳到最终写法。3.3 状态压缩从二维数组到一维数组的优化当你理解了二维DP的迭代版本接下来还可以再往前走一步——状态压缩。网格最小路径和的状态转移只依赖当前行的前一个格子i和上一行的对应格子i-1所以不需要开一个二维数组只需要用一个一维数组滚动更新就能完成。具体做法是初始化dp[j]为第一行从左到右的前缀和然后从第二行开始逐行更新每一行更新时dp[j] min(dp[j], dp[j-1]) grid[i][j]。这里的dp[j]在更新前代表上一行从起点到第j列的答案更新后代表当前行到第j列的答案。理解这个“覆盖”过程需要一点想象力但一旦想清楚代码的简洁度和空间效率都会上一个台阶。在笔试中状态压缩不一定是必然要求但一旦数据范围给到10^5级别的长条形网格二维数组就可能超出内存限制这时候压缩的价值就体现出来了。我建议所有准备笔试的朋友在学完DP基础后专门练一练状态压缩这不仅是优化技巧也是加深状态转移理解的极好途径。4. 模拟与数组处理题边界条件本身就是考点4.1 约瑟夫环类问题的模拟解法与数学优化2017年那套模考里有一个很有意思的数学模拟题——约瑟夫环。题目描述是n个人围成一圈从某个位置开始报数报到m的人出列然后从下一个人继续报数直到剩下最后一个人要求输出最后存活者的编号。初学者最自然的想法是模拟整个出列过程。可以用一个环形链表来模拟也可以用数组配合visited标记来跳过已经出列的人。这个解法思路清晰但复杂度是O(n*m)的n和m一大就非常吃力。当年这道题的数据范围给得比较严格纯模拟只能过一半的测试用例。优化的思路来自数学递推。定义f(n)为n个人从0开始编号时最后存活者的编号。当我们淘汰掉编号为m-1的人后剩下n-1个人的问题其实可以映射为一个新的(n-1)人约瑟夫环但所有人的编号都向前平移了m个位置。所以核心递推是f(n) (f(n-1) m) % n。有了这个递推就能用O(n)的循环直接算出答案完全不需要模拟。这个转换是这类题的灵魂。如果你在笔试里遇到约瑟夫环变体比如报数方向是顺时针走m步但被淘汰后反向走n步先把原问题抽象成数学表达式再想递推千万不要一上来就构造链表。4.2 区间合并问题里的排序细节区间合并也是四模里很有代表性的一道题。给定一组区间让你合并所有重叠区间。这道题的核心逻辑其实很简单先把所有区间按左端点排序然后遍历维护当前合并区间的右边界。但这里有一个隐藏的坑也是当年很多人做错的地方排序时如果左端点相同是否需要按右端点排序我当时的做法是只按左端点排序然后直接在遍历中更新右边界为max(当前右边界, 下一个区间的右端点)。这样是正确的因为左端点相同的情况下右端点的处理会通过max操作自动完成不需要额外的排序键。但如果你的实现方式是“把下一个区间合并进当前区间直接取当前右边界与下一个右边界中的较大者”那么也是对的。还有一个容易忽略的点输入的区间是否保证有序如果题目没有明确说就不能假设有序必须先排序。很多同学在本地测试时输入的区间恰好有序于是跳过了排序结果提交后面对乱序数据直接报错。在OJ场景里永远不要依赖输入数据“恰好满足你的假设”。4.3 大数运算与整数溢出的那些坑2017年的四模里还有一道大数相关的题要求计算两个大整数的和但数据范围远超int和long long的表示能力。这类题有两种解法一是把大数当成字符串模拟竖式加法二是用数组或者链表存储每一位手动管理进位。我的建议是优先掌握字符串模拟的思路。具体流程是从两个字符串的末位开始逐位相加维护一个进位carry每一位的结果为(sum % 10) 0拼接到结果字符串的前面最后如果carry不为0再补一个最高位。注意拼接的方向——如果使用res char res这种方式字符串会不断在头部插入复杂度是O(n^2)更高效的做法是先用push_back最后再用reverse统一反转这样复杂度是O(n)。这道题也提醒我们看到“大数”“超长整数”“数值范围极大”这些词条件反射就应该切换成字符串或者BigInteger的思路。2017年那会儿很多语言的库没有直接提供大数类现在好多了但理解模拟加法仍然很有价值因为工程里很多高精度问题都需要你手动实现位运算级别的逻辑。5. 赛后复盘从“把题做出来”到“把题做得快”5.1 四道题的时间分配策略做完这套模考后我复盘了自己的时间分配发现一个大问题我在第一道字符串题上花了太多时间精修代码导致后面两道简单题没有足够的时间做最后一道DP只写了暴搜的版本。这是完全没有必要的。我的建议是动笔前后先快速浏览四道题花3分钟评估每道题的难度和数据范围然后把题目分成两类——送分题和攻坚题。先做送分题保证基础分拿到再回头啃中等难度的题最后剩多少时间就做多少攻坚题。正式笔试中拿满送分题的正确率远比“有一道DP题写得非常完美但其他题都没时间做”更划算。还有一个细节每道题提交前一定要测试边界情况。当年我检查的时候发现区间合并那道题如果输入是空数组我的代码会直接报错。加了一行if (intervals.isEmpty()) return new int[0][0];就解决了。这种边界case本地测试根本不会遇到但OJ的用例设计者一定会放进去。5.2 检查清单提交前花一分钟少丢一半分我在刷完这套模考之后给自己列了一个“提交前检查清单”现在分享给看到的读者这个清单也适用于所有在线编程场景输入为空时你的代码能不能正确返回数组长度为1时逻辑是否正确所有数字都相同时排序和去重的逻辑是否还成立最大值、最小值、负数、0、空串这些极端输入是否都考虑到了循环中是否有自增运算符的边界越界风险这些问题不会花太多时间但真的能拦住大部分Runtime Error和Wrong Answer。我把这套检查清单用了很多年每次笔试都靠它兜底。5.3 从四模到正式笔试这套题教会我的三件事第一件事是审题比做题重要。2017年的四模题目普遍偏长如果只看最后一句“输出XXX”很容易漏掉“数组可能包含重复元素”“不需要保持原有顺序”这类关键约束。我现在做任何题都会先高亮题目里的“约束条件”部分再开始写码。第二件事是写完比写完得漂亮重要。牛客OJ只认输出结果对不对不认代码风格好不好。在时间紧张的情况下先用最直接的方法把题过了后面有剩余时间再优化。不要为了追求O(n)解法在一道O(n^2)就能过的题上耗太久。第三件事是复盘比刷题量重要。做完这套模考我没有急着做下一套而是把每一道题的思路、踩过的坑、用时数据都记录下来整理成一个表格。一个月后回头看这些记录再重新做一遍这四道题能明显感受到自己审题速度和代码稳定性的提升。这个习惯我保持至今。最后再分享一个小技巧牛客的模考题即使过了也值得在提交记录里看看别人的解法。我当年就是在“区间合并”这道题的讨论区里学到一个用差分数组实现区间覆盖次数的巧妙思路从那以后遇到类似的“活动安排”类问题都轻松很多。做题不是为了提交那一刻的快感而是为了下一题能更快地想通。