2018牛客模考二模编程题复盘：高频题型与解题思路

2018年那会儿牛客模考是校招季绕不开的一个词。二模这套编程题我在备战秋招时反复刷过不止一两遍后来面了几家公司发现不少笔试题目都能在这套题里找到影子尤其是对基础数据结构和边界条件的考察方式几乎成了我后续刷题的对照基准。今天就把这套题重新拆一遍把每类题型背后的解法思路、实现代码和实测时容易翻车的细节一起整理出来给正在备战笔试的朋友一个可以直接拿去对照的参考。很多人可能觉得2018年的题太老没什么时效性但实际做过一轮就会发现校招笔试的题型演进是很慢的字符串处理、贪心区间、动态规划、双指针这几大类至今仍是主流而且二模这套题的整体难度和真实笔试现场非常接近没有偏题怪题几乎每题都在考“基本功边界意识”。这也是我愿意花力气复盘它的原因。1. 2018年牛客模考二模的题风与备考定位1.1 当时的笔试生态为什么二模值得反复复盘2018年的校招笔试有一个很明显的特征线上OJ平台已经完全普及牛客、赛码这些平台成为各大公司笔试的主力载体。题目风格上不再像早几年那样偏重“脑筋急转弯”式的小智力题而是转向了算法与数据结构的硬功夫测试但又不至于像ACM竞赛那样高门槛难度卡在“认真准备能AC裸考就挂”的临界点上。二模这套题就是典型的这种风格。它不会考你过于冷门的算法比如后缀自动机、网络流这些也不会给一个明显不可能的复杂度要求让你为了满分去写奇技淫巧。它考的就是那几类高频题型字符串、数组、贪心、DP、简单搜索和数学规律。这种出题思路其实和面试官的心理高度一致——他们想确认的是你有没有扎实的编码功底能不能在有限时间内把思路转成干净、无bug、效率达标的代码。所以我的建议是即便你手头已经囤了最新年份的题库也不要跳过这套老题。它非常适合用来做“基线测试”——先限时做一遍看自己在哪些题型上容易卡壳再用我做题解里的思路去对照找出自己思考链路里的漏洞。这个价值远不是刷几道新题能替代的。1.2 二模编程题的整体难度分布与考点结构从题型分布来看二模的编程题大致可以归成几个梯队我按个人做题时的体感做了个分层方便你快速定位自己的薄弱点考点类别常见出题方式难度体感核心考察能力字符串/模拟压缩、反转、子串统计、按要求重排偏易至中等边界条件控制、代码稳健性贪心算法区间覆盖、跳跃问题、任务调度中等贪心策略证明、排序预处理双指针/滑动窗口连续子序列、去重、区间最值中等指针移动的时机判断动态规划子序列、路径计数、状态转移中等偏难状态定义、转移方程推导二分答案最大化最小值、查找满足条件的解中等偏难单调性判断、check函数设计基础数据结构栈、队列、链表操作偏易API熟练度、边界判断这里要注意一个细节难度体感是“相对二模这个环境”来说的。放在真实笔试里同一道题会因为环境紧张、时间压缩而被感觉得更难。所以我复盘这套题时除了给出正确解法更关注那些“一看就会、一写就错”的隐性细节这些才是真正拉开分数差距的地方。2. 从二模里提炼的几类常考题型与完整题解2.1 字符串压缩题考的不是压缩是边界和恢复策略二模里有几道字符串相关的题其中一道“字符串压缩”让我印象很深。题目要求并不复杂给定一个只包含大小写字母的字符串把连续出现的相同字符压缩成“字母出现次数”的形式。比如aabcccccaaa压缩后应该是a2b1c5a3。拿到这类题很多人的第一反应是遍历一次碰到相同字符就计数器加一。这个思路没问题但翻车点往往出在“收尾”阶段——字符串最后一段连续字符很容易在循环结束后被漏掉。看下面这份比较典型的初版实现def compress_string(s: str) - str: if not s: return res [] count 1 for i in range(1, len(s)): if s[i] s[i - 1]: count 1 else: res.append(s[i - 1] str(count)) count 1 # 循环结束后最后一段字符还没有写入结果 res.append(s[-1] str(count)) return .join(res)我特意在代码里留了注释。这个版本的思路是每次检测到前后字符不同就把前一个字符和它已累计的次数写入结果。循环结束后再把最后一段字符补上。这里的边界意识是核心如果少最后那一行res.append(s[-1] str(count))aaabbb就会输出a3直接把bbb丢掉。但这道题里还有一个更隐蔽的坑如果要求压缩后的字符串长度不小于原串应该返回原串。比如abc压缩后是a1b1c1长度反而变长了按题意需要原样返回。这是典型的“题目里藏了附加条件”的考法稍不留意就会失分。完整解法可以这样写def compress_string(s: str) - str: if not s: return compressed [] count 1 for i in range(1, len(s)): if s[i] s[i - 1]: count 1 else: compressed.append(s[i - 1] str(count)) count 1 compressed.append(s[-1] str(count)) result .join(compressed) return result if len(result) len(s) else s时间复杂度是 O(n)空间复杂度也是 O(n)这里没有再优化的空间也不应该为了省空间写出一个错漏百出的版本。实测下来的体会是这类题考察的其实就是“遍历到边界时你的代码有没有完整的收尾逻辑”。很多同学不是不会写而是写完自测时只看了示例输入样例过了就觉得万事大吉结果一提交就挂在a、aaaa、空串这类极端用例上。建议自己额外准备一个空串和单字符用例养成这个习惯之后很多字符串题的通过率都能直线上升。2.2 最长连续递增子序列双指针和状态转移两种解法的取舍另一类高频题是“最长连续递增子序列”。题目大概是给定一个未排序的整数数组找到最长连续递增子序列的长度要求子序列中的元素在原数组中必须是连续的。比如[1, 3, 5, 4, 7]答案是 3对应的子序列是[1, 3, 5]。注意这里不是最长递增子序列LISLIS 不要求连续而这题明确要求连续所以它其实是个“双指针/一次遍历”的简单题。但简单归简单它的实现思路又有点讲究。最直接的做法是用一个变量记录当前连续递增序列的长度从左到右扫描数组遇到nums[i] nums[i - 1]就继续累积否则重置为 1同时不断更新答案def find_length_of_lcis(nums): if not nums: return 0 ans 1 cur 1 for i in range(1, len(nums)): if nums[i] nums[i - 1]: cur 1 else: cur 1 ans max(ans, cur) return ans这份代码已经能正确通过。但我更想讨论的是为什么很多人会顺手把它写成动态规划因为看到“最长递增子序列”这几个字第一反应就是 LIS 的经典 DP 解法。这两个问题的唯一区别就在“连续”两个字上。LIS 的状态转移需要回头看前面所有比当前值小的位置复杂度是 O(n^2)还有一版二分优化到 O(n log n)而连续递增子序列因为要求连续当前位置的最优长度只依赖前一个位置所以本质上只需要 O(n) 的扫描连 DP 数组都可以省掉。这里有一个很实用的做题经验拿到题目第一步不要急着套算法模板先圈出题目里的限制词。是“连续”还是“不连续”是“子数组”还是“子序列”这两个词的差别直接决定了算法设计的方向。我见过不少人把这题当 LIS 去做交上去能过还好过不了还回来问我为什么 —— 其实就是没有意识到连续条件下更优解的存在。去牛客搜这套题的时候还会有个有意思的现象同一年不少公司在线笔试里出现了完全一样的题面只是换了个叙述方式。这侧面说明这类基础题就是校招笔试的基本盘值得反复练到闭眼都能写。2.3 跳跃游戏最少步数贪心出发时机判断的经典例子二模里还有一道“跳跃游戏最少步数”的变体。题面大致是给定一个非负整数数组你最初位于数组的第一个位置数组中的每个元素代表你在该位置可以跳跃的最大长度目标是到达最后一个位置问最少需要跳多少次。保证总是可以到达最后一个位置。这道题最经典的贪心解法是“反向跳”和“正向贪心”两种。反向跳的思路很直观从终点出发每次向左寻找一个能一步跳到当前位置的最远点。这个思路的时间复杂度是 O(n^2) 的因为每个位置都可能要往前扫一遍。更好的正向贪心只需要一趟遍历def jump(nums): n len(nums) if n 1: return 0 max_reach nums[0] # 当前这一步能跳到的最远位置 steps 1 # 当前用掉的步数 end nums[0] # 当前步数覆盖范围的右边界 for i in range(1, n): if i end: # 说明上一步的覆盖范围已经用尽必须再跳一次 steps 1 end max_reach max_reach max(max_reach, i nums[i]) return steps这段代码的核心逻辑是维护两个关键变量end表示当前步数能覆盖到的范围末端max_reach表示在这段范围内遍历时能看到的下一步最远位置。当i越过end时说明必须消耗一步把end更新为max_reach。很多人的疑问是为什么不等循环结束再更新steps而是在遍历过程中更新这里的关键在于“贪心”的触发条件不是等所有位置都访问完而是等当前波次的边界被突破。这就像冲锋时的接力棒跑完当前这段距离后马上从后面的人手里拿过新接力棒而不是等整条赛道跑完才结算。这题在2018年的二模里有一定区分度少数人能写出反向跳的 O(n^2) 版本但很多人写正向贪心时会把end和max_reach更新顺序搞反导致结果要么多算一步要么少算一步。一个非常有效的自测方法是准备[2,3,1,1,4]答案是 2和[1,2,1,1,1]答案是 3这两组数据如果都能过基本就稳了。2.4 区间覆盖最少区间数贪心处理排序类问题的常见陷阱区间类贪心题是二模的常客尤其是“用最少的区间覆盖目标区间”这个模型。大致的题面是给定一个目标区间[start, end]再给若干个小区间每个区间用[l, r]表示用最少的区间数覆盖目标区间输出最少区间数。这类题的经典贪心策略分三步走把所有小区间按左端点升序排序遍历区间维护一个current_right表示当前覆盖到的最右位置在能覆盖current_right的前提下选择右端点最远的区间如果某个区间的左端点已经大于current_right 1说明出现断层无法完成覆盖。这个策略本身不复杂但实现时有一个很常见的坑排序之后遍历过程中“选哪个区间作为下一次延伸”的判断逻辑很多人会写错。看下面这个参考实现def min_cover_intervals(intervals, start, end): intervals.sort(keylambda x: x[0]) current_right start count 0 i 0 n len(intervals) while current_right end: farthest current_right # 找出所有能接上当前覆盖范围的区间取右端点最远的 while i n and intervals[i][0] current_right: farthest max(farthest, intervals[i][1]) i 1 if farthest current_right: # 没有找到能延伸的区间说明出现断层 return -1 current_right farthest count 1 return count注意内层while的条件intervals[i][0] current_right意思是只要区间左端不超过当前覆盖的右边界就可以用来延长覆盖范围。然后从这些候选中选出右端点最大的区间。如果farthest没有变化说明接不上直接返回 -1。这里为何要“取右端点最远的”而不是“取长度最大的”因为目标是覆盖满整个目标区间每次延长覆盖右边界右端点越远越有利。直觉上“长度最大”似乎也行但两个区间起点不同长度大可能只是因为它起点靠左实际上右端点并不是最远。这个区别在数据一多就会显现出来。另外补充一个关于区间端点是否闭合的细节有的题目要求区间连续全覆盖比如[1,3]和[4,6]可以覆盖[1,6]有的题目则严格要求[1,3]和[3,6]才能无缝衔接。到底用的是 current_right还是 current_right需要看题目里区间的开闭语义这也是一个很容易被忽略的隐藏条件。3. 复盘二模时最容易翻车的三个编程细节3.1 输入输出格式的坑样例能过但评测系统全挂2018年牛客模考用的是类似OJ的评测系统输入输出格式非常严格哪怕最小的一点偏差都会导致“答案错误”或者“非零返回”。我复盘自己当年和身边同学的交战记录时发现以下这三个输入输出细节最坑多组数据 vs 单组数据。很多题目不会明说“输入包含多组测试数据”而是样例只给一组但后台评测会一次塞多组。如果不写成while True: try: ... except EOFError: break的处理方式第二组数据根本不会被读到。空白字符的处理。Python 用input()读一行字符串时会自动去掉末尾换行符但不会去开头和中间的空格、Tab。如果题目给的一行数据末尾有多余空格直接split()一般没问题可如果题目要求整个字符串原样处理就要考虑strip()到底该不该用。比如字符串压缩题输入带个首尾空格压缩完要不要保留不同题目要求不一样。输出格式。有的题要求每组结果之间空一行有的要求最后一行没有多余空格。这类细节在样例里通常会给但紧张时人往往会直接照抄示例输出格式忽略“最后一组后面是否也要输出分隔符”的区别。我自己当年就因为没处理多组输入一道二分的题丢了将近一半的分数。从那以后每道题拿到手我先看输入描述里有没有“多组”“以EOF结束”“多行数据”这些关键词再动手写读取逻辑。这个习惯帮我省下了很多无谓的因为 IO 格式扣分。3.2 复杂度估算错误逻辑对也不能AC二模的编程题有个特点它不会在题目里明确告诉你数据规模但你通过输入描述通常能猜个大概。比如数组长度会写成1 n 10^5这种规模下 O(n^2) 的算法在 Python 里即便逻辑正确也基本跑不过。当年我写那道“跳跃游戏最少步数”时第一版用了反向贪心因为是 O(n^2)自测数据没问题但后台评测里有一个很大的测试点直接超时。这是刷题时最容易被忽略的一层你以为的“正确解法”和“合格解法”之间隔着一个复杂度。对 OJ 来说逻辑正确只是第一步时间限制才是真正的门槛。先估算数据规模再确认算法复杂度最后再落笔是做任何笔试题都应该刻在脑子里的流程。尤其当题目数据规模到 10^5 级别时你脑子里应该自动弹出“O(n log n) 以内”的警戒线。一个通用建议把常见的几组复杂度量级和对应可处理的数据规模记清楚。n10^5 时 O(n^2) 要跑 10^10 次运算Python 必挂O(n log n) 很稳n10^3 时 O(n^2) 勉强能接受但超过两层循环也要谨慎。养成这个复杂度敏感度后你会发现自己写代码时自然会去挑更优的算法而不是先写个能跑的再说。3.3 边界条件遗漏空串、单元素、满区间边界条件是我再强调都不为过的一环。二模的题不算偏难但出题人非常喜欢在边界上埋雷。就前文提到的四类题字符串压缩空串、单字符、所有字符都想同最长连续递增子序列空数组、单元素、全递增、全递减跳跃游戏单元素数组、最大步数正好够到终点、每一步都是1区间覆盖区间刚好覆盖满、区间有重叠、区间完全无交集、目标区间本身就是空的。这些都是可以秒杀一批代码的测试点。我的方法是每次写完核心逻辑后强制自己列一个“边界用例清单”至少把下面的表格在大脑里过一遍题目类型必测边界预期结果字符串压缩空串 / 单字符 / 全部相同空串 / 原样 / 单字符数字连续递增序列空数组 / 单元素 / 全降序0 / 1 / 1跳跃游戏长度为1 / 刚好跳最后一格0 / 最小值区间覆盖空区间 / 断层 / 满覆盖0 / -1 / 最少区间数这个清单可以随着刷题量不断增加。花五分钟写几个边界用例比提交后对着“通过率 0%”发呆半小时要值太多。4. 从二模成绩到笔试现场一套可复用的答题节奏4.1 拿到题目先做两分钟“人工编译”很多同学在笔试时是“读题即写码”看完题面觉得有思路就开始敲键盘结果写着写着发现逻辑漏洞再删掉重来一来一回浪费大量时间。我在复盘二模时发现一个特别高效的替代方案先花两分钟用自然语言把整体思路讲一遍在脑子里跑一遍边界和特殊情况再动手写代码。这个“人工编译”的过程看起来多花了两分钟实际上能帮你避开至少一半的重写时间。因为在口述思路时你会逼自己去想这个循环的退出条件到底写在哪如果输入为空会发生什么用什么数据结构来记录中间状态这些问题在写代码时才发现就晚了但先想清楚再写代码往往一遍过。当你拿到一套题第一件事不是写代码而是先给每道题打一个难度评估标记把有把握的题先做了拿分把卡壳的题放到后面慢慢啃。这个排序策略比“按题号顺序做”要合理得多因为大部分OJ平台是按通过率计分的不会因为你先交就先给分。4.2 自测用例的设计方法不能只会跑样例二模的样例通常只有一个或两个远远不够用来验证代码的正确性。更离谱的是有时候样例全过了但提交上去全错。原因很简单样例只是出题人精心挑选的“正向路径”是为了展示题意的不是用来证明你代码正确的。我自己设计用例有一个三层递进的方法。第一层构造最朴素的正常输入看基本逻辑对不对。第二层构造边界输入——空、单元素、最大值、最小值、全相同、交替变化这一层能过滤掉大部分边界问题。第三层构造能触发特殊逻辑分支的输入比如跳跃游戏里“刚好跳到终点”“提前越过终点”“步数不够”等情况专门去撞你代码里的条件分支。这个方法听起来简单但真正执行的人不多。很多人写完代码只跑一遍示例通过了就交卷剩下全靠系统评测帮他验错。等到系统告诉你错了你再回来找问题既费时间又费心态。与其这样不如提前做三层自测一套下来也就多花三五分钟。4.3 笔试现场的时间分配建议把80分钟的编程题拆成40402018年牛客模考二模的编程题数量我记得是四到五道限定时间内全部AC几乎不可能但拿到大部分分数是能做到的。我的策略是把所有题先扫一遍用五分钟给题目排个难度序把前40分钟砸在最简单和次简单的两道题上确保它们AC后40分钟再集中对付中等难度题做不出来就写个暴力解法至少拿到部分通过率。这里我要特别提一个很多人踩过的坑不要在“看起来可能很简单”的题上死磕。人的思维是有惯性依赖的一旦你把大量时间投在没做出来的题上后面原本能拿分的题也会因为心态波动而失误。我当年二模就在一道字符串处理题上耗了太久最后最简单的跳跃题反而没写完。后来我给自己定了个死规矩单题卡超过20分钟立即切换除非你确定全卷没有更简单的题了。代码风格方面考场上的代码不需要花哨但变量命名和注释一定要清晰到“自己隔十分钟再看还能读懂”。因为万一需要回头调试一份能看懂的代码比一份写了一堆i、j、k的旧代码要省时太多。写几个关键的注释说是最被低估的考场习惯也不为过。5. 回头看二模这套题给后来人的三点建议第一刷题复盘一定要按题型归纳而不是按提交顺序一条道走到黑。2018年二模的题其实可以归类成不到十个模型真正吃透每个模型背后的思路变化比盲目做一百道新题有效得多。我后来把牛客模考整套题刷完收获最大的不是记住了每道题怎么写而是建立起了一套“看到题 → 识别题型 → 套对应模板 → 自查边界”的思维链路。第二代码的边界意识和复杂度意识是校招笔试里性价比最高的两项能力。它们不需要你掌握多少高深算法只需要你在做题时多问自己一句这个输入为空怎么办这个数据规模下 O(n^2) 能不能撑住就这么一句就能把很多“半吊子”代码堵在提交之前。第三用老题去碾压新题心态上会有一种奇妙的从容感。当你发现自己能把三年前的题快速拆解干净时面对新题时的那种紧张感会明显降低。这也是我强烈推荐你把牛客模考二模这套老题留在笔试前两周冲刺用的原因——它足够经典又足够有代表性能帮你把状态调整到“见到任何题都不慌”的频率上。最后再分享一个我后来养成的习惯每次刷完一套模拟题不管分数高低我都会花十分钟把错题和卡壳的题重新整理一遍写清楚卡住的环节是什么是思路断层还是边界遗漏还是复杂度不够。这个整理过程比多刷三套新题都更能带来实打实的提升。