牛客B卷编程题复盘：字符串、数组、DP的破题思路与避坑指南

这几天整理求职资料，翻到了2018年牛客模考一模的B卷编程题集合。乍看是几年前的题目，但一路刷下来发现，当年考的东西到现在依然是笔试标配：字符串、数组、排序、动态规划，换一层皮反复出现。这篇文章我用自己的方式把这套题拆了一遍，不写答案流水账，重点说每类题型的破题思路、代码写法，以及当年在牛客上模考时踩过的那些坑。无论你是准备校招的新人，还是想跳槽的老兵，只要还在刷题，这套经典题都值得重新过一遍。

1. 先看看这套题里藏着哪些考点

1.1 从考试形式看这套题的门道

牛客的编程题基本都是ACM模式，也就是你需要自己处理输入输出。这一点和LeetCode的只写核心函数不一样，B卷的题目同样延续了这个风格。2018年那会儿，很多第一次参加牛客模考的同学，题明明会做，但卡在输入解析上拿不到分，非常可惜。这套题集合汇集了几道不同难度的编程题，目的是模拟真实笔试环境，既有纯模拟题，也有需要绕几个弯的算法题。

从命题规律来看，B卷的难度通常比A卷稍微高一点，不是那种一眼能看出答案的题，但也没有到竞赛级别。它考察的核心是“基础算法熟练度”和“编码严谨性”，尤其是边界条件处理。比如字符串为空怎么办，数组只有一个元素怎么办，这些在牛客的判题系统里都会被单独测到。

1.2 核心考点清单与备考优先级

我做完这套题后，把考点整理成了一个优先级表。笔试时间有限，分清楚轻重缓急能省出很多时间。

这套题里没有出现特别复杂的图论或线段树，说明命题人想让大部分人有机会写出正解，同时通过一些细节拉开区分度。备考时别一上来就死磕难题，先把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)，当n=10^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 res

i > 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]表示长度为i+1的上升子序列中末尾元素的最小值。遍历每个数，如果它比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[j+w]也会为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[idx+1]); idx += 2 # 处理

这样即使某一行有多个空格也能正确读取。注意一定要判断if not data，因为牛客有个别用例是空输入，不判断会直接抛异常。

5.2 数组下标越界的预防

B卷的数组题大多需要区间访问，很容易越界。一个典型的错误是在循环里写nums[i+1]，却没有保证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次简单运算。如果n=10^5，O(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%的考试时间内，留一点余量应对意外。久而久之，你会形成自己的做题节奏，这才是在真实笔试中最宝贵的财富。