牛客模考三模编程题解析：校招笔试高频算法与Python实现

2017年牛客模考三模的编程题集合到今天再看依然是一套很典型的校招笔试训练题。那会儿我还在忙着刷题找工作牛客模考每次都会卡着时间做一遍三模这套题的难度曲线我记得很清楚前两道基本是送分题最后一道能拉开差距。最近用 Python 把它们重新做了一遍顺便把思路和踩坑整理出来希望对准备技术笔试的同学有帮助。这套题适合两类人看一类是正在备战校招、想在笔试前找实战感觉的同学另一类是已经工作一段时间想重新捡起算法基本功的开发者。读完之后你至少能收获三样东西常见题型的识别方法、经典算法的模板写法以及一套在线笔试环境下排查问题的思路。1. 从三模看校招笔试这套题到底想考什么1.1 模考定位与题目梯度设计牛客的模考并不是单纯给几道题让你刷它是在模拟真实在线笔试环境有限的时间、看不到实时提交反馈、代码要自己本地验证之后粘贴上去。2017年的这场三模编程题集合按难度递进基本是“一道热身的字符串题 一道数据结构题 一道综合算法题”的配置。这种设计很老练它想让笔试成绩有区分度同时也给不同水平的选手稳定的得分机会。基础题考验的是“能不能顺畅地写代码”也就是基本功综合题考验的是“在时间压力下能不能把问题抽象成算法模型”。所以你会发现这套题不是考冷门技巧而是反复在考同一批高频考点字符串处理、栈和队列、动态规划、搜索。这其实给后来人一个很明显的信号校招笔试不追求偏题怪题核心是把经典问题的解法练到肌肉记忆。1.2 题目背后的四项核心能力我做完这三道题之后复盘发现它们考察的能力可以拆成四层。第一层是读题抽象能力能不能把一段描述转成明确的输入输出和数据模型第二层是算法设计能力根据数据范围选择合适的算法而不是看到“最短路”就直接写 Floyd第三层是实现与调试能力能不能把思路落成边界正确的代码第四层是复杂度意识会不会预估最坏情况下的运行时间。以第三层为例很多人在本地测对了一提交就 Runtime Error原因往往是数组越界或空输入没处理。2017年的题集里就有一个字符串题输入行可能包含多个空格用 input().split() 和不处理空串的方法结果完全不一样。这就是典型的基础不牢。所以这套题虽然年代早了点但考点一点都不过时。2. 核心考点拆解四个高频题型套路2.1 字符串处理绝不只是“遍历一遍”字符串题看起来简单但笔试里它是翻车重灾区。2017年三模里有一道单词反转的题目要求保持单词顺序把每个单词内部反转。很多人第一反应是先用 split() 按空格切分再逐个反转最后 join。思路没问题但如果题目要求保留多余空格事情就变得有点麻烦。我建议这类题一定要先确认两件事一是输入是否可能包含多余空格、换行符、制表符二是输出要求是否严格匹配分隔符。如果允许用高级语言特性Python 的切片很容易完成单次反转但如果要求写 C 或 Java双指针是更通用的方案。刷题的时候不要只满足于“能过样例”要想想如果不让你用 split你还能不能写出来。2.2 栈与队列括号匹配和单调栈的两种用法括号匹配是栈的经典应用思路很简单遇到左括号入栈遇到右括号时看栈顶是否匹配匹配就弹出不匹配就返回错误。但真正写代码时很多人会忘记处理“栈为空但遇到右括号”的情况或者遍历结束后栈里还有剩余左括号。2017年的题目里括号相关的题不光要求判断合法性还要求计算最长合法括号子串的长度。这就要用到栈的另一个技巧栈底保存“最后一个未匹配的右括号位置”。一旦遇到合法括号对当前位置减去栈底位置就是当前合法子串长度。这个思路不是原始思路但非常实用很多后续题目都换了件马甲继续考。如果你对栈不熟建议把“括号匹配 最长匹配”这两个模板都背下来。2.3 动态规划从二维 DP 到空间压缩三模的压轴题里动态规划占了不少分量典型如最小编辑距离。这类题的套路很固定定义 dp[i][j] 为第一个字符串前 i 个字符变成第二个字符串前 j 个字符的最小操作次数然后按“插入、删除、替换”三种操作写状态转移。初学 DP 的同学容易盯着递推公式看半天却忽略了初始化的正确性。编辑距离里dp[0][j] 应该等于 j因为空串变成 j 个字符只能插入 j 次dp[i][0] 应该等于 i同理。这个要是写错整个表都废了。等二维表写顺了再考虑空间压缩其实每一行只依赖上一行所以可以用两个一维数组滚动更新把空间降到 O(n)。校招笔试虽然一般不管空间但能写出空间优化版本在面试里是加分项。2.4 搜索BFS 与 DFS 怎么选搜索题是综合题的常客。网格类题目里求最短路径优先用 BFS因为 BFS 第一次到达终点时的步数一定是最短的而判断是否存在路径、求解连通区域数量DFS 或 BFS 都可以。2017年的题目中有一道迷宫题数据范围不大DFS 也能过但从稳健角度我更喜欢 BFS。BFS 的模板非常固定队列 visited 数组入队时标记出队时扩展四个方向。这里有一个特别容易被忽略的点如果出队时才标记 visited同一个节点可能被多个邻居重复入队虽然结果可能正确但性能和内存上会有问题。正确的做法是“入队即标记”在做提前就把它锁死避免重复。3. 实战模拟代表题的完整题解这套题里有几道代表性能拉满的题目我把题干大意和完整解题过程复述一下代码用 Python 写尽量做到可以直接跑。3.1 题解一单词反转简单题面输入一个英文句子单词之间用空格分隔可能包含连续空格。输出每个单词内部字符都反转后的句子单词顺序保持不变。这道题考察字符串切割与拼接。最简单的做法是 split 后逐词反转s input().strip() words s.split() res [w[::-1] for w in words] print( .join(res))如果你不想用 split也可以双指针从后往前找单词边界。需要注意的地方有两个第一strip() 要去掉首尾多余空格否则空字符串可能混进结果第二如果题目要求保留连续空格上面的代码会丢失格式。这种题不能想当然一定要根据题目输出要求决定是否保留。3.2 题解二最长合法括号子串中等题面给定一个只包含 ( 和 ) 的字符串求最长连续合法括号子串的长度。栈的经典扩展。常规做法是维护一个栈遇到 ( 入栈遇到 ) 出栈但单纯这样只能判断合法求不了最长长度。需要把栈底留作一个“哨兵”位置def longest_valid_parentheses(s): stack [-1] max_len 0 for i, ch in enumerate(s): if ch (: stack.append(i) else: stack.pop() if not stack: stack.append(i) else: max_len max(max_len, i - stack[-1]) return max_len解释一下遍历到右括号时先弹出一个左括号索引如果弹完之后栈空了说明这之前的括号无法配对就把当前位置压入栈底作为新的哨兵如果栈不为空用当前位置减去栈顶元素得到以当前右括号结尾的合法子串长度。实测下来这个方法非常稳定代码短且不容易漏边界。3.3 题解三最长无重复字符子串中等题面给定一个字符串找出其中不含有重复字符的最长子串长度。这是滑动窗口的经典题。维护一个窗口用哈希表记录字符最新出现的位置。遍历字符串时窗口右端不断右移如果下一个字符之前出现过就把窗口左端移动到上次出现位置的下一个位置。def length_of_longest_substring(s): char_index {} left 0 max_len 0 for right, ch in enumerate(s): if ch in char_index and char_index[ch] left: left char_index[ch] 1 char_index[ch] right max_len max(max_len, right - left 1) return max_len这里最关键的是判断条件char_index[ch] left。如果不加这个条件可能把左边界往左拉。举个例子字符串 abba当遍历到最后一个 a 时虽然 a 之前出现过但它在窗口外所以不应该移动 left。这个坑我在笔试里踩过一次印象特别深。3.4 题解四最小编辑距离较难题面有两个字符串 word1 和 word2允许插入、删除、替换一个字符计算将 word1 变成 word2 所需的最小操作次数。经典 DP。定义 dp[i][j] 表示 word1 前 i 个字符转换到 word2 前 j 个字符的最小步数。初始化首行首列后双循环遍历def min_distance(word1, word2): m, n len(word1), len(word2) dp [[0] * (n 1) for _ in range(m 1)] for i in range(m 1): dp[i][0] i for j in range(n 1): dp[0][j] j for i in range(1, m 1): for j in range(1, n 1): if word1[i - 1] word2[j - 1]: dp[i][j] dp[i - 1][j - 1] else: dp[i][j] min(dp[i - 1][j] 1, dp[i][j - 1] 1, dp[i - 1][j - 1] 1) return dp[m][n]注意状态转移的语义dp[i-1][j] 1表示删除 word1 的第 i 个字符dp[i][j-1] 1表示插入一个字符到 word2dp[i-1][j-1] 1表示替换。笔试时建议先用二维表把思路理顺再视情况优化一维空间。如果直接一维写错了不好排查。3.5 题解五迷宫最短路综合题面给定一个 n 行 m 列的网格0 表示可走1 表示障碍从 (0,0) 出发每次可以上下左右移动一步求到达 (n-1, m-1) 的最少步数如果不可达返回 -1。BFS 模板题from collections import deque def min_steps(grid): if not grid or grid[0][0] 1: return -1 n, m len(grid), len(grid[0]) visited [[False] * m for _ in range(n)] q deque() q.append((0, 0, 0)) visited[0][0] True dirs [(1, 0), (-1, 0), (0, 1), (0, -1)] while q: x, y, step q.popleft() if x n - 1 and y m - 1: return step for dx, dy in dirs: nx, ny x dx, y dy if 0 nx n and 0 ny m and not visited[nx][ny] and grid[nx][ny] 0: visited[nx][ny] True q.append((nx, ny, step 1)) return -1这段代码有三个关键点起点可能被障碍堵住方向数组要能覆盖上下左右visited 标记一定要在入队时做。如果你的代码把visited[nx][ny] True放在了 pop 之后数据一大就会队列爆炸。这也是在线笔试中很常见的性能陷阱。4. 答题过程中的常见问题与排查技巧实录4.1 我踩过的五个坑常见问题现象原因解决方案输入读取错误数据只有一半或输出完全不同用 input() 读一行但输入实际有多行用 sys.stdin.read().split() 统一读取数组越界报 IndexError访问网格邻居时没判断边界先判断 0xn再访问DP 初始化错误答案偏大或偏小dp[0][j]、dp[i][0] 没赋初值初始化首行首列为递增序列栈空未处理括号匹配误判见右括号直接 pop栈已空先判断栈是否为空超时无优化大样例卡死穷举所有子串O(n^2)改成滑动窗口 O(n)这些坑看着简单但每一条都对应着真实的失分现场。尤其是输入读取牛客的测试数据往往比本地练习更复杂不一次性读入可能会因为换行符导致数据错位。4.2 在线笔试环境下如何自测在线笔试不像本地 IDE你可以一边调试一边看变量。很多测评系统只给你一个“答案错误”的反馈所以自测策略很重要。我个人的做法是三步走。第一步跑一遍题目自带的示例确保基本流程正确。第二步构造边界数据空字符串、单字符、全障碍网格、重复字符、连续空格等这一轮能过滤掉大部分隐藏错误。第三步估算数据规模如果最高复杂度可能达到 10^8 级别就要考虑换算法或剪枝。还有一个小技巧在本地准备一个随机测试脚本针对输入输出可以生成随机数据然后和暴力解法对比。比如编辑距离题可以写一个 BFS 的暴力版做对照随机小数据比对结果虽然笔试现场没时间这样做但在家刷题时非常好用。5. 基于这套题延伸的备考建议5.1 刷题策略从“做对”到“做快”刷题阶段很多人只追求把题做出来但校招笔试真正拉开差距的是“做快”和“做稳”。一道题如果你需要 50 分钟才能写出来那考试时基本等于没做。我建议按知识点分类刷题字符串一组、栈和队列一组、DP 一组、搜索一组每个知识点刷到能不看模板默写核心代码。每道题做完之后都花 10 分钟复盘这题考的是哪个模板我当时卡在哪一步以后遇到相似题第一反应应该是什么把这些内容记到自己的模板库里比毫无目的地刷两百道题更有效。刷题数量当然重要但数量必须建立在每次都有沉淀的基础上。5.2 Python 写算法题的三个实用技巧如果你打算用 Python 参加笔试有三个技巧非常实用我最近在做这套题时也一直在用。第一个是collections.deque。BFS 时不要用 list 模拟队列因为 pop(0) 是 O(n) 操作数据量一大就卡死deque 的 popleft() 是 O(1)。第二个是快速读取输入。多行输入时推荐import sys data sys.stdin.read().split()这样一次读入所有内容再按下标取数既快又不容易漏行。很多遇到“本地能跑在线超时”的同学问题往往就出在输入输出上。第三个是functools.lru_cache。解决递归型 DP 时加一行装饰器就能自动记忆化比如跳台阶、斐波那契、递归子序列问题都可以用。不过要注意如果递归深度很大建议还是改成显式 DP避免栈溢出。5.3 后续扩展方向这套题里涉及的题型都有很多扩展。字符串题可以延伸到 KMP 和字典树括号题可以继续思考如何生成所有合法括号组合最长不重复子串再往前走就是滑动窗口做最小覆盖子串编辑距离可以扩展到编辑代价不同的变种迷宫 BFS 可以推广到多源 BFS、带权最短路。如果你把这套题里的每个模板都吃透再去刷其他真题会发现很多题都是“旧瓶装新酒”。比如看到最长合法括号你可以联想到栈看到迷宫你马上想到 BFS 模板看到两个字符串求最小代价你意识到要设计 DP 状态。这种条件反射才是刷题训练最值钱的结果。我个人在实际操作中的体会是2017年的题目放在今天依然有练习价值不是因为题目有多难而是它把校招笔试最常考的题型都浓缩进去了。重新做一遍的时候我仍然会犯一些低级错误比如栈空判断漏掉、滑动窗口边界写错。所以别嫌题老基础模板的熟练度永远是笔试提分最快的一条路。