这几天整理求职资料翻到了2018年牛客模考一模的B卷编程题集合。乍看是几年前的题目但一路刷下来发现当年考的东西到现在依然是笔试标配字符串、数组、排序、动态规划换一层皮反复出现。这篇文章我用自己的方式把这套题拆了一遍不写答案流水账重点说每类题型的破题思路、代码写法以及当年在牛客上模考时踩过的那些坑。无论你是准备校招的新人还是想跳槽的老兵只要还在刷题这套经典题都值得重新过一遍。1. 先看看这套题里藏着哪些考点1.1 从考试形式看这套题的门道牛客的编程题基本都是ACM模式也就是你需要自己处理输入输出。这一点和LeetCode的只写核心函数不一样B卷的题目同样延续了这个风格。2018年那会儿很多第一次参加牛客模考的同学题明明会做但卡在输入解析上拿不到分非常可惜。这套题集合汇集了几道不同难度的编程题目的是模拟真实笔试环境既有纯模拟题也有需要绕几个弯的算法题。从命题规律来看B卷的难度通常比A卷稍微高一点不是那种一眼能看出答案的题但也没有到竞赛级别。它考察的核心是“基础算法熟练度”和“编码严谨性”尤其是边界条件处理。比如字符串为空怎么办数组只有一个元素怎么办这些在牛客的判题系统里都会被单独测到。1.2 核心考点清单与备考优先级我做完这套题后把考点整理成了一个优先级表。笔试时间有限分清楚轻重缓急能省出很多时间。优先级考点主题典型出现位置复习建议P0字符串处理与模拟第1、2题附近必须拿满多练库函数P0数组基本操作排序、去重、合并必须拿满注意原地操作P1双指针与滑动窗口数组类优化题推荐掌握笔试高频P1简单动态规划分步骤计数题至少能写状态转移P2排序算法自定义比较器结构体排序加分项部分题目用得到这套题里没有出现特别复杂的图论或线段树说明命题人想让大部分人有机会写出正解同时通过一些细节拉开区分度。备考时别一上来就死磕难题先把P0和P1的题型练到肌肉记忆再往深了走。1.3 一道题一个坑题型速览表为了后面展开方便我把这套题涉及的题型做了一个速览后面几个章节会逐个细讲字符串类找子串、循环位移、括号匹配。数组类合并有序数组、逆序对、找第K大。动态规划类最长上升序列、背包变形、矩阵最小路径和。模拟类设计一个队列/栈或者按照规则逐步计算。每一类都有自己的“坑”。字符串题坑在字符偏移数组题坑在越界DP题坑在初始状态。下面我按题型逐个展开顺便放一些可以直接用的代码模板。2. 字符串与模拟题笔试里的“送分题”怎么拿满分2.1 字符串题的通用解题框架字符串题在笔试中属于性价比最高的题。它没有太深的算法思维但特别考验细心程度。我总结了一个百试不爽的四步流程先看题确认是“操作题”还是“匹配题”然后确定用什么数据结构存储通常就是字符数组或StringBuilder接着把特殊输入空串、单字符、全重复字符列出来最后再动手写逻辑。很多新手拿到题直接开始写写到一半发现忘记考虑大小写、空格、Unicode结果改来改去。正确做法是先花两分钟把边界条件在草稿纸上写出来。比如字符串循环位移这道题题目会给你一个字符串和一个位移量K让你把每个字母往后移动K个位置。看起来很简单但K可能非常大可能超过26这时候必须取模也可能为负数要统一处理成正数还可能包含非字母字符需要跳过。不列全边界条件写出来的代码一定有问题。2.2 代码模板字符串按规则位移这里我以字符串循环位移为例给一个可复用的模板。这题在牛客B卷里是一道经典入门题考察字符串遍历和ASCII码换算。import sys def shift_char(c: str, k: int) - str: if c.islower(): return chr((ord(c) - ord(a) k) % 26 ord(a)) if c.isupper(): return chr((ord(c) - ord(A) k) % 26 ord(A)) return c def solve(): line sys.stdin.readline().strip() if not line: return parts line.split() if len(parts) 2: return s parts[0] k int(parts[1]) % 26 # 先对26取模防止大数 result .join(shift_char(c, k) for c in s) print(result) if __name__ __main__: solve()代码关键点有两个。第一ord和chr是基础API一定要记熟。第二k int(parts[1]) % 26这里取模不只是为了效率更是为了防止在字符运算时得到负数或超过ASCII可打印范围。第三if not line处理了空输入这在牛客的系统里必须要有否则你本地测试通过了线上却可能报索引错误。2.3 模拟题最容易错的三个地方模拟题指的是那些没有复杂算法、按题目给的规则一步步执行的题。B卷里的括号匹配、出栈序列判断都属于这类。这类题思路简单但出错率极高我总结了三个高频雷区。雷区一是更新状态的时机。比如括号匹配用栈来维护遇到左括号入栈遇到右括号出栈。问题在于很多人在pop之前没检查栈是否为空结果右括号先出现时直接报错。正确的逻辑是遇到右括号时如果栈为空则立即判定不合法否则pop并检查pop出来的左括号是否和当前右括号匹配对只有一种括号的题可以省略。这个检测顺序非常关键。雷区二是输入可能有空格或换行。牛客的输入经常有多余空格有些人用input()读入后不strip()导致字符串长度判断出错。建议所有输入处理统一写sys.stdin.readline().strip()。雷区三是死循环。比如模拟约瑟夫环问题时循环条件写错导致出不了循环超时被判0分。这种问题只能靠模拟前在纸上画出几个关键状态来解决不要直接写代码。3. 数组与排序暴力解法之外的思维升级3.1 数组类题目的四步解法数组题几乎每次笔试都有而且经常不止一道。B卷里有关数组合并、去重、寻找第K大的题。拿到数组题我习惯先问四个问题数据范围多大是否有序是否允许额外空间是否需要稳定排序这四个问题决定了你用什么算法。如果数组规模在10^5以下O(n^2)的暴力方法可能勉强能过但如果到10^6就必须用O(nlogn)或O(n)算法。B卷的不少题暴力的思路很好想但通过率很低原因就是超时。所以写题前要先根据数据范围估算复杂度这是职业选手和业余选手的分水岭。举个例子找数组中的逆序对数量。暴力做就是两层循环复杂度O(n^2)当n10^5时肯定超时。稍微想一想就知道可以用归并排序在合并过程中统计逆序对复杂度降到O(nlogn)。很多第一次考的同学吃亏在不会估算复杂度以为暴力能过结果白丢分。3.2 典型题目合并两个有序数组B卷有一道经典的合并两个有序数组题要求把数组A和B合并到A中A的长度足够容纳两个数组的元素。这题在LeetCode上是88题在牛客上换了一种输入输出形式出现。最容易想到的方法是新建一个数组把A和B的元素放进去再排序但这样空间复杂度是O(n)而且没有利用“原数组有序”这个条件。更聪明的做法是从后往前填充。因为A的后半部分是空的我们可以用两个指针分别指向A和B的末尾比较大小把较大的元素放到A的末尾。这样不需要额外空间时间复杂度O(n)。def merge(nums1, m, nums2, n): i, j, k m - 1, n - 1, m n - 1 while i 0 and j 0: if nums1[i] nums2[j]: nums1[k] nums1[i] i - 1 else: nums1[k] nums2[j] j - 1 k - 1 while j 0: nums1[k] nums2[j] j - 1 k - 1这里最容易被忽略的是最后那个while j 0。如果B数组没遍历完需要把剩余元素复制过来反之如果A数组没遍历完是不用动的因为它们已经在正确位置。这个细节就能区分零分和满分。我当年就栽在这里以为只要主循环结束就完事了结果漏了剩余元素。3.3 从两数之和到三数之和尺取与去重B卷里有一道扩展题在一个排序数组中找三数之和等于目标值。它其实是LeetCode 15题的变体。两数之和可以用哈希表O(n)搞定但三数之和直接三层循环是O(n^3)肯定不行。正确思路是固定一个数然后对剩下的区间用双指针夹逼。关键难点在于去重。题目要求结果不能包含重复三元组。如果你只是简单地用Set去重可能超空间更好的办法是在指针移动时跳过重复元素。我在牛客上提交时第一次就是因为没跳过重复导致输出多了几组被判错。def three_sum(nums, target): nums.sort() n len(nums) res [] for i in range(n - 2): if i 0 and nums[i] nums[i - 1]: continue left, right i 1, n - 1 while left right: s nums[i] nums[left] nums[right] if s target: res.append([nums[i], nums[left], nums[right]]) while left right and nums[left] nums[left 1]: left 1 while left right and nums[right] nums[right - 1]: right - 1 left 1 right - 1 elif s target: left 1 else: right - 1 return resi 0 and nums[i] nums[i-1]这行是去重的关键。双指针的移动也要跳过重复值。这种细节只能靠平时多踩坑积累没有捷径。4. 动态规划状态定义才是灵魂4.1 一眼认出DP题动态规划题在B卷里占了两到三道属于压轴类型。很多同学一看“最优”“最大”“多少种”就懵了其实DP题有很强的特征题目往往可以拆成重叠的子问题。怎么识别一个简单的方法是如果这道题能用递归做且递归过程中会重复计算它大概率就是DP题。比如求最长上升子序列长度你会想“以某个元素结尾的最长子序列长度”这就是状态。这个状态可以由前面所有比它小的元素推导出来形成递推关系。DP难就难在状态定义。定义好了转移方程自然就出来了定义不好代码写出来像一团乱麻。4.2 最长上升子序列的两种写法最长上升子序列LIS是B卷中的一个压轴题。最经典的DP写法是O(n^2)def length_of_lis(nums): n len(nums) if n 0: return 0 dp [1] * n res 1 for i in range(1, n): for j in range(i): if nums[j] nums[i]: dp[i] max(dp[i], dp[j] 1) res max(res, dp[i]) return res这个写法不复杂但面试官更希望你写出O(nlogn)的贪心加二分版本。它的核心是维护一个d数组d[i]表示长度为i1的上升子序列中末尾元素的最小值。遍历每个数如果它比d的末尾大就追加否则用二分查找替换第一个比它大的位置。我在牛客模考时先写了O(n^2)的版本能过大部分用例但最后两个大数据用例超时了。后来改成二分版本才通过。这道题给了一个很重要的教训笔试时如果看到n的范围在10^5以上就别犹豫直接上nlogn解法。4.3 遇到背包变体怎么切题B卷还有一道背包问题的变体——有若干物品每个物品只能选一次问能否凑出某个总价值。这就是典型的0/1背包状态定义是dp[j]表示容量为j时能装的最大价值。但题目有时候会变成“有多少种凑法”那么dp的含义就要从“最大价值”改成“方案数”。关键点在于遍历顺序。0/1背包要求外层遍历物品内层从大到小遍历容量防止同一个物品被重复选择。而完全背包每个物品无限次则要求内层从小到大遍历。这个区别我记了三年才不出错最简单的方法就是做一道题理解一遍不要死记。def knapsack_ways(weights, target): dp [0] * (target 1) dp[0] 1 for w in weights: for j in range(target, w - 1, -1): dp[j] dp[j - w] return dp[target]这题如果问的是“能否”可以把dp变成布尔数组用或运算转移。如果dp[j]已经为True那么dp[jw]也会为True。学会根据题目要求调整dp数据的类型和转移方式比背模板重要得多。5. 笔试现场踩坑录音输入输出与边界条件5.1 ACM模式下的输入输出坑牛客的模考环境要求你写完整的程序包括处理输入和输出。这是和LeetCode最大不同的地方。很多本地IDE能跑的代码粘贴到牛客上就编译不过大概率是包名、类名、输入输出格式的问题。用Python的话推荐统一使用sys.stdin.read()或者sys.stdin.readline()。如果一次性读入多行数据可以使用sys.stdin.read().split()把所有空白分隔的字符串取出来再按顺序解析。这样能避免不同系统间换行符的差异。举个例子如果输入描述是“第一行一个整数T表示测试用例数接下来T行每行两个整数a和b”你应该这样写import sys data sys.stdin.read().split() if not data: sys.exit() t int(data[0]) idx 1 for _ in range(t): a int(data[idx]); b int(data[idx1]); idx 2 # 处理这样即使某一行有多个空格也能正确读取。注意一定要判断if not data因为牛客有个别用例是空输入不判断会直接抛异常。5.2 数组下标越界的预防B卷的数组题大多需要区间访问很容易越界。一个典型的错误是在循环里写nums[i1]却没有保证i n-1。要预防这个问题最好的方式是先画出区间示意图。以滑动窗口求最大值为例如果窗口大小为k数组长度为n那么窗口起始位置i的范围是0到n-k而不是0到n-1。很多人写循环时没注意这个上限导致读到了不存在的元素。还有Python的负数索引是个陷阱。list[-1]在脚本语言里表示倒数第一个但这在C里是越界错误。如果你同时写几种语言务必小心。我在实际模考时习惯在关键数组访问前加一个断言逻辑比如assert i len(arr)本地调试时能快速发现越界点提交前再把assert删掉。这个方法笨但有效。5.3 超时不是玄学是复杂度失控很多同学看到“超时”两个字就头疼觉得自己代码本地运行很快。本地快不代表线上快。牛客的数据量可能是本地的几百倍你的O(n^2)循环到了线上就变成天文数字。比如求字符串中出现次数最多的字符有人用了两层循环每次遍历字符串统计一个字符的次数看起来也没几万次操作但如果字符串长度是10^6两层循环就是10^12次操作当然超时。正确做法是用哈希表做一次遍历统计复杂度O(n)。判断是否可能超时有一个快速估算1秒大概能跑10^7到10^8次简单运算。如果n10^5O(n^2)是10^10必死O(nlogn)大约是10^6次稳过。看见题先算这个账能帮你节省大量试错时间。6. 模考之后怎么复盘才有用6.1 三遍刷题法模考的意义不只是看分数而是暴露问题。我做这套B卷时用了“三遍刷题法”。第一遍按真实考试状态计时完成不管对错把每道题实际花费的时间记下来第二遍是考后当天把每道题重新思考一遍不看答案直到自己写出能通过的代码第三遍是在一周后把做错的题拿出来直接写如果还能写对说明真的掌握了否则说明只是背了答案。这个方法能帮你筛出“假懂”的题。很多题你看答案时觉得简单“原来用字典就行”但一周后让你自己写可能还是卡在初始化和边界上。三遍法就是用来消灭这种情况的。6.2 建立错题本的正确姿势从小到大都在说错题本但刷题错题本和上学时不太一样。我不建议抄题而是记录“失败模式”。比如我在这套B卷中的错题记录格式是题目类型动态规划错误点状态初始化用0而不是1导致方案数为0同类题背包方案数、走格子方案数预防措施初始化时思考“空集”和“空路径”对应的方案数这样一条记录不到五十字但每次模考前翻一遍能快速唤醒记忆。有人喜欢把完整代码贴到笔记里其实没必要代码是公开的你能找到重要的是记录你的思维盲点。6.3 关于牛客模考我的几点观察牛客的模考系统有一个好处是实时排名和分数分布。2018年的B卷整体通过率并不高特别是最后一道DP题通过率不到10%。这说明大部分人不是不会而是时间分配不合理前面简单题上花了太多时间导致压轴题没时间写。我自己的建议是如果目标是及格通过60%的用例优先保证前面所有简单和中档题的正确性压轴题骗出部分用例的分数即可如果目标是高分就需要在简单题上做到手速飞快把省下的时间留给DP。简单题要做到什么程度看到题直接开始敲不犹豫不返工。7. 一些零碎但重要的提醒这套2018年的牛客模考编程题集合虽然过去了几年但它的题型结构和考察点依然是今天校招笔试的缩影。如果你现在准备刷题我建议不要只盯着新题而要把这些经典题当作“体检表”检验自己对字符串、数组、DP这些基础模块的掌握程度。有一点我想特别提醒不要因为某道题以前做过就直接跳过闭着眼睛写一遍看能不能一遍通过。很多看着眼熟的题实际写的时候会卡在细节上。这也是我重刷这套B卷最大的收获。如果你用的是Python平时多积累标准库的用法比如collections.Counter、bisect、heapq这些在笔试中能帮你省去大量手写逻辑的时间。但注意不要为了简洁而牺牲可读性毕竟笔试的时候如果出了bug结构清晰的代码更好查。最后再分享一个小技巧每次在牛客上做完一套题不要急着关页面把每一道题的耗时记录下来。我通常会把总耗时控制在70%的考试时间内留一点余量应对意外。久而久之你会形成自己的做题节奏这才是在真实笔试中最宝贵的财富。