每年三四月份牛客网的模考一出来群里就炸锅。2017年那次一模我印象特别深那会儿我还在学校刚刷完剑指offer觉得自己行了结果被一模编程题教做人。现在回头看那套题其实一点也不偏反而特别能反映笔试编程题的核心套路——字符串处理、贪心、动态规划、模拟全是这些东西。这几年我帮学弟学妹改简历、做模拟面试发现大家刷题有个通病光顾着刷量不研究题目背后的设计逻辑。所以今天想借2017牛客模考一模编程题集合这个经典样本把笔试编程题的解题思路完整拆一遍包括题目考点、常见陷阱、代码实现以及我当时踩过的坑和总结出的应考节奏。这套题适合谁两类人。第一类是准备秋招春招的应届生尤其是投后端、算法、测试开发这些要考编程题的岗位第二类是刚刷完基础题、想检验自己水平的大二大三学生。如果你已经工作但想跳槽也可以拿它当热身。文章不会只给答案我会把每道题的思考过程、为什么这么解、换一道类似的题怎么识别考点都讲清楚。1. 2017一模整体的题目设计思路1.1 题型分布与难度曲线先看整体盘子。牛客模考编程题通常四道左右2017年一模的难度分布大致是一道简单字符串、一道中等模拟、一道贪心、一道动态规划。这个配置几乎成了之后几年校招笔试的模板到现在很多公司的笔试题还是这个比例只不过难度整体抬高了。为什么出题人这么安排很简单考查覆盖面。字符串是基础编码能力的试金石模拟题考代码组织能力和状态梳理能力贪心考思维敏锐度动态规划考算法功底。四道题分别对应不同维度能把候选人的水平拉开层次。如果你只擅长某一种题大概率会被卡住。再具体一点难度曲线是前松后紧。第一道题基本是送分题保证大部分人能上手写第二道题稍微绕一点需要理清逻辑第三道和第四道是分水岭决定了你能不能进下一轮面试。很多人栽在第三道贪心题上不是不会而是没看出来这是个贪心——这是最可惜的失分方式。我建议拿到题先花两分钟扫一遍所有题目不要从第一题按顺序做。先把送分题做了再跳到你最有把握的中等题最后啃难题。这个策略我在后面章节会详细讲。1.2 为什么这套题现在刷依然不过时有人可能觉得2017年的题太老了现在面试都不考这些。这话对了一半。新技术框架确实日新月异但笔试编程题考的是算法和数据结构基础这东西十年二十年不会变。2017年考最长上升子序列2025年还在考2017年考区间调度贪心现在依然是大厂高频题。而且2017年这套题有个好处它处在牛客模考这个体系的早期题目风格还没被各种培训机构研究透所以题目更纯粹没有太多偏题怪题。现在的笔试题反而经常出现一些为了难而难的题目动不动就上后缀自动机、树链剖分对校招生来说反而失去了选拔意义。所以拿这套题打基础性价比很高。我每年带新人刷题都会让他们先把这套题做一遍目的不是让他们背答案而是让他们感受一下一个正常难度的笔试是什么样。做完这套题再去刷那些偏难怪题心里就有底了。1.3 一道题的完整估值模型刷题不能傻刷你得知道每道题大概花多长时间是合理的。我自己的标准是第一道简单题控制在5分钟以内中等题10到15分钟难题如果20分钟还没有思路果断放弃或者写个暴力解法先拿部分分。这个时间估值基于一个简单的公式笔试总时长除以题目数量再考虑难度加权。比如一共90分钟四道题平均每道22.5分钟但简单题不应该用满这个时间省下来的时间得补给难题。很多人栽就栽在简单题上死磕最优解结果难题连暴力分都没拿到。2017年一模我当时就犯了这错误。第一道字符串题明明用最基本的遍历就能AC我非要优化成O(n)空间复杂度的花活结果折腾了二十分钟后面贪心题只能草草写个错误答案交上去。笔试不是给你炫技的是让你拿分的。2. 高频考点拆解字符串与模拟题2.1 回文串判定的三种写法字符串题是笔试的常客2017一模第一道题就是回文串相关。题目大致是给定一个字符串判断它是否是回文串忽略空格和标点且不区分大小写。听起来很简单对吧但越简单的题越容易暴露出编码习惯问题。最稳妥的写法是双指针——一个指向开头一个指向结尾跳过非字母数字字符然后比较。这个方法时间复杂度O(n)空间复杂度O(1)既不依赖额外的数据结构也不容易出错。def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: while left right and not s[left].isalnum(): left 1 while left right and not s[right].isalnum(): right - 1 if s[left].lower() ! s[right].lower(): return False left 1 right - 1 return True第二种写法是逆序比较先把字符串清洗干净再反转然后逐位比较。这个思维最直白但多了一次字符串拷贝空间复杂度O(n)。第三种写法是递归不推荐在笔试里用容易栈溢出而且代码还长。这里有个小坑很多人会踩if s[left].lower() ! s[right].lower()注意是用lower()统一大小写而不是直接比较。还有内层跳过非字母数字的while循环要加left right条件不然可能越界。这些细节在IDE里有提示但在牛客这种不帮你检查越界的在线编辑器里可能直接报错。2.2 字符串压缩与解压的边界处理另一道高频字符串题是压缩给定一个字符串把连续重复的字符压缩成字符次数的形式比如aaabbc压缩成a3b2c1。这题考的是对连续区间的处理跟统计词频是同一类思路。def compress(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)这题有两个边界必须处理好。第一个是空串输入直接返回空串不然s[-1]会越界第二个是最后一个字符的统计——很多人循环里只处理了前后字符不同的情况忘了把最后一组追加进去。这两个问题我每次改卷子都能看到说明不是个例是普遍习惯问题。还有一个优化的点如果压缩后的字符串不比原串短应返回原串。这个要求源自LeetCode 443的变体牛客的题也常这样出。加上这个判断后代码要多一层逻辑def compress(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)) compressed .join(res) return compressed if len(compressed) len(s) else s这种题本身不难但要拿满分边界条件一个都不能漏。我强调这些是因为笔试判分的时候很多case就是针对边界条件设计的——你功能逻辑全对但空串没处理照样WAWrong Answer。2.3 模拟题的通用思路状态机思维模拟题是2017一模的第二道也是很多人的噩梦。那道题大概是模拟一个简化版计算器输入一个只包含数字、、-、*、/的表达式输出计算结果。这种题不考算法考的是对过程的拆解能力。我做模拟题有个固定套路先画状态机。状态就是当前正在读什么——可能是数字、可能是运算符、可能是操作符之后的下一个数字。每一次读入一个字符根据当前状态决定下一步动作。把这个状态流转画清楚代码就是状态机的直译。比如计算器表达式求值核心是处理优先级。经典做法是用两个栈一个操作数栈一个运算符栈。遇到运算符时如果栈顶运算符优先级不低于当前运算符就先弹出运算再把当前运算符压栈。这个弹栈计算的过程就是状态机里读到运算符时进入结算状态的落地。def calculate(s: str) - int: stack [] num 0 sign for i, ch in enumerate(s): if ch.isdigit(): num num * 10 int(ch) if ch in -*/ or i len(s) - 1: if sign : stack.append(num) elif sign -: stack.append(-num) elif sign *: stack.append(stack.pop() * num) elif sign /: stack.append(int(stack.pop() / num)) sign ch num 0 return sum(stack)这里有个Python特有的坑int(stack.pop() / num)和stack.pop() // num结果不一样。比如-3 // 2在Python里等于-2因为Python的整除是向下取整而题目通常想要的是向零取整。所以必须写成int(-3 / 2)得-1。这种语言层面的细节笔试中不会有编译器提醒你只能靠平时积累。模拟题拿高分的核心就一句话先把规则梳理成清晰的流程再写代码。我见过太多人上手就写写到一半发现少处理一种情况又回头改结构最后代码跟意大利面一样——能跑但没人敢保证它是对的。花三分钟整理流程能省下三十分钟改bug的时间。3. 贪心与动态规划那两道分水岭题目3.1 区间调度贪心的证明思路2017一模的第三道题是会议室安排问题变种给定一组区间找出最多能选择多少个互不重叠的区间。这题是贪心算法的经典入门题也是面试官最爱问的题之一——因为它表面上是安排实际上是考你是否理解贪心策略背后的选择逻辑。最经典的解法是按区间结束时间排序然后依次选择只要当前区间开始时间不早于上一个选中区间的结束时间就选中它。排序复杂度O(n log n)选择过程O(n)。def max_non_overlapping(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return count很多人会问为什么按结束时间排序而不是按开始时间或者区间长度这个问题的答案才是面试官真正想听的。按结束时间排序保证了每次选择都给后面留下尽可能大的剩余空间这是贪心选择性质的直观理解。形式化证明是交换论证法假设最优解的第一个区间不是结束时间最早的可以把最优解的第一个区间替换成结束时间最早的区间其余部分不受影响因此存在一个包含结束时间最早区间的最优解。这个证明思路我建议背下来因为很多贪心题的证明套路都长一个样。笔试虽然不要求写证明但理解证明能帮你在面对变形题的时候判断这题是不是贪心。3.2 最长上升子序列的DP推导最后一道题是经典的动态规划——最长上升子序列LIS。题目给一个无序数组求最长严格递增子序列的长度。子序列不要求连续但要保持原数组顺序。看到最长加子序列这两个词第一反应就应该是DP。状态定义dp[i]表示以nums[i]结尾的最长上升子序列长度。转移方程dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。初始状态dp全为1每个元素自身构成一个长度为1的子序列。def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)O(n^2)的解法是最容易实现也最不容易出错的。但面试或笔试如果限时较紧可能会希望你会O(n log n)的优化版——用贪心加二分维护一个tails数组其中tails[k]表示长度为k1的上升子序列末尾元素的最小值。具体不展开网上很多资料。我想强调的是先写对再写快。如果O(n^2)的思路清晰就按O(n^2)写不要为了炫技写二分然后因为边界条件出错。笔试是看AC的题数不看复杂度多漂亮。3.3 怎么快速判断一道题该用贪心还是DP这是个困扰许多人的问题。我的判断标准是贪心是每一步做局部最优选择DP是考虑所有可能状态并取最优。如果题目有每一步可以做出一个选择选择后整个问题变成一个更小的同类型子问题的结构很可能贪心如果题目有多种方式组合成答案需要把所有情况都考虑到的结构那是DP。举个例子区间调度按结束时间排序是贪心因为每选一个区间后问题就缩小成从当前结束时间之后找最大数量区间而且选择结束时间最早的区间永远不比选择其他区间差。而LIS不是贪心——你不能说选最小的那个数一定最优因为子序列的构成要考虑顺序所以必须枚举所有可能性用DP。还有一个典型的区分题找零钱问题。如果用无限量硬币凑出某个金额求最少硬币数先用最大面值硬币不一定最优比如面值1、3、4凑6先拿4再拿11是3枚但33只要2枚所以这题不能用贪心得用DP。但如果是面值1、5、10、25美分贪心反而最优。原因是这些面值满足贪心选择性质。所以判断标准不是看起来能不能贪而是局部最优是否真的能推出全局最优。4. 真题实战两道完整的解题过程4.1 题目最小覆盖子串的滑窗实现虽然不是2017一模的原题但滑动窗口这类题在牛客模拟中反复出现一模也有一道变种。我拿一道典型题来讲完整流程给定一个字符串S和一个模式串T在S中找到包含T所有字符的最短子串。这题是滑窗的经典场景。思路分五步走。第一步用字典need记录T中每个字符的需求量第二步用两个指针left和right表示窗口边界第三步移动right扩展窗口同时更新窗口内字符计数第四步当窗口内已包含T全部字符时尝试移动left收缩窗口记录最短长度第五步重复直到right遍历完整个S。def min_window(S: str, T: str) - str: from collections import Counter if not S or not T: return need Counter(T) remain len(T) left 0 min_len float(inf) min_left 0 for right, ch in enumerate(S): if need[ch] 0: remain - 1 need[ch] - 1 while remain 0: if right - left 1 min_len: min_len right - left 1 min_left left left_ch S[left] if need[left_ch] 0: remain 1 need[left_ch] 1 left 1 return if min_len float(inf) else S[min_left:min_left min_len]这个代码里最关键的是remain这个变量。它表示还没满足的T中字符个数只有当窗口内某个字符是T需要的且当前数量不足时remain才会减一。这个设计比每次都比较两个Counter要高效得多也避免了重复计算。我实战中常犯的错误是在收缩窗口时忘了恢复need计数。每次移动left必须把对应字符的需求量加回来否则窗口内字符计数会越来越小导致误判。这个bug特别隐蔽因为小数据量可能测不出来但大数据量就会出现明明包含T的字符却显示不包含的诡异现象。4.2 题目最大连续子数组和的两种解法另一道常考的题是最大连续子数组和也就是LeetCode 53。题目很简短给定一个整数数组找出一个具有最大和的连续子数组返回其最大和。看似简单但它既可以用DP解也可以用分治法解是考察基本功的好题。Kadane算法是这题的最优解cur max(num, cur num)result max(result, cur)。一维DP的压缩版空间O(1)时间O(n)。def max_subarray(nums): cur nums[0] result nums[0] for num in nums[1:]: cur max(num, cur num) result max(result, cur) return result理解这个算法的关键是cur的语义以当前位置为结尾的最大连续子数组和。为什么是max(num, cur num)因为要么从当前元素重新开始要么接着前面的连续段。很多人在这一步纠结如果前面的连续段本身就小于0怎么办——max(num, cur num)已经处理了这个情况如果cur是负数加上num反而不如直接取num大所以自动选择重新开始。分治法解法也值得掌握把数组分成两半最大子数组要么完全在左半要么完全在右半要么跨越中点。前两种情况递归解决跨越中点的情况需要从中点向两边扩展找最大和然后三取一。复杂度O(n log n)虽然不如Kadane但分治思想在很多进阶题里都会用到建议写一遍加深理解。4.3 完整调试与自测的实操记录来说说我当年在牛客上做这类题的真实过程。写完之后我不会直接提交先自己构造几组测试用例跑一遍。第一组是最简单的正常情况比如[1, 2, 3]第二组是全负数比如[-1, -2, -3]这组最容易暴露初始值没设好的问题第三组是混合正负比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]。每组用例都要在纸上先算好预期输出再跑到代码里验证。全负数这个用例特别关键。很多人Kadane算法初始化cur 0结果全负数数组会错误地输出0。正确做法是初始化cur nums[0]或者cur float(-inf)再遍历。我在牛客上见过太多人因为这一个小问题写对了80%的逻辑但提交直接WA。自测的时候还有一个技巧故意加一个大规模随机数组来压测。不是检查正确性而是看时间复杂度是否够快。如果O(n^2)的解法跑到10万数据量会卡住那就趁早换思路。笔试环境一般有性能监控超时也算错。5. 牛客笔试中的失分点与排查技巧5.1 输入输出格式的坑牛客笔试和LeetCode最大的区别就是牛客要自己处理输入输出LeetCode只需要实现函数。这个差异让很多人吃了大亏。最常见的问题是读入数据时类型不对——比如题目说第一行一个整数n第二行n个整数你按字符串读进来忘了转int自然全错。牛客输入模板我建议形成肌肉记忆。整数数组data list(map(int, sys.stdin.readline().split()))。多行输入以EOF结束for line in sys.stdin: ...。字符串s sys.stdin.readline().strip()。这些模板不花什么技术含量但能避免大量低级错误。还有一个很隐蔽的坑输出格式。要求每个结果占一行你正确输出了结果但忘了换行——这种情况通常不会判错但如果要求用空格分隔而你在末尾多打了一个空格有些严格的判题系统会报Presentation Error。虽然不算WA但零分和全分之间就差了这一个空格很冤。5.2 边界条件速查表我总结了一个笔试前必看的边界条件清单每个题目类型对应几个必测的边界题目类型必须测试的边界条件数组类空数组、单元素数组、全相同元素、全负数字符串类空串、单字符串、全空格串、大小写混合二叉树类空树、只有左子树、只有右子树、单节点动态规划n0、n1、n2、目标值等于边界值数学类零、负数、最大整数、溢出场景别觉得这些是废话。我在牛客上看到的最多报错就是数组越界和空指针异常全是边界条件没处理干净。特别是递归和DP类题目n0的时候dp数组初始化为[0] * n输出时越界n1时循环根本不执行有些变量没被赋值——这些问题在提交前自己先测一遍就能发现。5.3 时间复杂度的经验判断笔试经常会碰到题目说数据范围n10^5你的算法跑了O(n^2)的情况。一套下来肯定超时。我平时判断能否通过有一个粗略经验表数据量10^5O(n log n)大概是1秒上下O(n^2)直接是分钟级别数据量10^4O(n^2)勉强能过但O(n^3)就别想了数据量10^3O(n^2)很轻松O(n^3)可能危险。如果时间不够优化至少写个暴力解拿部分分。有些题目的判分规则是多个测试点每个测试点有一定分值暴力解能过其中一部分小的case。千万别空着空着连同情分都没有。我曾亲眼见过有人四道题只AC两道但第三题写了个暴力拿了40%的分数最后总分比三道题满分的人都高——因为难度越大的题别人越可能完全做不出来。5.4 笔试现场的调试策略在线笔试通常没有调试器你只能用print大法。但print不是随便打的要有技巧。我自己的习惯是先打印最关键的状态变量——循环的起点、终点、中间结果然后再打印循环内部每个分支的走向。比如DP题我会在每次状态转移之后把dp数组打印出来看变化趋势如果某个值不对根据dp的变化能立刻定位是转移方程写错还是初始化写错。比盲目打印所有变量高效得多。还有一个小技巧不要把print留在最终提交的代码里。很多人调试完忘了删结果满屏调试输出直接判错。我习惯在提交前用CtrlF搜一下print确认没有调试语句才提交。6. 基于2017一模的备考建议与刷题节奏6.1 三轮刷题法如果离笔试还有一段时间我建议用三轮刷题法来准备。第一轮是分类刷把所有高频考点各刷10道左右目标是形成条件反射——看到最长想DP看到区间想贪心看到字符串匹配想滑窗第二轮刷整套模拟卷每周一套目标是训练时间分配和手感第三轮是回顾错题重点是把自己反复错的题目类型重做一遍。三轮之间不是递进关系而是有交叉的。分类刷的时候也可以偶尔抽一套完整卷子来检验做整套卷子的时候遇到不会的题回归到对应知识点去补课。这样周而复始效果比闷头刷题好得多。2017一模就是很适合做第二轮刷题练手的卷子。因为它难度适中题型分布均匀不会像一些大厂真题那样一开始就被难题劝退。用它来检测自己哪一类考点还没掌握再针对性地去补模块性价比最高。6.2 如何高效整理错题本我不推荐手抄错题太费时间。推荐用电子表格或者笔记软件每道错题记录六要素题目链接、考点标签、错误原因、正确思路、代码实现、复盘时间。重点是错误原因这一栏要具体到边界条件没处理还是状态转移方程写错了还是压根没想到这个考点。整理错题不是记完就完了要定期回顾。我会在每周末把本周错题重新做一遍做对两遍以上的才标记为已掌握。这个重复做对两遍的标准很重要因为第一遍看答案做对的题过两周大概率还是会忘。只有完全凭自己写出来、跑通才算真正掌握。我在帮别人复盘时发现一个规律大部分人的错误类型不超过三种。有的永远在边界条件上翻车有的永远卡在状态转移有的是一到模拟题就逻辑混乱。找到自己的固定短板集中突破比什么都题都平均用力有效得多。6.3 笔试时间分配的具体建议最后说说考场上到底怎么分配时间。假设一共四道题我习惯这样安排前5分钟快速浏览全部题目标注每道题的难度和擅长程度然后先做最擅长的那道把确定能拿的分先拿到接着做最简单的送分题再处理中等题最后剩下的时间全部投入难题如果难题15分钟还没有完整思路直接写暴力过小数据case。这样的安排能保证一个下限至少做对两道题可能三道。如果按顺序死磕很可能第一道简单题做完第二道中等题卡了半小时后面两道题连看都没来得及看。我2017年一模就是这样第一道题做了太久第三道贪心题基本没时间思考草草写了个错误解法——那次模考我考完就知道问题出在哪之后调整了做题顺序和节奏秋招笔试顺利多了。还有个小建议平时练习时尽量使用和笔试相同的编程环境。牛客网有模拟笔试功能完全复刻真实考试界面和判题方式。多用这个功能做全真模拟到真实笔试时环境适应成本就很小。环境不熟悉导致的紧张在编程笔试里是很亏的。7. 从一道模考题看校招笔试的出题趋势7.1 考察重点从会不会转向熟不熟对比2017年和现在的笔试题目我发现一个明显变化现在的题目越来越卷但核心考点的考察方式反而更偏向熟练度和准确率。出题人已经不太用偏题怪题来筛人了而是在经典题型上增加信息量让题目看起来复杂但确定能解出来。这是什么意思呢比如LIS2017年可能就直接给数组求最长上升子序列现在可能给一堆点的坐标让你先排序再求LIS或者给每个数字加上额外属性需要自定义排序规则再套LIS。说白了题目的外衣越来越多内核不变。这就更要求你把基础算法的推导过程吃透而不是死记硬背模板。模板背得再熟遇到披了新外衣的题认不出来一样白搭。所以我带人的时候从来不让直接背Kadane算法或者LIS模板而是要求他们能从状态定义开始自己推导出转移方程。这个过程走一遍比刷十道同类题更有用。笔试的时候忘了一个边角语法可以通过推导再确认而不是依赖死记硬背的代码。7.2 数据范围增大带来的复杂度要求另一个趋势是数据范围越来越大。早年模板题可能n100O(n^3)都能过现在很多中等题n10^5O(n^2)就是超时。这就要求你在写代码之前先估算复杂度再决定用哪种算法。我建议在草稿纸上养成一个习惯读完题先看数据范围标记出可能的时间复杂度上限再根据这个上限倒推算法。比如n10^5最坏允许O(n log n)那你能用的算法就限定在排序、二分、堆、并查集这些里面DP数组如果是一维O(n)可以二维O(n^2)就不可行要优化或换思路。这个先看数据范围再定算法的习惯我在2017年那会儿还没有是后来吃了亏才养成的。有一次模拟笔试题目给的是n10^5我上来就写了个二维DP写完还在得意状态转移方程很巧妙一提交直接超时。从那以后我拿到题第一件事就是盯数据范围。7.3 面试中的算法延伸提问笔试做完了题目本身还没结束。面试官经常会拿你笔试里做过的题来深挖比如问你这道题还有没有更优解你刚才这个解法空间复杂度还能不能降如果输入是流式数据你怎么改。如果你笔试时只是背模板AC了这些追问很容易露馅。针对一套模考题面试前可以自己准备几个追问的答案。比如LIS能说出O(n log n)的二分优化和证明思路区间调度能说出贪心选择性质的交换证明最大子数组和能说出分治解法和Kadane算法的区别与联系。准备这些不是为了背答案而是通过思考这些问题把题目理解得更深。笔试时你只是完成代码面试时你需要展示思维深度。这也是为什么我把2017一模这道题翻来覆去地讲——它足够经典可以往各个方向延伸。把一道经典题的上下游都打通比囫囵吞枣刷十道新题收获更大。我从2017年那个被模考打击到的学生到后来帮别人准备校招笔试中间最大的变化就是明白了笔试考的不是你遇到过多少题而是你在有限时间内把核心算法应用到一个新场景里的能力。牛客模考也好、公司笔试题也好都是这个逻辑的外化。这套题的每道题都值得反复咀嚼直到你不仅能写出代码还能讲清楚每一步为什么这么走。 2017牛客模考编程题全解析：笔试高频考点与解题策略
每年三四月份牛客网的模考一出来群里就炸锅。2017年那次一模我印象特别深那会儿我还在学校刚刷完剑指offer觉得自己行了结果被一模编程题教做人。现在回头看那套题其实一点也不偏反而特别能反映笔试编程题的核心套路——字符串处理、贪心、动态规划、模拟全是这些东西。这几年我帮学弟学妹改简历、做模拟面试发现大家刷题有个通病光顾着刷量不研究题目背后的设计逻辑。所以今天想借2017牛客模考一模编程题集合这个经典样本把笔试编程题的解题思路完整拆一遍包括题目考点、常见陷阱、代码实现以及我当时踩过的坑和总结出的应考节奏。这套题适合谁两类人。第一类是准备秋招春招的应届生尤其是投后端、算法、测试开发这些要考编程题的岗位第二类是刚刷完基础题、想检验自己水平的大二大三学生。如果你已经工作但想跳槽也可以拿它当热身。文章不会只给答案我会把每道题的思考过程、为什么这么解、换一道类似的题怎么识别考点都讲清楚。1. 2017一模整体的题目设计思路1.1 题型分布与难度曲线先看整体盘子。牛客模考编程题通常四道左右2017年一模的难度分布大致是一道简单字符串、一道中等模拟、一道贪心、一道动态规划。这个配置几乎成了之后几年校招笔试的模板到现在很多公司的笔试题还是这个比例只不过难度整体抬高了。为什么出题人这么安排很简单考查覆盖面。字符串是基础编码能力的试金石模拟题考代码组织能力和状态梳理能力贪心考思维敏锐度动态规划考算法功底。四道题分别对应不同维度能把候选人的水平拉开层次。如果你只擅长某一种题大概率会被卡住。再具体一点难度曲线是前松后紧。第一道题基本是送分题保证大部分人能上手写第二道题稍微绕一点需要理清逻辑第三道和第四道是分水岭决定了你能不能进下一轮面试。很多人栽在第三道贪心题上不是不会而是没看出来这是个贪心——这是最可惜的失分方式。我建议拿到题先花两分钟扫一遍所有题目不要从第一题按顺序做。先把送分题做了再跳到你最有把握的中等题最后啃难题。这个策略我在后面章节会详细讲。1.2 为什么这套题现在刷依然不过时有人可能觉得2017年的题太老了现在面试都不考这些。这话对了一半。新技术框架确实日新月异但笔试编程题考的是算法和数据结构基础这东西十年二十年不会变。2017年考最长上升子序列2025年还在考2017年考区间调度贪心现在依然是大厂高频题。而且2017年这套题有个好处它处在牛客模考这个体系的早期题目风格还没被各种培训机构研究透所以题目更纯粹没有太多偏题怪题。现在的笔试题反而经常出现一些为了难而难的题目动不动就上后缀自动机、树链剖分对校招生来说反而失去了选拔意义。所以拿这套题打基础性价比很高。我每年带新人刷题都会让他们先把这套题做一遍目的不是让他们背答案而是让他们感受一下一个正常难度的笔试是什么样。做完这套题再去刷那些偏难怪题心里就有底了。1.3 一道题的完整估值模型刷题不能傻刷你得知道每道题大概花多长时间是合理的。我自己的标准是第一道简单题控制在5分钟以内中等题10到15分钟难题如果20分钟还没有思路果断放弃或者写个暴力解法先拿部分分。这个时间估值基于一个简单的公式笔试总时长除以题目数量再考虑难度加权。比如一共90分钟四道题平均每道22.5分钟但简单题不应该用满这个时间省下来的时间得补给难题。很多人栽就栽在简单题上死磕最优解结果难题连暴力分都没拿到。2017年一模我当时就犯了这错误。第一道字符串题明明用最基本的遍历就能AC我非要优化成O(n)空间复杂度的花活结果折腾了二十分钟后面贪心题只能草草写个错误答案交上去。笔试不是给你炫技的是让你拿分的。2. 高频考点拆解字符串与模拟题2.1 回文串判定的三种写法字符串题是笔试的常客2017一模第一道题就是回文串相关。题目大致是给定一个字符串判断它是否是回文串忽略空格和标点且不区分大小写。听起来很简单对吧但越简单的题越容易暴露出编码习惯问题。最稳妥的写法是双指针——一个指向开头一个指向结尾跳过非字母数字字符然后比较。这个方法时间复杂度O(n)空间复杂度O(1)既不依赖额外的数据结构也不容易出错。def is_palindrome(s: str) - bool: left, right 0, len(s) - 1 while left right: while left right and not s[left].isalnum(): left 1 while left right and not s[right].isalnum(): right - 1 if s[left].lower() ! s[right].lower(): return False left 1 right - 1 return True第二种写法是逆序比较先把字符串清洗干净再反转然后逐位比较。这个思维最直白但多了一次字符串拷贝空间复杂度O(n)。第三种写法是递归不推荐在笔试里用容易栈溢出而且代码还长。这里有个小坑很多人会踩if s[left].lower() ! s[right].lower()注意是用lower()统一大小写而不是直接比较。还有内层跳过非字母数字的while循环要加left right条件不然可能越界。这些细节在IDE里有提示但在牛客这种不帮你检查越界的在线编辑器里可能直接报错。2.2 字符串压缩与解压的边界处理另一道高频字符串题是压缩给定一个字符串把连续重复的字符压缩成字符次数的形式比如aaabbc压缩成a3b2c1。这题考的是对连续区间的处理跟统计词频是同一类思路。def compress(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)这题有两个边界必须处理好。第一个是空串输入直接返回空串不然s[-1]会越界第二个是最后一个字符的统计——很多人循环里只处理了前后字符不同的情况忘了把最后一组追加进去。这两个问题我每次改卷子都能看到说明不是个例是普遍习惯问题。还有一个优化的点如果压缩后的字符串不比原串短应返回原串。这个要求源自LeetCode 443的变体牛客的题也常这样出。加上这个判断后代码要多一层逻辑def compress(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)) compressed .join(res) return compressed if len(compressed) len(s) else s这种题本身不难但要拿满分边界条件一个都不能漏。我强调这些是因为笔试判分的时候很多case就是针对边界条件设计的——你功能逻辑全对但空串没处理照样WAWrong Answer。2.3 模拟题的通用思路状态机思维模拟题是2017一模的第二道也是很多人的噩梦。那道题大概是模拟一个简化版计算器输入一个只包含数字、、-、*、/的表达式输出计算结果。这种题不考算法考的是对过程的拆解能力。我做模拟题有个固定套路先画状态机。状态就是当前正在读什么——可能是数字、可能是运算符、可能是操作符之后的下一个数字。每一次读入一个字符根据当前状态决定下一步动作。把这个状态流转画清楚代码就是状态机的直译。比如计算器表达式求值核心是处理优先级。经典做法是用两个栈一个操作数栈一个运算符栈。遇到运算符时如果栈顶运算符优先级不低于当前运算符就先弹出运算再把当前运算符压栈。这个弹栈计算的过程就是状态机里读到运算符时进入结算状态的落地。def calculate(s: str) - int: stack [] num 0 sign for i, ch in enumerate(s): if ch.isdigit(): num num * 10 int(ch) if ch in -*/ or i len(s) - 1: if sign : stack.append(num) elif sign -: stack.append(-num) elif sign *: stack.append(stack.pop() * num) elif sign /: stack.append(int(stack.pop() / num)) sign ch num 0 return sum(stack)这里有个Python特有的坑int(stack.pop() / num)和stack.pop() // num结果不一样。比如-3 // 2在Python里等于-2因为Python的整除是向下取整而题目通常想要的是向零取整。所以必须写成int(-3 / 2)得-1。这种语言层面的细节笔试中不会有编译器提醒你只能靠平时积累。模拟题拿高分的核心就一句话先把规则梳理成清晰的流程再写代码。我见过太多人上手就写写到一半发现少处理一种情况又回头改结构最后代码跟意大利面一样——能跑但没人敢保证它是对的。花三分钟整理流程能省下三十分钟改bug的时间。3. 贪心与动态规划那两道分水岭题目3.1 区间调度贪心的证明思路2017一模的第三道题是会议室安排问题变种给定一组区间找出最多能选择多少个互不重叠的区间。这题是贪心算法的经典入门题也是面试官最爱问的题之一——因为它表面上是安排实际上是考你是否理解贪心策略背后的选择逻辑。最经典的解法是按区间结束时间排序然后依次选择只要当前区间开始时间不早于上一个选中区间的结束时间就选中它。排序复杂度O(n log n)选择过程O(n)。def max_non_overlapping(intervals): if not intervals: return 0 intervals.sort(keylambda x: x[1]) count 1 end intervals[0][1] for i in range(1, len(intervals)): if intervals[i][0] end: count 1 end intervals[i][1] return count很多人会问为什么按结束时间排序而不是按开始时间或者区间长度这个问题的答案才是面试官真正想听的。按结束时间排序保证了每次选择都给后面留下尽可能大的剩余空间这是贪心选择性质的直观理解。形式化证明是交换论证法假设最优解的第一个区间不是结束时间最早的可以把最优解的第一个区间替换成结束时间最早的区间其余部分不受影响因此存在一个包含结束时间最早区间的最优解。这个证明思路我建议背下来因为很多贪心题的证明套路都长一个样。笔试虽然不要求写证明但理解证明能帮你在面对变形题的时候判断这题是不是贪心。3.2 最长上升子序列的DP推导最后一道题是经典的动态规划——最长上升子序列LIS。题目给一个无序数组求最长严格递增子序列的长度。子序列不要求连续但要保持原数组顺序。看到最长加子序列这两个词第一反应就应该是DP。状态定义dp[i]表示以nums[i]结尾的最长上升子序列长度。转移方程dp[i] max(dp[j] 1)其中j i且nums[j] nums[i]。初始状态dp全为1每个元素自身构成一个长度为1的子序列。def length_of_lis(nums): if not nums: return 0 dp [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) return max(dp)O(n^2)的解法是最容易实现也最不容易出错的。但面试或笔试如果限时较紧可能会希望你会O(n log n)的优化版——用贪心加二分维护一个tails数组其中tails[k]表示长度为k1的上升子序列末尾元素的最小值。具体不展开网上很多资料。我想强调的是先写对再写快。如果O(n^2)的思路清晰就按O(n^2)写不要为了炫技写二分然后因为边界条件出错。笔试是看AC的题数不看复杂度多漂亮。3.3 怎么快速判断一道题该用贪心还是DP这是个困扰许多人的问题。我的判断标准是贪心是每一步做局部最优选择DP是考虑所有可能状态并取最优。如果题目有每一步可以做出一个选择选择后整个问题变成一个更小的同类型子问题的结构很可能贪心如果题目有多种方式组合成答案需要把所有情况都考虑到的结构那是DP。举个例子区间调度按结束时间排序是贪心因为每选一个区间后问题就缩小成从当前结束时间之后找最大数量区间而且选择结束时间最早的区间永远不比选择其他区间差。而LIS不是贪心——你不能说选最小的那个数一定最优因为子序列的构成要考虑顺序所以必须枚举所有可能性用DP。还有一个典型的区分题找零钱问题。如果用无限量硬币凑出某个金额求最少硬币数先用最大面值硬币不一定最优比如面值1、3、4凑6先拿4再拿11是3枚但33只要2枚所以这题不能用贪心得用DP。但如果是面值1、5、10、25美分贪心反而最优。原因是这些面值满足贪心选择性质。所以判断标准不是看起来能不能贪而是局部最优是否真的能推出全局最优。4. 真题实战两道完整的解题过程4.1 题目最小覆盖子串的滑窗实现虽然不是2017一模的原题但滑动窗口这类题在牛客模拟中反复出现一模也有一道变种。我拿一道典型题来讲完整流程给定一个字符串S和一个模式串T在S中找到包含T所有字符的最短子串。这题是滑窗的经典场景。思路分五步走。第一步用字典need记录T中每个字符的需求量第二步用两个指针left和right表示窗口边界第三步移动right扩展窗口同时更新窗口内字符计数第四步当窗口内已包含T全部字符时尝试移动left收缩窗口记录最短长度第五步重复直到right遍历完整个S。def min_window(S: str, T: str) - str: from collections import Counter if not S or not T: return need Counter(T) remain len(T) left 0 min_len float(inf) min_left 0 for right, ch in enumerate(S): if need[ch] 0: remain - 1 need[ch] - 1 while remain 0: if right - left 1 min_len: min_len right - left 1 min_left left left_ch S[left] if need[left_ch] 0: remain 1 need[left_ch] 1 left 1 return if min_len float(inf) else S[min_left:min_left min_len]这个代码里最关键的是remain这个变量。它表示还没满足的T中字符个数只有当窗口内某个字符是T需要的且当前数量不足时remain才会减一。这个设计比每次都比较两个Counter要高效得多也避免了重复计算。我实战中常犯的错误是在收缩窗口时忘了恢复need计数。每次移动left必须把对应字符的需求量加回来否则窗口内字符计数会越来越小导致误判。这个bug特别隐蔽因为小数据量可能测不出来但大数据量就会出现明明包含T的字符却显示不包含的诡异现象。4.2 题目最大连续子数组和的两种解法另一道常考的题是最大连续子数组和也就是LeetCode 53。题目很简短给定一个整数数组找出一个具有最大和的连续子数组返回其最大和。看似简单但它既可以用DP解也可以用分治法解是考察基本功的好题。Kadane算法是这题的最优解cur max(num, cur num)result max(result, cur)。一维DP的压缩版空间O(1)时间O(n)。def max_subarray(nums): cur nums[0] result nums[0] for num in nums[1:]: cur max(num, cur num) result max(result, cur) return result理解这个算法的关键是cur的语义以当前位置为结尾的最大连续子数组和。为什么是max(num, cur num)因为要么从当前元素重新开始要么接着前面的连续段。很多人在这一步纠结如果前面的连续段本身就小于0怎么办——max(num, cur num)已经处理了这个情况如果cur是负数加上num反而不如直接取num大所以自动选择重新开始。分治法解法也值得掌握把数组分成两半最大子数组要么完全在左半要么完全在右半要么跨越中点。前两种情况递归解决跨越中点的情况需要从中点向两边扩展找最大和然后三取一。复杂度O(n log n)虽然不如Kadane但分治思想在很多进阶题里都会用到建议写一遍加深理解。4.3 完整调试与自测的实操记录来说说我当年在牛客上做这类题的真实过程。写完之后我不会直接提交先自己构造几组测试用例跑一遍。第一组是最简单的正常情况比如[1, 2, 3]第二组是全负数比如[-1, -2, -3]这组最容易暴露初始值没设好的问题第三组是混合正负比如[-2, 1, -3, 4, -1, 2, 1, -5, 4]。每组用例都要在纸上先算好预期输出再跑到代码里验证。全负数这个用例特别关键。很多人Kadane算法初始化cur 0结果全负数数组会错误地输出0。正确做法是初始化cur nums[0]或者cur float(-inf)再遍历。我在牛客上见过太多人因为这一个小问题写对了80%的逻辑但提交直接WA。自测的时候还有一个技巧故意加一个大规模随机数组来压测。不是检查正确性而是看时间复杂度是否够快。如果O(n^2)的解法跑到10万数据量会卡住那就趁早换思路。笔试环境一般有性能监控超时也算错。5. 牛客笔试中的失分点与排查技巧5.1 输入输出格式的坑牛客笔试和LeetCode最大的区别就是牛客要自己处理输入输出LeetCode只需要实现函数。这个差异让很多人吃了大亏。最常见的问题是读入数据时类型不对——比如题目说第一行一个整数n第二行n个整数你按字符串读进来忘了转int自然全错。牛客输入模板我建议形成肌肉记忆。整数数组data list(map(int, sys.stdin.readline().split()))。多行输入以EOF结束for line in sys.stdin: ...。字符串s sys.stdin.readline().strip()。这些模板不花什么技术含量但能避免大量低级错误。还有一个很隐蔽的坑输出格式。要求每个结果占一行你正确输出了结果但忘了换行——这种情况通常不会判错但如果要求用空格分隔而你在末尾多打了一个空格有些严格的判题系统会报Presentation Error。虽然不算WA但零分和全分之间就差了这一个空格很冤。5.2 边界条件速查表我总结了一个笔试前必看的边界条件清单每个题目类型对应几个必测的边界题目类型必须测试的边界条件数组类空数组、单元素数组、全相同元素、全负数字符串类空串、单字符串、全空格串、大小写混合二叉树类空树、只有左子树、只有右子树、单节点动态规划n0、n1、n2、目标值等于边界值数学类零、负数、最大整数、溢出场景别觉得这些是废话。我在牛客上看到的最多报错就是数组越界和空指针异常全是边界条件没处理干净。特别是递归和DP类题目n0的时候dp数组初始化为[0] * n输出时越界n1时循环根本不执行有些变量没被赋值——这些问题在提交前自己先测一遍就能发现。5.3 时间复杂度的经验判断笔试经常会碰到题目说数据范围n10^5你的算法跑了O(n^2)的情况。一套下来肯定超时。我平时判断能否通过有一个粗略经验表数据量10^5O(n log n)大概是1秒上下O(n^2)直接是分钟级别数据量10^4O(n^2)勉强能过但O(n^3)就别想了数据量10^3O(n^2)很轻松O(n^3)可能危险。如果时间不够优化至少写个暴力解拿部分分。有些题目的判分规则是多个测试点每个测试点有一定分值暴力解能过其中一部分小的case。千万别空着空着连同情分都没有。我曾亲眼见过有人四道题只AC两道但第三题写了个暴力拿了40%的分数最后总分比三道题满分的人都高——因为难度越大的题别人越可能完全做不出来。5.4 笔试现场的调试策略在线笔试通常没有调试器你只能用print大法。但print不是随便打的要有技巧。我自己的习惯是先打印最关键的状态变量——循环的起点、终点、中间结果然后再打印循环内部每个分支的走向。比如DP题我会在每次状态转移之后把dp数组打印出来看变化趋势如果某个值不对根据dp的变化能立刻定位是转移方程写错还是初始化写错。比盲目打印所有变量高效得多。还有一个小技巧不要把print留在最终提交的代码里。很多人调试完忘了删结果满屏调试输出直接判错。我习惯在提交前用CtrlF搜一下print确认没有调试语句才提交。6. 基于2017一模的备考建议与刷题节奏6.1 三轮刷题法如果离笔试还有一段时间我建议用三轮刷题法来准备。第一轮是分类刷把所有高频考点各刷10道左右目标是形成条件反射——看到最长想DP看到区间想贪心看到字符串匹配想滑窗第二轮刷整套模拟卷每周一套目标是训练时间分配和手感第三轮是回顾错题重点是把自己反复错的题目类型重做一遍。三轮之间不是递进关系而是有交叉的。分类刷的时候也可以偶尔抽一套完整卷子来检验做整套卷子的时候遇到不会的题回归到对应知识点去补课。这样周而复始效果比闷头刷题好得多。2017一模就是很适合做第二轮刷题练手的卷子。因为它难度适中题型分布均匀不会像一些大厂真题那样一开始就被难题劝退。用它来检测自己哪一类考点还没掌握再针对性地去补模块性价比最高。6.2 如何高效整理错题本我不推荐手抄错题太费时间。推荐用电子表格或者笔记软件每道错题记录六要素题目链接、考点标签、错误原因、正确思路、代码实现、复盘时间。重点是错误原因这一栏要具体到边界条件没处理还是状态转移方程写错了还是压根没想到这个考点。整理错题不是记完就完了要定期回顾。我会在每周末把本周错题重新做一遍做对两遍以上的才标记为已掌握。这个重复做对两遍的标准很重要因为第一遍看答案做对的题过两周大概率还是会忘。只有完全凭自己写出来、跑通才算真正掌握。我在帮别人复盘时发现一个规律大部分人的错误类型不超过三种。有的永远在边界条件上翻车有的永远卡在状态转移有的是一到模拟题就逻辑混乱。找到自己的固定短板集中突破比什么都题都平均用力有效得多。6.3 笔试时间分配的具体建议最后说说考场上到底怎么分配时间。假设一共四道题我习惯这样安排前5分钟快速浏览全部题目标注每道题的难度和擅长程度然后先做最擅长的那道把确定能拿的分先拿到接着做最简单的送分题再处理中等题最后剩下的时间全部投入难题如果难题15分钟还没有完整思路直接写暴力过小数据case。这样的安排能保证一个下限至少做对两道题可能三道。如果按顺序死磕很可能第一道简单题做完第二道中等题卡了半小时后面两道题连看都没来得及看。我2017年一模就是这样第一道题做了太久第三道贪心题基本没时间思考草草写了个错误解法——那次模考我考完就知道问题出在哪之后调整了做题顺序和节奏秋招笔试顺利多了。还有个小建议平时练习时尽量使用和笔试相同的编程环境。牛客网有模拟笔试功能完全复刻真实考试界面和判题方式。多用这个功能做全真模拟到真实笔试时环境适应成本就很小。环境不熟悉导致的紧张在编程笔试里是很亏的。7. 从一道模考题看校招笔试的出题趋势7.1 考察重点从会不会转向熟不熟对比2017年和现在的笔试题目我发现一个明显变化现在的题目越来越卷但核心考点的考察方式反而更偏向熟练度和准确率。出题人已经不太用偏题怪题来筛人了而是在经典题型上增加信息量让题目看起来复杂但确定能解出来。这是什么意思呢比如LIS2017年可能就直接给数组求最长上升子序列现在可能给一堆点的坐标让你先排序再求LIS或者给每个数字加上额外属性需要自定义排序规则再套LIS。说白了题目的外衣越来越多内核不变。这就更要求你把基础算法的推导过程吃透而不是死记硬背模板。模板背得再熟遇到披了新外衣的题认不出来一样白搭。所以我带人的时候从来不让直接背Kadane算法或者LIS模板而是要求他们能从状态定义开始自己推导出转移方程。这个过程走一遍比刷十道同类题更有用。笔试的时候忘了一个边角语法可以通过推导再确认而不是依赖死记硬背的代码。7.2 数据范围增大带来的复杂度要求另一个趋势是数据范围越来越大。早年模板题可能n100O(n^3)都能过现在很多中等题n10^5O(n^2)就是超时。这就要求你在写代码之前先估算复杂度再决定用哪种算法。我建议在草稿纸上养成一个习惯读完题先看数据范围标记出可能的时间复杂度上限再根据这个上限倒推算法。比如n10^5最坏允许O(n log n)那你能用的算法就限定在排序、二分、堆、并查集这些里面DP数组如果是一维O(n)可以二维O(n^2)就不可行要优化或换思路。这个先看数据范围再定算法的习惯我在2017年那会儿还没有是后来吃了亏才养成的。有一次模拟笔试题目给的是n10^5我上来就写了个二维DP写完还在得意状态转移方程很巧妙一提交直接超时。从那以后我拿到题第一件事就是盯数据范围。7.3 面试中的算法延伸提问笔试做完了题目本身还没结束。面试官经常会拿你笔试里做过的题来深挖比如问你这道题还有没有更优解你刚才这个解法空间复杂度还能不能降如果输入是流式数据你怎么改。如果你笔试时只是背模板AC了这些追问很容易露馅。针对一套模考题面试前可以自己准备几个追问的答案。比如LIS能说出O(n log n)的二分优化和证明思路区间调度能说出贪心选择性质的交换证明最大子数组和能说出分治解法和Kadane算法的区别与联系。准备这些不是为了背答案而是通过思考这些问题把题目理解得更深。笔试时你只是完成代码面试时你需要展示思维深度。这也是为什么我把2017一模这道题翻来覆去地讲——它足够经典可以往各个方向延伸。把一道经典题的上下游都打通比囫囵吞枣刷十道新题收获更大。我从2017年那个被模考打击到的学生到后来帮别人准备校招笔试中间最大的变化就是明白了笔试考的不是你遇到过多少题而是你在有限时间内把核心算法应用到一个新场景里的能力。牛客模考也好、公司笔试题也好都是这个逻辑的外化。这套题的每道题都值得反复咀嚼直到你不仅能写出代码还能讲清楚每一步为什么这么走。