作为一个当年在牛客网上反复刷模拟题、秋招前被三模虐到怀疑人生又硬啃下来的过来人看到这个标题我还是很有感触的。2019牛客三模的编程题集合放在当时是很多人秋招前的一次重要演练现在回头看里面好几道题考察的思维点和边界处理方式放到今天的笔试里依然很经典尤其是那类“看起来简单、一写就错”的模拟题和带点动态规划味道的递推题。这篇文章我把当时做题的完整思路、代码实现和踩过的坑都整理出来给正在准备笔试的朋友一个参考。这个题目集合适合谁看主要还是准备校园招聘笔试、想熟悉在线评测系统OJ判题规则的人不管你是后端、客户端还是测开方向编程题都是躲不掉的一关。文章不会只贴答案而是把每道题的思考过程、为什么这样做、以及常见的错误点讲清楚这样你遇到变体题也不慌。1. 整体设计与思路拆解1.1 19年三模编程题的考察倾向我印象很深的点是2019牛客三模的编程题整体难度不算特别大但陷阱非常多。它不像一些竞赛题那样上来就让你写平衡树或者网络流而是更贴近“实际工作中的编码能力”和“面试手撕代码的基本功”。从考点分布上看核心集中在几个方面字符串处理与边界判断尤其是输入可能带空格、空行、大小写混合的情况。模拟类题目题目描述很长本质就是让你按规则一步步实现需要提炼核心逻辑。基础的排序和查找但要求你考虑稳定性或者复杂度不能无脑调API完事。递推和简单动态规划往往伪装成“数学题”或者“找规律题”实际是状态转移。数据范围陷阱比如很大整数要用long long或Python直接支持大整数否则C选手会栽。这个设计思路其实很聪明。秋招笔试不是选拔竞赛选手而是在有限时间内考察候选人能不能写出清晰、正确、健壮的代码。所以那些“看起来简单但容易考虑不全”的题反而最能拉开差距。1.2 为什么说这是一套练手价值很高的题目集很多人会觉得考完试题目就没用了但我不这么看。这套题的价值在于它模拟了真实笔试中最容易出现的“审题偏差”。举个例子有一道题要求对字符串做某种替换描述里写着“按照字典序最小的方式输出”。很多人的第一反应是直接排序但仔细分析之后会发现如果你直接把整个字符串排序会破坏原有字符的相对位置关系而题目的隐含要求可能是“在保持原顺序的前提下让某一部分字典序最小”。这种差异化理解正是三模想考验你的地方。另外这套题还很喜欢在“输入输出格式”上做文章。比如有的题目输出答案时要换行有的要求每个结果之间用空格分隔末尾不能有空格有的数据是多组输入读到某个标志才结束。这些细节在本地IDE里你根本不会注意但上了OJ就是一次次Wrong Answer。我当时就因为这个原因交了七次才过了一道题。所以说平时用牛客这种在线评测系统刷题能帮你提前适应这种严苛的判题环境这是只在本地上跑跑用例完全比不了的。2. 核心细节解析与实操要点2.1 第一类典型题带规则的字符串变换这类题在笔试里出现频率极高核心是考察对字符串下标和边界条件的把控。我当时遇到的一道题大致是这样给定一个只包含小写字母的字符串要求把所有连续相同的字符压缩成“字符出现次数”的形式如果压缩后的字符串长度没有变短则输出原字符串否则输出压缩结果。看起来无非就是遍历一遍但下面几个点很容易犯错。第一个坑是次数可能超过一位数。比如“aaaaaaaaaa”10个a压缩结果是“a10”长度是3确实是变短了但如果你的代码里只是用count 0来拼接超过9就全乱了。正确做法是使用整型转字符串的函数C里可以用to_stringJava里是String.valueOfPython里直接用str()就行。第二个坑是“长度没有变短则输出原字符串”的判断时机。你不要每处理一个字符就判断一次那样逻辑会很乱。正确做法是先完整生成压缩串最后判断压缩串和原串的长度大小再决定输出哪个。这里有一个小技巧如果压缩串中途长度已经超过原串理论上可以提前终止但对笔试而言没必要做这种优化反而容易写错。第三个坑是末尾字符的收尾。我见过很多人写循环时只在当前字符和下一个字符不同的时候处理前一个字符的计数结果循环结束后忘记处理最后一组字符导致漏掉了末尾一串字母。这个错误太经典了几乎所有新手都会踩一次。我的习惯是在循环里先比较i和i1不相等就结算之前的循环结束后再把最后一段补上。2.2 第二类典型题模拟题中“状态机”思维的重要性三模里还有一道排队模拟的题具体规则我记不太清了大概是说有一堆任务按照不同优先级到达每次执行一个时间片然后判断某个时间点的任务状态。这类题看起来简单但如果直接用循环模拟每个时间片一旦数据范围大了就会超时而且代码冗余。我当时用的是“状态机”的思路来简化。先分析一个任务在整个过程中可能处于哪些状态等待、执行、完成。然后根据时间推进只关心在关键时间点上的状态变化而不是一个时间片一个时间片地推进。比如任务在时间t到达执行时长为p如果当前任务队列为空那么任务立刻执行否则需要等待前面所有任务完成。这样就能推导出每个任务的开始时间和结束时间而不用真的去模拟每一秒。这里同样有个大坑如果多个任务到达时间相同优先级怎么处理题目一定会定义清楚比如按编号先后或者按优先级。读题时务必圈出来因为排序规则会直接影响结果。我建议把任务封装成一个结构体包含到达时间、执行时长、编号、优先级然后用一个优先队列来维护。在C里priority_queue默认是大顶堆如果你想按优先级高的先出队需要自定义比较函数而Java的PriorityQueue则是最小堆使用方式略有不同。Python里可以用heapq存进元组的时候注意排序字段的顺序。这个技巧我至今仍在用。2.3 第三类典型题不动点与循环节思想还有一道题让我印象很深题目大意是给定一个正整数n如果它是偶数就把n除以2如果是奇数就把n乘以3再加1重复操作问经过多少次可以变成1。这就是著名的考拉兹猜想3n1问题。题目本身不要求证明只是实现看起来简单到不行。但这道题真正的考点是“数据溢出”。当n较大时在变成1的过程中中间值可能会先变得非常大。比如n27中间最高值能达到9232这还算温和如果是更大的数C的int绝对会溢出。所以这类题只要涉及乘法加一一定要用long long甚至unsigned long long。如果用Python可以暂时高枕无忧因为Python的整数是任意精度的。另一个考点是“循环检测”。虽然考拉兹猜想至今没有被证明但如果在题目条件里加入了一个特定模数或者让你判断某个数会不会重复出现那就可以用哈希集合记录访问过的数一旦重复就认为进入循环。这是一种通用套路在模拟“走迷宫死循环”类题目中常见。我当时在做这道题时就额外实现了一个set来记录虽然题目不一定需要但作为一种防御性编程对思考很有帮助。2.4 第四类典型题看似数学题实则DP的数列问题还有一类题很迷惑人题目会给你一个递推公式比如f(n) f(n-1) f(n-2) - f(n-3)然后让你求第n项。有些人第一反应是直接递归结果n稍微大一点就栈溢出或者超时。更有些人尝试去找数学通项公式但大多数情况下并没有那么简单的闭式解。这道题的正确打开方式是动态规划用一个数组或者几个变量滚动保存前几项的结果。为什么说是DP而不是“递推”因为递推关系和DP状态转移本质上是同一个东西但DP强调的是“无后效性”和“重叠子问题”。在这里f(n)只依赖于前三项所以你不需要保存所有历史的f值只需要维护最近三个状态每次迭代滚动更新就好了。具体到代码可以定义三个变量a, b, c分别代表f(n-3), f(n-2), f(n-1)然后循环计算d c b - a更新完再整体往前移动一位。这个做法的空间复杂度是O(1)时间复杂度是O(n)对于笔试场景是标准答案。我见过很多人虽然能写出递归但无法优化遇到n10^7直接歇菜。所以这题考的不只是公式而是你能不能把递归改成迭代的滚动数组。3. 实操过程与核心环节实现3.1 环境准备与输入输出套路我强烈建议在正式刷题之前先搞定“输入输出模板”。这不是浪费时间因为在笔试中很多人不是不会写算法而是卡在“怎么读入一整行包含空格的字符串”“怎么处理多组输入直到EOF”这种事情上。以Python为例常见模板就是import sys def solve(): data sys.stdin.read().strip().split() # 处理单个数字 n int(data[0]) # 处理多组输入直到EOF tokens sys.stdin.read().split() i 0 while i len(tokens): a int(tokens[i]); b int(tokens[i1]) # 做点什么 i 2 if __name__ __main__: solve()不要用input()一行行读当数据量大的时候sys.stdin.read()一次性读入再切分是最稳的。C则建议关闭同步流在main函数开头写一句ios::sync_with_stdio(false);再配合cin.tie(nullptr);否则容易超时。这个习惯我从三模一直保持到现在很多ACM选手也是这么写的。另外注意输出格式。如果题目说每行输出一个结果就老老实实print(ans)如果要求用空格分隔可以用print( .join(map(str, ans_list)))这样自动不会有多余空格。我在三模时因为多打了一个空格被判Presentation Error虽然判题系统没有算错但这种无谓的罚时很不值。3.2 字符串压缩题的参考实现与细节为了直接能用我给出一个经过反复测试的Python版本def compress(s: str) - str: if not s: return res [] cnt 1 for i in range(1, len(s)): if s[i] s[i-1]: cnt 1 else: res.append(s[i-1]) res.append(str(cnt)) cnt 1 res.append(s[-1]) res.append(str(cnt)) compressed .join(res) return s if len(compressed) len(s) else compressed这段代码的重点在于循环里比较i和i-1而不是i和i1这样就不太容易漏掉最后一组。最后用len(compressed) len(s)作为是否保留原串的条件符合题目的“没有变短则输出原串”。如果要求相等时输出原串那这个判断就是对的如果要求相等时输出压缩串改成即可。这个细节一定要看清题目。我在测试时发现很多人会忽略一个问题如果原串里面已经有数字压缩后的表示就可能产生歧义。当然题目通常限定只包含小写字母但如果题目没有明确说明那么压缩方案本身就不严谨。所以在拿到题时先确认输入约束条件这会省下一堆麻烦。3.3 任务模拟问题的参考实现与分析我给一个简化版的思路示例重点在于数据结构和事件处理逻辑。假设我们有任务列表tasks[(arrive, duration, priority, id)]需要输出每个任务的完成时间。import heapq def process_tasks(tasks): tasks.sort() # 按到达时间排序 heap [] idx 0 current_time 0 ans {} n len(tasks) while idx n or heap: if not heap and idx n and current_time tasks[idx][0]: current_time tasks[idx][0] while idx n and tasks[idx][0] current_time: arrive, duration, priority, tid tasks[idx] heapq.heappush(heap, (-priority, arrive, tid, duration)) idx 1 if heap: neg_pri, arrive, tid, duration heapq.heappop(heap) current_time duration ans[tid] current_time return ans这段代码的思路是先把任务按到达时间排序维护一个小顶堆堆内以负优先级作为键这样优先级高的任务会先被弹出current_time表示当前系统时间当堆为空且下一个任务还没到就直接把时间跳到下一个任务的到达时间避免无意义的空转。整个过程是O(n log n)的足够应对大多数笔试数据范围。需要注意的一点是如果两个任务优先级相同题目往往会要求先到达的先执行所以堆元素里的第二个键可以用arrive如果还相同再用id保证同优先级时按照到达顺序或输入序号执行。你还需要自己确认如果任务在执行过程中来了更高优先级的任务是允许抢占还是非抢占。三模里那道题应该是非抢占的也就是一旦开始执行就不会被新任务打断。如果题目要求抢占式调度那么代码要改成每次新任务到达时就重新比较剩余时间逻辑会复杂一些。3.4 考拉兹类模拟题的实现与细节这道题的实现思路非常直白但要注意数据类型和步数上限。下面给出C和Python两种版本。C版#include iostream using namespace std; int main() { long long n; cin n; int steps 0; while (n ! 1) { if (n % 2 0) n / 2; else n n * 3 1; steps; if (steps 1000000) break; // 防止意外死循环 } cout steps endl; return 0; }Python版def collatz_steps(n: int) - int: steps 0 while n ! 1: if n % 2 0: n // 2 else: n n * 3 1 steps 1 # 预防卡死可加一个合理的上限 if steps 10**6: return -1 return steps注意Python中偶数操作要使用整除//如果写成/会变成浮点数不但慢还会引起精度问题。C里则要注意乘法溢出所以n字段必须定义为long long。如果你看到题目给的初始n特别接近10^9那么中间值可能会接近10^9乘以3甚至更大32位int绝对不够。我当年就见过有人用int结果本地测试小数据时全对一提交就WA还找不到原因。所以类型选择是这类题的第一道坎。很多题目还会继续追问“输出过程中出现过的最大值是多少”那就在循环里维护max_val变量每次更新max_val max(max_val, n)即可。把它们合在一起实现起来并不难关键是想清楚是否有必要记录历史值这取决于题目问的是什么。3.5 滚动数组DP的参考实现假如题目递推式是f(n) f(n-1) f(n-2) - f(n-3)初始给出f(0), f(1), f(2)求f(n)。那么代码可以这样写def get_f(n: int, f0: int, f1: int, f2: int) - int: if n 0: return f0 if n 1: return f1 if n 2: return f2 a, b, c f0, f1, f2 for _ in range(3, n 1): d c b - a a, b, c b, c, d return c这里a, b, c对应的是f(i-3), f(i-2), f(i-1)每算出一个d f(i)就把三数整体前移。这个做法的好处是无论n多大只要O(n)时间可承受空间永远是常数。不过需要注意递推式中涉及减法结果可能为负也可能增长很快。如果题目要求取模比如“对10^97取模”那么每次得出d之后就要立刻取模并且注意在c b - a时Python的负数取模结果仍然是正数直接用(c b - a) % MOD即可而C的负数取模会得到负值需要写成((c b - a) % MOD MOD) % MOD来保证结果正确。这是很多人容易翻车的地方。如果n特别大比如10^18那就不能再用O(n)的循环了这时候要用矩阵快速幂加速递推。三模的题目大概率不会考到这种程度但作为延伸如果你以后遇到这类题目就得会构造转移矩阵。递推式对应的矩阵形式为| f(n) | | 1 1 -1 | | f(n-1) | | f(n-1) | | 1 0 0 | * | f(n-2) | | f(n-2) | | 0 1 0 | | f(n-3) |用矩阵快速幂可以在O(log n)时间内求出第n项。我个人觉得就算三模不考你也值得掌握因为很多公司的笔试会把简单递推藏在高数据范围后面专门筛选那些只会递归的人。4. 常见问题与排查技巧实录4.1 多次Wrong Answer到底错在哪我在三模那会儿最崩溃的不是题不会做而是明明本地测试都对一交上去就WA。后来我总结了一套排查流程非常适合比赛和笔试中使用。第一检查数据范围。这是最容易被忽视的。题目里说n小于等于10^9那么你在计算答案的过程中会不会用到乘法如果用int存中间结果可能已经溢出最终答案自然不对。遇到这种题一律用long longPython选手则不用太担心但要注意浮点数与整数的区别。第二检查多组输入。题目可能没有明说“多组测试数据”但在线评测时往往会用多个用例同时验证。如果你的代码只处理了一个用例第二个用例开始就会错。所以养成习惯如果输入模板是按行读取尽量在主循环里用while处理到EOF除非题目明确说只有一个用例。第三检查输出格式。输出多余的空格或换行通常会被判为Presentation Error。虽然它不计为WA但会耗费你宝贵的试错次数。还有一种情况是要求“每个结果后跟一个换行”而你用了空格分隔也会WA。第四检查特殊边界。字符串为空、n等于0、数组长度为1、输入中有前导零、数据包含负值等等。在提交前逐一遍历这些边界手动构造最小的输入来本地跑一遍往往能立刻发现问题。我给一个通用的“自测模板”习惯写代码之前先设计几个用例普通情况比如在压缩字符串中用aaabbb期望输出a3b3。边界情况字符串只有一个字符a压缩后是a1长度等于或大于原串应输出原串a。极端情况全相同且长度很大比如aaaaa...压缩后应该明显更短。空输入如果题目没说不会给空串那if not s的分支不能省。这些用例写完再提交通过率会高很多。4.2 数组越界和空指针的防范技巧在线编程题中数组越界是另一种高发错误。尤其是C/C数组越界通常不会当场崩溃而是会覆盖相邻内存造成难以捉摸的错误。我见过有人写for (int i 0; i n; i)访问a[n]而数组定义长度只有n这种问题很难发现。解决方法是在写循环时反复确认上下界。比如访问a[i]和a[i1]时循环条件一定要是i1 len而不是i len。在Java里一旦越界会抛出ArrayIndexOutOfBoundsException相对容易定位但Python的列表越界会抛IndexError也很好发现。真正危险的是C这种不强制检查的语言。空指针问题在Java中较常见比如使用一个对象前没有判断是否为null。虽然在笔试的纯算法题中不常遇到但如果题目要求设计数据结构比如链表操作那就要注意边界节点的判空。我的建议是在debug时打印关键位置的变量值不要只靠脑子想。在线OJ上可以先用小样例暴力输出中间结果肉眼确认没问题后再删掉调试代码。4.3 超时的常见原因与优化方向如果你碰到的是TLETime Limit Exceeded那问题往往出在算法复杂度上。比如一道题如果n等于10^5O(n^2)的算法就会超时必须把复杂度降到O(n log n)或O(n)。这种情况在三模里也很常见尤其是模拟题如果你真的一个时间点一个时间点去推数据大一点就GG。我前面提到的用优先队列模拟任务调度就是典型的从O(total_time)优化到O(n log n)的思路。还有一种超时是语言本身的输入输出太慢。Python的input()和print()在大量数据时不如sys.stdin.read()和sys.stdout.write()。C的cin/cout如果不同步也会比scanf/printf慢很多。虽然现在的OJ大多放宽了时限但保险起见还是用更快的方式为好。我之前在三模的某道题里就用sys.stdin.buffer.read()比sys.stdin.read()还要快一些数据量很大时差距更明显。4.4 从WA到AC的调试实战记录我说一个真实的例子。当时有一道题要求统计一个整数数组中有多少对元素的和等于目标值k。我第一版写的O(n^2)双重循环提交后TLE了。然后我想到用哈希表遍历数组对于每个元素num看k-num在不在哈希表里。这个思路本身没问题但我第一次写时是先全部塞进哈希表再遍历这会导致同一对元素被统计两次而且存在重复值的数组还容易把三元组也算进去。我当时的修复方案是“边遍历边统计”也就是先查k-num的计数再把当前num加入哈希表。这样就保证了每一对元素只会统计一次而且不需要考虑下标先后问题。修改之后又出现了一个边界如果num等于k-num比如k6数组里只有一个3那么理论上没有配对但如果先插入再查询或者先查询后插入但不做计数控制可能就会把自己也算进去。这个问题的本质是“同一元素不能使用两次”。正确做法是查询的是之前已经遍历过的元素而不是当前的元素这样才能避免使用同一个元素两次。这个小案例说明很多题目的正确解法并不是难想而是细节容易出错。当你WA到怀疑人生时不要急着改代码先回过来把题目的约束再读三遍尤其是“是否可以重复使用元素”“是否要求下标不同”这些限定词往往就是关键。4.5 考场上的时间分配与提交策略还有一点经验想分享虽然不算技术但很实用。三模的题目数量通常是四道左右时间有限如果一道题卡了半小时还没思路果断跳过先做后面的题。笔试的评分很多时候是按通过的测试用例比例给分所以即使你只过了部分用例也比交白卷强。我当时的策略是先花5分钟把所有题都看一遍标注每道题的难度和可能用到的算法。从最容易拿分的题目开始做保证至少有一道题是完整AC的。遇到难题如果想到了一个O(n^2)的解法数据范围不大就先写能拿部分分就拿部分分如果数据范围大那就先写一个暴力版本保底再思考优化。提交前至少留5分钟检查输入输出格式和边界用例。4.6 牛客模考成绩不理想还有救吗最后想再说一句三模只是模拟成绩不理想不代表秋招就没救。我当年三模只做了两道半当时特别沮丧但后来总结发现那两道半其实帮我暴露了很多问题读题不仔细、边界处理差、数据结构不熟练。于是我把每道错题都整理成笔记写上错误原因和正确思路之后又去刷了牛客的历年真题和类似题型大概两周后水平就有了明显提升。所以如果你也正在被模考虐恭喜你这是提前暴露问题的机会比在正式笔试中踩坑要幸运得多。我的建议是准备一个错题本不用抄题只要记录知识盲区和坑点比如“以后遇到XX条件记得用long long”“输出要求严格换行”“模拟题先看是否支持抢占”等等。到正式笔试前翻一遍效果非常好。我个人现在碰到复杂题目还是会下意识使用三模时总结的那套结构化思考方式场景模拟先抽象状态字符串处理先想边界递推关系先想滚动数组排序问题先想稳定性和复杂度。这套方法论比记住某道题的答案有价值得多。