牛客模考五模编程题复盘：高频算法考点与笔试技巧

2023年秋招我的刷题计划里一直留着牛客的模考卷。原因很简单正式笔试前需要有一套和真实环境一样有输入输出、有AC率、有排行榜的题目来模拟一遍。牛客模考五模的编程题集合是我印象比较深刻的一套四道编程题覆盖了字符串处理、贪心区间、搜索、动态规划这些笔试常客难度梯度设置得也比较像大厂正式笔试。对于正在准备春招、暑期实习笔试或者刚开始刷题的人这套题的价值不只是“做了几道题”而是能帮你快速定位自己在哪些考点上还处于“似懂非懂”的状态。本文将基于这套题里最有代表性的几道题还原我的解题思路、现场踩过的坑以及考后复盘时的总结。代码直接用Python写因为牛客笔试环境里用Python的同学越来越多而且这套题用Python实现起来足够清晰。1. 2023五模题集在笔试复习中的定位1.1 模考卷的构成与难度分布牛客的模考一般是按照主流互联网公司笔试节奏设计的常规构成是选择题加编程题编程题通常四道难度从签到题到压轴题逐渐递增。五模这套编程题集合给我的整体感觉是前两道属于“基本功”第三道开始出现搜索和状态设计最后一道如果不熟悉动态规划很容易写出一份超时或者答案错误的代码。我当时整理了这套题的考点分布大致可以画成这样的表格题号核心考点推荐解法难度第一题字符串处理一次遍历模拟简单第二题区间调度贪心 排序中等第三题二维网格连通块DFS / BFS中等第四题完全背包 / 最少硬币一维动态规划较难这个分布其实代表了笔试编程题的典型思维层次先看你会不会处理基础输入和字符串切片再看你有没有“排序后贪心”的意识然后考你能不能把图论模型套到二维网格上最后用动态规划筛掉只会暴力枚举的人。1.2 为什么值得专门写一遍很多人刷题习惯在 LeetCode 上按题号刷但牛客这类 ACM 风格平台对笔试的还原度更高。LeetCode 的核心函数模板帮你封装好了输入输出而牛客要求自己处理标准输入流一个多余的换行、一次错误的split都有可能让你交出一份“本地能跑提交 CE/WA”的代码。五模编程题最大的价值就是让你提前熟悉笔试系统的脾气。它会告诉你不是思路对了就能 AC输入读取、边界值、循环退出条件任何一个环节出问题都是零分。我在正式秋招前把五模完整做了一遍考场上遇到类似题时心态确实稳了很多。2. 高频考点的底层逻辑2.1 字符串处理从“模拟到恶心”到“一行函数搞定”第一题考字符串压缩这类题在笔试里出现频率极高。它本身不难但很容易被“复杂模拟”带偏。比如有些人看到题目就开始写循环套循环还要考虑字符的边界情况最后代码写得又长又容易漏。真正高效的思路是单次遍历记录当前字符和出现次数当字符变化时把结果写入列表最后统一拼接。Python 里字符串是不可变对象每次都可能产生新的对象所以别用字符串不断拼接而是先存到列表里再.join()。这不是炫技而是为了在数据量大的时候避免不必要的性能损耗。这类题还有一个隐藏考点读题。有时候题目要求“连续相同字符超过一次才计数”有时候要求“全部字符都要带上次数”。我在五模时就是因为没注意题目的输出格式要求把a3b2c1写成了a3b2c白丢了一次提交。所以写字符串题之前先花十秒钟看清楚输出示例。2.2 贪心与排序为什么排序方向错了就全盘皆输第二题是经典的“最多能参加多少个会议”类问题。这类题的结论很明确按结束时间升序排序然后贪心选择结束时间最早的会议再跳过所有与它冲突的会议重复这个过程。关键点是排序依据。我见过不少同学按开始时间排序然后发现答案不对。其实可以自己构造一个反例会议A是[0, 10]会议B是[1, 2]会议C是[3, 4]。如果按开始时间排会先选A但A一个会议就占满了整天按结束时间排会先选B再选C能得到最优解“2个会议”。这个例子很直白地说明了贪心策略的局部最优是否能推到全局最优。结束时间越早给后面留下的时间越多这是直觉也是证明。笔试中遇到区间类题目先判断能不能用贪心再立刻想到排序。2.3 搜索与动态规划先建模再动手第三题和第四题分别是网格连通块和最少硬币。它们看起来完全不同但都有一个共同点先建模再套模板。“岛屿数量”就是二维网格里的连通块数量问题建模为无向图每个为1的格子是一个节点上下左右相邻的格子之间连边然后统计有多少个连通分量。DFS、BFS、并查集都能做。现场最容易出问题的是忘记把访问过的格子标记为“已访问”导致无限递归或者重复计数。“最少硬币”是典型的完全背包变体。硬币数量无限要凑出总金额求最少硬币数。暴力递归会超时需要从底向上构建DP数组dp[i]表示凑出金额i需要的最少硬币数初始为无穷大dp[0]0。状态转移是dp[i] min(dp[i], dp[i - coin] 1)反过来遍历每种硬币即可。写这类题时先确定状态定义再写转移方程最后检查初始化。3. 五道代表性题目的完整复盘3.1 字符串压缩一场关于“输出格式”的较量题目描述给定一个仅由小写字母组成的字符串将其中连续出现的相同字母压缩为字母出现次数的形式例如aaabbc输出a3b2c1。输入一行字符串长度不超过1000输出压缩后的结果。输入示例aaabbc输出示例a3b2c1解题思路一次遍历维护当前字符cur和计数器cnt。当遇到新字符时把cur str(cnt)加入结果列表然后重置。遍历结束后再处理最后一组字符。这样可以保证时间复杂度 O(n)空间复杂度 O(n)。参考代码s input().strip() if not s: print() exit() res [] cur s[0] cnt 1 for ch in s[1:]: if ch cur: cnt 1 else: res.append(cur str(cnt)) cur ch cnt 1 res.append(cur str(cnt)) print(.join(res))复盘要点我提交时犯过一个低级错误没有判断空字符串。虽然题目说字符串非空但我还是习惯性加了保护。另一个容易丢分的地方是“如果某个字符出现一次输出a1还是省略成a”这个必须严格按题目要求来不确定时多看一眼示例。牛客的判题很严格输出多了空格或者少了换行都可能判错。3.2 会议安排贪心排序证明题目描述给定n个会议的开始时间和结束时间每个会议用[start, end]表示你最多能参加多少个互不重叠的会议会议结束时间严格大于开始时间n 10^5。输入示例4 1 2 3 4 0 6 5 7输出示例2解题思路按照结束时间从小到大排序然后遍历。记录当前已选择的最后一个会议的结束时间last_end如果当前会议的开始时间大于等于last_end则选择它并更新last_end。这个策略能在同样结束时间下选更多会并且留下的剩余时间最多。参考代码n int(input()) meetings [] for _ in range(n): s, e map(int, input().split()) meetings.append((s, e)) meetings.sort(keylambda x: x[1]) ans 0 last_end -1 for s, e in meetings: if s last_end: ans 1 last_end e print(ans)复盘要点如果题目改成“最多能安排多少个不重叠区间”那这里选还是就要看题目定义。开会通常认为[0, 1]和[1, 2]是可以无缝衔接的所以用s last_end。如果要求严格不重叠首尾不能相接就要改成s last_end。这类细节在笔试里经常出现建议拿到题目先标记清楚边界条件。3.3 岛屿数量DFS 递归与现场保护题目描述给定一个m x n的二维网格1表示陆地0表示水域。岛屿由相邻上下左右的陆地组成请你计算岛屿的数量。m, n 200。输入示例4 5 11000 11000 00100 00011输出示例3解题思路遍历整个网格遇到一个1就把它所在连通块里的所有1都改成0或者用visited数组标记岛屿数量加一。这里我用 DFS 实现因为代码量少适合笔试。参考代码import sys sys.setrecursionlimit(1000000) def dfs(i, j, grid, m, n): if i 0 or i m or j 0 or j n or grid[i][j] 0: return grid[i][j] 0 dfs(i 1, j, grid, m, n) dfs(i - 1, j, grid, m, n) dfs(i, j 1, grid, m, n) dfs(i, j - 1, grid, m, n) m, n map(int, input().split()) grid [list(input().strip()) for _ in range(m)] ans 0 for i in range(m): for j in range(n): if grid[i][j] 1: ans 1 dfs(i, j, grid, m, n) print(ans)复盘要点DFS 的递归深度在这个题目里最多是m*n最大 40000Python 默认递归深度可能不够所以我写了sys.setrecursionlimit。如果不想冒险可以用栈模拟 DFS或者换成 BFS。现场写的时候我还发现grid[i][j] 1这种判断在二维字符数组里很顺手但如果是整数矩阵记得不要写成双引号和单引号混用。这类题的核心在于“访问过就把值改掉”避免重复计算。3.4 找零问题完全背包的一维优化题目描述给定不同面额的硬币coins和一个总金额amount返回凑成总金额所需的最少硬币个数。如果无法凑成返回-1。每种硬币数量无限amount 10000。输入示例3 1 2 5 11输出示例3解题思路使用一维数组的完全背包动态规划。dp[i]表示凑出金额i的最少硬币数初始化为一个很大的数比如float(inf)dp[0] 0。遍历每种硬币再遍历金额i从coin到amount更新dp[i] min(dp[i], dp[i - coin] 1)。最终dp[amount]如果是无穷大返回-1。参考代码n int(input()) coins list(map(int, input().split())) amount int(input()) INF 10**9 dp [INF] * (amount 1) dp[0] 0 for coin in coins: for i in range(coin, amount 1): if dp[i - coin] 1 dp[i]: dp[i] dp[i - coin] 1 print(-1 if dp[amount] INF else dp[amount])复盘要点这里最容易搞错的是内外层循环的顺序。如果是“每种硬币只能用一次”的 0/1 背包内层要倒序遍历但本题硬币无限是典型完全背包内层正序遍历才能让同一个硬币被多次使用。很多人死记硬背“正序还是倒序”其实可以想一下dp[i - coin]如果已经使用了当前硬币正序遍历时还能继续基于它再选同一个硬币就实现了无限取用。这样理解比背结论牢靠得多。3.5 括号匹配栈的边界处理题目描述给定一个只包含(、)、[、]、{、}的字符串判断括号序列是否合法。字符串长度不超过10000。输入示例([{}])输出示例true解题思路用栈维护当前未匹配的左括号。遍历字符串时如果是左括号就入栈如果是右括号判断栈顶是否是对应的左括号不对应或者栈为空都表示不合法。遍历结束后如果栈为空则合法否则存在未匹配的左括号。参考代码s input().strip() stack [] pairs {): (, ]: [, }: {} for ch in s: if ch in ([{: stack.append(ch) else: if not stack or stack[-1] ! pairs[ch]: print(false) break stack.pop() else: print(true if not stack else false)复盘要点Python 的for...else在笔试里用得好会很省事else块在循环没有被break中断时执行正好用来处理合法情况。容易忽略的细节包括空栈时遇到)属于非法最后栈里还有(也属于非法。我现场第一次提交时忘了if not stack直接stack[-1]导致运行时错误。在线笔试遇到这类异常不会友好提示所以边界判断一定要写在前面。4. 在线笔试的输入输出与边界值陷阱4.1 牛客的输入格式到底该怎么读很多第一次用牛客做题的人最不适应的就是标准输入。LeetCode 给你一个函数参数都传好了但牛客要求你从标准输入里自己解析。以 Python 为例我常用的模板是import sys def solve(): data sys.stdin.read().split() # 按需求解析 data 列表 pass if __name__ __main__: solve()sys.stdin.read().split()会把全部输入切分成一个个 token好处是处理类如“第一行一个数n第二行n个数”的格式时非常方便。缺点是如果要逐行处理带空格的字符串就不能简单用split这时候要配合input().strip()或者sys.stdin.readline。共享同一个input()和sys.stdin.readline的区别在数据量大时很明显。对于万级以上的输入input()底层调用的解释器逻辑偏慢而sys.stdin.readline直接读一行速度更快。我一般在大数据量题目里固定使用sys.stdin.readline。import sys input sys.stdin.readline n int(input()) arr list(map(int, input().split()))另外读到的每行末尾可能带有\n如果题目要求逐字符串处理一定要strip()。如果目标字符串本身就是空行strip()后得到空字符串也要做好判断避免对空字符串取下标时报错。4.2 容易被忽略的边界值编程题判题用例特别喜欢在边界上设陷阱。五模这套题里我遇到的边界问题包括但不限于字符串长度为 1压缩循环里不会进入内部else最后必须把最后一组字符写入结果。会议数量为 0last_end初始值要小于任何合法开始时间否则会漏选第一个会议。网格只有一行或一列DFS 的四个方向里有两个方向会越界必须有边界判断。金额为 0dp[0] 0此时不需要任何硬币答案应该是 0而不是-1。括号序列为空栈为空合法输出true。输入行末有空格如果用strip()处理会丢失字符串内部的合法空格吗如果题目要求保留空格就不能对所有字符串无脑strip()只能去掉末尾换行。笔试时最冤的丢分不是不会做而是没有把题目描述里的每一个“空”“重复”“0”当回事。我通常会在草稿纸上单独列一个边界值清单写完代码后逐个代入验证。4.3 超时与递归过深的处理方法有些同学思路正确但 TLE超时常见原因有两个。第一个是不加判断的暴力枚举。比如最少硬币问题里直接用递归穷举所有组合金额稍微大一点就直接指数爆炸。第二个是 Python 递归爆栈DFS 在最大网格上可能递归几万层不主动提高递归上限会有RecursionError。超时的优化思路也分两种对暴力枚举问题先检查是否存在重叠子问题有就想能不能用动态规划或记忆化搜索。对 DFS如果递归深度不可控就改成显式栈。显式栈写法稍微长一点但不会受限于递归深度。def num_islands(grid, m, n): dirs [(1,0),(-1,0),(0,1),(0,-1)] ans 0 for i in range(m): for j in range(n): if grid[i][j] 1: ans 1 stack [(i, j)] grid[i][j] 0 while stack: x, y stack.pop() for dx, dy in dirs: nx, ny x dx, y dy if 0 nx m and 0 ny n and grid[nx][ny] 1: grid[nx][ny] 0 stack.append((nx, ny)) return ans单看代码量并不比 DFS 多多少但稳定性更高。如果追求稳妥我推荐这类搜索题在笔试环境里优先考虑显式栈或 BFS。5. 模考之后最有效的复盘姿势5.1 给错题打标签模考不是做完对着答案看一遍就结束而是要对错题做分类。我习惯把每道错题标记为四类之一不会做完全没有思路需要补对应专题。会做但超时算法复杂度有问题需要优化。思路对但答案错大概率是边界条件、输入输出、初始值的问题。代码对但提交失败可能是环境差异比如用了较新的 Python 语法牛客判题机不认。标签盖好以后重点不是重新做一遍而是针对每一类错因做一次专项训练。比如“边界条件出错”特别多就集中刷一些数据范围很小的题锻炼自己找边界的能力。5.2 沉淀一套自己的代码模板模考另一个作用是暴露你的“底层模板是否熟练”。代码模板不是死记硬背而是把高频考点的基础结构先固化成肌肉记忆。我自己的模板库里有这么几块输入输出模板sys.stdin.readline二叉树先序/中序/后序遍历模板DFS/BFS 的网格与图模板一维 DP 的完全背包/0/1背包模板区间贪心排序模板单调栈模板有了这些模板正式笔试里第一眼看到题目类型就能快速搭建起代码骨架把更多时间留给真正的思考。5.3 后续刷题规划建议如果你的目标是一个月后参加秋招或实习笔试不建议漫无目的地在题库里乱刷。可以按阶段推进第一周数组、字符串、模拟、排序、二分查找。第二周链表、栈、队列、哈希表。第三周树、DFS/BFS、图。第四周动态规划、贪心、回溯算法。每周结束时把牛客周赛或者模拟题做一遍作为检测。不要贪多一天吃透两三道有价值的题比一天刷十道但留下印象的题更有用。我自己的体会是牛客模考五模这套题集难度不算变态但每一道都踩在正式笔试的高频点上。特别是第四题最少硬币当时我完全没有 DP 意识用 DFS 硬搜最后 TLE。后来把完全背包的内外层顺序彻底弄懂之后这种小优化成了长在脑子里的东西。最后再分享一个我在线上笔试里常用的土办法所有提交前在本地把题目里给的那个输入示例跑一遍再自己造一个最小输入比如只有一个元素、金额是 0、网格只有一行三列把这些边界值都跑通心里的底就足多了。