2017年秋天牛客网办过一场模拟校招笔试我记得是第四场模考。那是我第一次在限时环境下做在线编程题没有本地IDE、没有编译调试提交之后只能等一个红红或绿绿的判题结果。四道编程题最后AC了两道半倒数第二道BFS差一个边界条件最后一道DP直接超时。说实话那场考试让我第一次意识到“看懂题”和“写对题”之间隔着一条很大的沟。后来我专门找时间把这套卷子的题重刷了一遍把每道题的思路、代码和踩过的坑都记录了下来。这篇博文就是那次复盘的结果我会把这套卷里最有代表性的四道题抽出来从出题逻辑、解法思路、完整代码到坑点一步步过一遍。如果你是准备校招笔试的在校生或者刚开始刷牛客编程题、想系统补一补算法基础的新手这篇内容应该能帮你少走不少弯路。1. 那年的模考卷题型布局与出题逻辑1.1 从送分到压轴四道题的梯度设计那场模考的编程题一共四道整体难度是明显往上走的。第一道题基本是送分考的是字符串处理和集合去重只要会用标准库五分钟之内就能提交通过。第二道题是数学推导表面上是解三元一次方程真正要命的是边界条件——整数校验、负数校验、回代验证每一步都想不周全就可能全盘皆输。第三道题是迷宫最短路径典型的最短路径搜索考察图论基本功但迷宫的边界条件、障碍物判断、访问标记这些细节非常考验写代码的严谨程度。第四道题是0/1背包动态规划里最经典的入门模型考的是状态定义和滚动数组优化。这种出题顺序其实就是校招笔试的标准节奏先用一道简单的题稳住大多数人的心态再用数学推导题过滤掉粗心大意的人接着用搜索题考察基本功最后用DP题拉开区分度。牛客模考的出题团队明显是研究过真实校招笔试题型的这套卷子的难度曲线和当年互联网公司笔试的编程题基本一致。如果你第一次做这四道题按顺序做下来会有一个非常明显的感受前两题是热身的后两题才是真正决定你能不能通过笔试的部分。1.2 为什么2017年的题到现在仍有参考价值有人可能会问都2017年的题了现在刷还有意义吗我自己后来把过去几年的笔试题对比过结论是很明确的核心考点没有变过。去重统计、数学推导、最短路径、DP背包这四类题在现在的牛客模拟和真实校招笔试里依然高频出现。变的只是题面包装越来越花哨输入数据规模越来越大但底层的算法模型就是那几类。所以2017年的题反而更适合拿来练基本功——题目干净没有太多干扰信息可以专心把每个技术点吃透。如果你现在做这套卷能稳定四题全过说明你的基础已经比较扎实再去刷近两年的笔试题会顺手很多。2. 四道代表性题目的解题思路拆解2.1 第一题统计不同的食材种类集合应用先看第一题题目本身不复杂但很典型。小易要做一道菜需要准备若干食材现在给定若干行购物清单每行包含若干个英文单词单词之间用空格隔开统计清单里一共出现了多少种不同的食材。输入是多行文本读到文件末尾结束输出一个整数表示不同食材的种类数。样例输入是这样的apple banana banana orange apple样例输出是3这道题本质上就是字符串去重统计。最直接的做法是维护一个集合set每读入一个单词就插入集合最后输出集合的大小。为什么用set而不是数组因为食材名是字符串不是连续的数字不能直接用下标映射如果手动写哈希表当然也可以但C标准库里的set底层是红黑树插入和查询都是O(log n)对这个数据规模完全够用而且代码量少、不容易出错。如果你用的是Python直接用set容器一行insert最后len一下整个逻辑一样。这道题真正考察的点有两个。第一个是能不能想到用集合去重这属于数据结构的基本应用第二个是能不能正确处理“多行输入直到文件结束”这种输入格式。很多新手在本地测试时习惯用getline逐行读但题干说的是“每行包含若干个单词”如果直接用cin word自动按空白字符切分反而更省事还不用关心换行符在哪。这两点想清楚了这道题就是三分钟的事。2.2 第二题由算式反推三人的糖果数方程与回代第二题的题干是A、B、C三个小朋友手里有糖果若干已知四个关系式A - B aB - C bA B cB C d其中a、b、c、d是输入的四个整数请你求出A、B、C的值。如果不存在满足条件的整数解输出“No”。样例输入1 -2 3 4样例输出2 1 3这道题看到第一反应是解方程。由A - B a和A B c两式相加得2A a c相减得2B c - a由B - C b和B C d两式相加得2C d - b。算出A、B、C候选值之后还要再把回代入四个关系式验证一遍。为什么要验证因为输入的四元组不一定自洽。比如a1、b2、c3、d4时按公式算出来A2、B1、C1但B - C 1 - 1 0不等于b2所以这组输入没有合法解必须输出“No”。这道题是典型的“看起来简单错起来容易”的题。我见过很多人在算出A、B、C之后就直接输出了完全不检查奇偶性、不检查负数、不检查回代结果。如果题目要求“整数解”那(ac)必须能被2整除否则A不可能是整数如果题目隐含有“糖果数不能为负”的日常语义那负数的C也必须排除。在实际笔试中这类条件通常不会全写在题干里而是藏在“糖果”这两个字的日常理解里。做题时一定要把“值是整数”和“值合理”这两层都考虑到。2.3 第三题迷宫最短步数BFS最短路径这道题是一个N行M列的迷宫0表示可以走的路1表示障碍物。小易从左上角(0,0)出发每次只能向上、下、左、右四个方向移动一格不能走出边界也不能走到障碍物上请问到达右下角(N-1, M-1)最少需要多少步如果无法到达则输出-1。样例输入3 3 0 0 0 0 1 0 0 0 0样例输出4为什么这道题必须用BFS而不是DFSBFS按层扩展每层代表“走一步能到达的所有位置”所以第一次扩展到终点时步数一定是最少的。DFS虽然也能搜到终点但它的特点是一条路走到黑找到终点时的路径不一定最短如果要找最短路径还得遍历所有可能路径效率差很多。对这种等权图上的最短路径问题BFS是自然而然的解法。实现BFS有几个关键细节。第一要有一个dist二维数组记录每个位置的最短步数同时兼作访问标记初始化为-1表示未访问第二用队列存当前位置每次从队首弹出一个坐标向四个方向尝试扩展第三扩展时先判断是否越界再判断是否是障碍物最后判断是否已经访问过第四起点是0终点如果被扩展到就输出对应的步数。这里面最容易漏的是起点和终点本身是障碍物的情况——起点是1那直接没法走终点是1也到不了如果题目的测试数据包含了这种极端情况没做判断就会被卡掉一半的分。2.4 第四题预算内的最大喜爱度0/1背包问题第四题的题干是小易去超市采购手上有M元预算超市里有N件商品每件商品有价格p[i]和喜爱度v[i]每种商品最多买一件问在预算不超过M元的前提下能获得的最大喜爱度总和是多少。输入第一行是两个整数N和M接下来N行每行两个整数p[i]和v[i]输出一个整数表示最大喜爱度。样例输入4 5 2 3 1 2 3 4 2 2样例输出7这个样例里选价格2喜爱3、价格1喜爱2、价格2喜爱2三项总价格正好是5总喜爱度是7是所有组合里最大的。这道题就是一个标准0/1背包N件物品每件最多选一次总重量不能超过M求最大价值。0/1背包的状态转移方程是dp[j] max(dp[j], dp[j - p[i]] v[i])dp[j]表示容量为j的背包能装下的最大价值。对第i件商品要么不选保持dp[j]不变要么选在容量j里腾出p[i]的空间再加上当前商品的喜爱度。注意内层循环必须从M到p[i]倒序遍历原因和滚动数组的原理有关如果正序遍历一件商品会被重复使用多次那就变成完全背包了。这两种背包问题在笔试里都很常见倒序还是正序是区分它们的关键也是面试官最喜欢挖坑的地方。3. 完整实现与现场调试记录3.1 第一题代码实现输入读取的细节第一题完整代码用C写出来大概是这样#include iostream #include set #include string using namespace std; int main() { string word; setstring dict; while (cin word) { dict.insert(word); } cout dict.size() endl; return 0; }我当时在这道题上面踩过一个很低级的坑。第一版我是这么写的先getline读每一行然后手动split空格再逐个插入set。程序本地跑得好好的一提交到在线OJ就超时因为题目数据量比较大getline加手动split的方式效率不高而且处理回车符和多余空格很容易出错。后来改成直接用cin word标准输入流会自动按空白字符切分又简洁又高效。所以当你看到“以空格分隔的若干单词”这种输入描述时不要自己做字符串分割直接用cin / Python的split就好。如果你是Python选手这道题更简单words set() while True: try: line input() for word in line.split(): words.add(word) except EOFError: break print(len(words))当然Python也可以写成读取所有输入再统一处理不过这种逐行读的方式更贴近在线笔试场景不容易因为某一行格式问题全部崩溃。3.2 第二题代码实现整数校验的顺序很重要第二题的完整实现我放在这里#include iostream using namespace std; int main() { int a, b, c, d; while (cin a b c d) { int sumA a c; int sumB1 c - a; int sumC d - b; int sumB2 b d; if (sumA % 2 ! 0 || sumB1 % 2 ! 0 || sumC % 2 ! 0 || sumB2 % 2 ! 0) { cout No endl; continue; } int A sumA / 2; int B sumB1 / 2; int C sumC / 2; int B2 sumB2 / 2; if (A 0 || B 0 || C 0) { cout No endl; continue; } if (B ! B2 || A - B ! a || B - C ! b || A B ! c || B C ! d) { cout No endl; continue; } cout A B C endl; } return 0; }这段代码里有几个比较关键的点。第一是奇偶判断四个表达式只要有一个是奇数就说明对应的和不能被2整除直接No。第二是B的两个计算路径要一致一个由c - a得到一个由b d得到如果两个结果不一样说明四元组内部互相矛盾。第三是负数判断这一点容易被忽略因为“糖果数”的日常生活中不可能是负数但题目如果没有显式说明会有不少人踩这个坑。第四是回代验证用算出来的A、B、C重新计算A - B、B - C、A B、B C和输入的a、b、c、d比对。这一串检查要按顺序做先算后判这个顺序本身就是逻辑严谨性的体现。3.3 第三题代码实现BFS队列的细节处理第三题完整实现我用的C#include iostream #include vector #include queue using namespace std; int main() { int N, M; while (cin N M) { vectorvectorint maze(N, vectorint(M)); for (int i 0; i N; i) for (int j 0; j M; j) cin maze[i][j]; if (maze[0][0] 1 || maze[N - 1][M - 1] 1) { cout -1 endl; continue; } vectorvectorint dist(N, vectorint(M, -1)); queuepairint, int q; dist[0][0] 0; q.push({0, 0}); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx N || ny 0 || ny M) continue; if (maze[nx][ny] 1) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } cout dist[N - 1][M - 1] endl; } return 0; }BFS的框架是很固定的关键就是不要漏掉任何判断。我当年在这道题上栽过一次就是因为提前判断了起点和终点障碍物的特殊情况却在方向扩展时把越界判断和障碍物判断的顺序写反了——先判断障碍物再判断越界当某个方向坐标已经负数时访问maze[nx][ny]会下标越界导致运行时错误。正确的顺序一定是先判越界再判障碍。这个问题在本地测试时如果用例比较温和可能暴露不出来但换到OJ的边界数据就会直接崩掉。3.4 第四题代码实现滚动数组的循环顺序第四题完整C实现#include iostream #include vector #include algorithm using namespace std; int main() { int N, M; while (cin N M) { vectorint p(N); vectorint v(N); for (int i 0; i N; i) cin p[i] v[i]; vectorint dp(M 1, 0); for (int i 0; i N; i) { for (int j M; j p[i]; --j) { dp[j] max(dp[j], dp[j - p[i]] v[i]); } } cout dp[M] endl; } return 0; }为什么内层循环一定要倒序我当时学背包的时候一直没想通直到自己跑了一次正序遍历才彻底明白。正序遍历时dp[j]可能已经包含了第i件商品再更新dp[j p[i]]时就会把同一件商品用两次这是在允许同一件商品无限用的情况下的逻辑。0/1背包要求每件最多选一次所以必须倒序dp[j]更新时只会从dp[j - p[i]]取状态而j - p[i]一定小于j逆序操作时当前商品还没有被用过所以不会出现重复使用的问题。这个细节是0/1背包和完全背包的分水岭笔试题里经常把这两种模型混在题干里看到“每种商品最多买一件”就要条件反射写倒序。如果M特别大比如M 100000N 100这个O(N*M)的复杂度是能过的。但如果M到了10^7级别二维dp数组加一维滚动数组就直接内存溢出了这时候可以考虑把状态压缩成1维但复杂度还是下不来只能换思路比如按价格排序后用贪心或者搜索剪枝。不过在校招笔试的常规数据范围内标准0/1背包写法完全够用。下面补一个Python版的背包实现现在很多公司的在线笔试已经支持Python了while True: try: N, M map(int, input().split()) p [] v [] for _ in range(N): pi, vi map(int, input().split()) p.append(pi) v.append(vi) dp [0] * (M 1) for i in range(N): for j in range(M, p[i] - 1, -1): dp[j] max(dp[j], dp[j - p[i]] v[i]) print(dp[M]) except EOFError: breakPython写起来确实清爽但要注意在数据量大时Python的纯循环比C慢很多。如果你目标公司笔试用Python建议在牛客的练习模式里多提交几次观察一下自己写法和用PyPy提交的区别提前熟悉性能边界。4. 复盘过程中的常见问题与避坑清单4.1 那些年我在线笔试踩过的坑把四道题重刷一遍之后我整理出了一个很典型的“易错点清单”。第一道题的自定义分割是典型的画蛇添足直接用流式输入就可以我省略了手动切分反而又稳又快。第二道题最容易忘的是回代验证很多同学算完A、B、C直接输出如果遇到矛盾数据就会错。其实在真实笔试里这类“解出来还不算完必须再验证一遍”的陷阱特别多宁可多写几行代码也不要省掉验证逻辑。第三道题是典型的边界条件地狱。起点终点障碍判断、越界判断、障碍判断、访问标记判断四个判断环环相扣漏任何一个都可能出错。第四道题最坑的是题意理解题干里“每种商品最多买一件”这句话没注意的话容易写成完全背包正序遍历导致结果错误。很多人在笔试结束后复盘才发现自己写的代码逻辑其实不难难的是把题目的每个条件都转换成代码里的每一个if分支。4.2 边界条件与极端用例检查在线笔试最怕的不是算法不会而是代码在极端用例下崩溃。第四题我在重写时专门构造了一组极端数据4 0 2 3 1 2 3 4 2 2M0也就是说预算为0一件商品都买不起正确输出应该是0。如果dp数组初始化正确内层循环j从0开始就不会进入任何更新最后输出dp[0]0这个用例能直接验证循环边界是否正确。同理第三题可以构造N1、M1、maze[0][0]0的用例只有一个格子的迷宫起点就是终点正确输出0如果maze[0][0]1正确输出-1。这些极简用例在调试时特别有用千万别嫌简单跑一遍能瞬间定位很多问题。4.3 四道题常见错误速查表我把这四道题可能遇到的典型错误整理成了表格方便大家自查题目常见错误解决思路食材统计手动split字符串处理换行符出错直接用cin word按空白自动切分食材统计用数组存储单词无法快速去重使用set插入后直接输出size糖果方程算完A、B、C直接输出不验证回代四个关系式全部匹配才输出糖果方程忽略奇偶性和负数先判整除再判非负再验算迷宫最短路径越界判断和障碍判断顺序写反先判越界再判障碍再判访问状态迷宫最短路径不处理起点/终点是障碍在BFS前提前检查能直接输出-10/1背包内层循环正序物品被重复使用内层从M到p[i]倒序遍历0/1背包dp数组开小M1写错确认dp大小为M1循环从M开始这张表我后来在刷别家公司的笔试题时也经常拿出来看这些错误不是2017年才有现在依然很常见。5. 从模考到今天的观察5.1 哪些考点被保留哪些变了味重刷这套卷子再对比近两年的校招笔试题我的感觉是考点的集中度反而更高了。集合去重、字符串处理、BFS、DFS、二维DP、贪心、二分这些基础题依然是最常出现的题型。但题面确实变得越来越长场景包装越来越复杂有时候光读懂题就要花好几分钟反而把真正的算法核心藏在很深的描述里。这不是坏事也是一种筛选方式——能在大量干扰信息里快速识别模型的人实际开发中阅读理解需求的能力往往也更强。所以刷题的时候不要只看解法还要训练自己从题干里提炼模型的速度。另一个变化是语言选择。2017年那会儿大部分笔试默认写C或JavaPython虽然能用但偶尔因为性能被判超时。现在很多公司的在线笔试已经明确支持Python而且Python在写BFS、DFS、DP这类题时开发效率确实高很多。我眼下的建议是C打底把指针、数组、STL的常用容器用熟Python作为备选在题目数据量较小或时间紧张时用Python快速提交。这套2017年的题完全可以用两种语言各刷一遍对你理解算法本身没有坏处。5.2 给现在刷题的人三个建议第一刷题一定要模拟真实笔试环境。不要开IDE自动补全不要本地调试完了再粘贴直接在牛客的在线编辑器里写写完直接提交。你平时写代码舒适习惯了上了考场突然发现连编译错误都找不到那才是最难受的。第二建议做一个自己的错题本不用花哨就把每道题的错误原因、正确思路、对应代码贴在一起。这个习惯我坚持到现在面试前翻一翻比自己重新刷题效率高得多。第三不要盲目追求偏题难题。牛客上有很多大神分享题解看起来很有深度但对你笔试提分的帮助很小。你更需要的是把每一道模考题里的常规考点吃透做到看到“最大喜爱度”“最短步数”“种类数”就能立刻反应出对应算法模型。这套2017年牛客模考四模的编程题难度放到今天依然是很好的基础训练材料。我自己在重刷的时候最大的收获不是记住了某个题解而是把“验证边界、确认数据合理性、在草稿纸上演算”这几个习惯真正养成了。这几年再参加各种线上笔试和技术面试遇到的大部分题底子都还是当年这套卷子打下来的那套思维。最后再分享一个小技巧刷完一道题不要急着看题解先在评论区看看别人的提交记录特别是那些超时和越界的错误提交往往比正确题解更能暴露你对题目的理解漏洞。这套卷子我在牛客上翻了不少人的提交记录发现同一个坑能有一百种踩法。你能避开其中几种笔试通过率就已经领先很多人了。
校招笔试算法复盘：从集合去重到0/1背包的进阶之路
2017年秋天牛客网办过一场模拟校招笔试我记得是第四场模考。那是我第一次在限时环境下做在线编程题没有本地IDE、没有编译调试提交之后只能等一个红红或绿绿的判题结果。四道编程题最后AC了两道半倒数第二道BFS差一个边界条件最后一道DP直接超时。说实话那场考试让我第一次意识到“看懂题”和“写对题”之间隔着一条很大的沟。后来我专门找时间把这套卷子的题重刷了一遍把每道题的思路、代码和踩过的坑都记录了下来。这篇博文就是那次复盘的结果我会把这套卷里最有代表性的四道题抽出来从出题逻辑、解法思路、完整代码到坑点一步步过一遍。如果你是准备校招笔试的在校生或者刚开始刷牛客编程题、想系统补一补算法基础的新手这篇内容应该能帮你少走不少弯路。1. 那年的模考卷题型布局与出题逻辑1.1 从送分到压轴四道题的梯度设计那场模考的编程题一共四道整体难度是明显往上走的。第一道题基本是送分考的是字符串处理和集合去重只要会用标准库五分钟之内就能提交通过。第二道题是数学推导表面上是解三元一次方程真正要命的是边界条件——整数校验、负数校验、回代验证每一步都想不周全就可能全盘皆输。第三道题是迷宫最短路径典型的最短路径搜索考察图论基本功但迷宫的边界条件、障碍物判断、访问标记这些细节非常考验写代码的严谨程度。第四道题是0/1背包动态规划里最经典的入门模型考的是状态定义和滚动数组优化。这种出题顺序其实就是校招笔试的标准节奏先用一道简单的题稳住大多数人的心态再用数学推导题过滤掉粗心大意的人接着用搜索题考察基本功最后用DP题拉开区分度。牛客模考的出题团队明显是研究过真实校招笔试题型的这套卷子的难度曲线和当年互联网公司笔试的编程题基本一致。如果你第一次做这四道题按顺序做下来会有一个非常明显的感受前两题是热身的后两题才是真正决定你能不能通过笔试的部分。1.2 为什么2017年的题到现在仍有参考价值有人可能会问都2017年的题了现在刷还有意义吗我自己后来把过去几年的笔试题对比过结论是很明确的核心考点没有变过。去重统计、数学推导、最短路径、DP背包这四类题在现在的牛客模拟和真实校招笔试里依然高频出现。变的只是题面包装越来越花哨输入数据规模越来越大但底层的算法模型就是那几类。所以2017年的题反而更适合拿来练基本功——题目干净没有太多干扰信息可以专心把每个技术点吃透。如果你现在做这套卷能稳定四题全过说明你的基础已经比较扎实再去刷近两年的笔试题会顺手很多。2. 四道代表性题目的解题思路拆解2.1 第一题统计不同的食材种类集合应用先看第一题题目本身不复杂但很典型。小易要做一道菜需要准备若干食材现在给定若干行购物清单每行包含若干个英文单词单词之间用空格隔开统计清单里一共出现了多少种不同的食材。输入是多行文本读到文件末尾结束输出一个整数表示不同食材的种类数。样例输入是这样的apple banana banana orange apple样例输出是3这道题本质上就是字符串去重统计。最直接的做法是维护一个集合set每读入一个单词就插入集合最后输出集合的大小。为什么用set而不是数组因为食材名是字符串不是连续的数字不能直接用下标映射如果手动写哈希表当然也可以但C标准库里的set底层是红黑树插入和查询都是O(log n)对这个数据规模完全够用而且代码量少、不容易出错。如果你用的是Python直接用set容器一行insert最后len一下整个逻辑一样。这道题真正考察的点有两个。第一个是能不能想到用集合去重这属于数据结构的基本应用第二个是能不能正确处理“多行输入直到文件结束”这种输入格式。很多新手在本地测试时习惯用getline逐行读但题干说的是“每行包含若干个单词”如果直接用cin word自动按空白字符切分反而更省事还不用关心换行符在哪。这两点想清楚了这道题就是三分钟的事。2.2 第二题由算式反推三人的糖果数方程与回代第二题的题干是A、B、C三个小朋友手里有糖果若干已知四个关系式A - B aB - C bA B cB C d其中a、b、c、d是输入的四个整数请你求出A、B、C的值。如果不存在满足条件的整数解输出“No”。样例输入1 -2 3 4样例输出2 1 3这道题看到第一反应是解方程。由A - B a和A B c两式相加得2A a c相减得2B c - a由B - C b和B C d两式相加得2C d - b。算出A、B、C候选值之后还要再把回代入四个关系式验证一遍。为什么要验证因为输入的四元组不一定自洽。比如a1、b2、c3、d4时按公式算出来A2、B1、C1但B - C 1 - 1 0不等于b2所以这组输入没有合法解必须输出“No”。这道题是典型的“看起来简单错起来容易”的题。我见过很多人在算出A、B、C之后就直接输出了完全不检查奇偶性、不检查负数、不检查回代结果。如果题目要求“整数解”那(ac)必须能被2整除否则A不可能是整数如果题目隐含有“糖果数不能为负”的日常语义那负数的C也必须排除。在实际笔试中这类条件通常不会全写在题干里而是藏在“糖果”这两个字的日常理解里。做题时一定要把“值是整数”和“值合理”这两层都考虑到。2.3 第三题迷宫最短步数BFS最短路径这道题是一个N行M列的迷宫0表示可以走的路1表示障碍物。小易从左上角(0,0)出发每次只能向上、下、左、右四个方向移动一格不能走出边界也不能走到障碍物上请问到达右下角(N-1, M-1)最少需要多少步如果无法到达则输出-1。样例输入3 3 0 0 0 0 1 0 0 0 0样例输出4为什么这道题必须用BFS而不是DFSBFS按层扩展每层代表“走一步能到达的所有位置”所以第一次扩展到终点时步数一定是最少的。DFS虽然也能搜到终点但它的特点是一条路走到黑找到终点时的路径不一定最短如果要找最短路径还得遍历所有可能路径效率差很多。对这种等权图上的最短路径问题BFS是自然而然的解法。实现BFS有几个关键细节。第一要有一个dist二维数组记录每个位置的最短步数同时兼作访问标记初始化为-1表示未访问第二用队列存当前位置每次从队首弹出一个坐标向四个方向尝试扩展第三扩展时先判断是否越界再判断是否是障碍物最后判断是否已经访问过第四起点是0终点如果被扩展到就输出对应的步数。这里面最容易漏的是起点和终点本身是障碍物的情况——起点是1那直接没法走终点是1也到不了如果题目的测试数据包含了这种极端情况没做判断就会被卡掉一半的分。2.4 第四题预算内的最大喜爱度0/1背包问题第四题的题干是小易去超市采购手上有M元预算超市里有N件商品每件商品有价格p[i]和喜爱度v[i]每种商品最多买一件问在预算不超过M元的前提下能获得的最大喜爱度总和是多少。输入第一行是两个整数N和M接下来N行每行两个整数p[i]和v[i]输出一个整数表示最大喜爱度。样例输入4 5 2 3 1 2 3 4 2 2样例输出7这个样例里选价格2喜爱3、价格1喜爱2、价格2喜爱2三项总价格正好是5总喜爱度是7是所有组合里最大的。这道题就是一个标准0/1背包N件物品每件最多选一次总重量不能超过M求最大价值。0/1背包的状态转移方程是dp[j] max(dp[j], dp[j - p[i]] v[i])dp[j]表示容量为j的背包能装下的最大价值。对第i件商品要么不选保持dp[j]不变要么选在容量j里腾出p[i]的空间再加上当前商品的喜爱度。注意内层循环必须从M到p[i]倒序遍历原因和滚动数组的原理有关如果正序遍历一件商品会被重复使用多次那就变成完全背包了。这两种背包问题在笔试里都很常见倒序还是正序是区分它们的关键也是面试官最喜欢挖坑的地方。3. 完整实现与现场调试记录3.1 第一题代码实现输入读取的细节第一题完整代码用C写出来大概是这样#include iostream #include set #include string using namespace std; int main() { string word; setstring dict; while (cin word) { dict.insert(word); } cout dict.size() endl; return 0; }我当时在这道题上面踩过一个很低级的坑。第一版我是这么写的先getline读每一行然后手动split空格再逐个插入set。程序本地跑得好好的一提交到在线OJ就超时因为题目数据量比较大getline加手动split的方式效率不高而且处理回车符和多余空格很容易出错。后来改成直接用cin word标准输入流会自动按空白字符切分又简洁又高效。所以当你看到“以空格分隔的若干单词”这种输入描述时不要自己做字符串分割直接用cin / Python的split就好。如果你是Python选手这道题更简单words set() while True: try: line input() for word in line.split(): words.add(word) except EOFError: break print(len(words))当然Python也可以写成读取所有输入再统一处理不过这种逐行读的方式更贴近在线笔试场景不容易因为某一行格式问题全部崩溃。3.2 第二题代码实现整数校验的顺序很重要第二题的完整实现我放在这里#include iostream using namespace std; int main() { int a, b, c, d; while (cin a b c d) { int sumA a c; int sumB1 c - a; int sumC d - b; int sumB2 b d; if (sumA % 2 ! 0 || sumB1 % 2 ! 0 || sumC % 2 ! 0 || sumB2 % 2 ! 0) { cout No endl; continue; } int A sumA / 2; int B sumB1 / 2; int C sumC / 2; int B2 sumB2 / 2; if (A 0 || B 0 || C 0) { cout No endl; continue; } if (B ! B2 || A - B ! a || B - C ! b || A B ! c || B C ! d) { cout No endl; continue; } cout A B C endl; } return 0; }这段代码里有几个比较关键的点。第一是奇偶判断四个表达式只要有一个是奇数就说明对应的和不能被2整除直接No。第二是B的两个计算路径要一致一个由c - a得到一个由b d得到如果两个结果不一样说明四元组内部互相矛盾。第三是负数判断这一点容易被忽略因为“糖果数”的日常生活中不可能是负数但题目如果没有显式说明会有不少人踩这个坑。第四是回代验证用算出来的A、B、C重新计算A - B、B - C、A B、B C和输入的a、b、c、d比对。这一串检查要按顺序做先算后判这个顺序本身就是逻辑严谨性的体现。3.3 第三题代码实现BFS队列的细节处理第三题完整实现我用的C#include iostream #include vector #include queue using namespace std; int main() { int N, M; while (cin N M) { vectorvectorint maze(N, vectorint(M)); for (int i 0; i N; i) for (int j 0; j M; j) cin maze[i][j]; if (maze[0][0] 1 || maze[N - 1][M - 1] 1) { cout -1 endl; continue; } vectorvectorint dist(N, vectorint(M, -1)); queuepairint, int q; dist[0][0] 0; q.push({0, 0}); int dx[4] {-1, 1, 0, 0}; int dy[4] {0, 0, -1, 1}; while (!q.empty()) { int x q.front().first; int y q.front().second; q.pop(); for (int k 0; k 4; k) { int nx x dx[k]; int ny y dy[k]; if (nx 0 || nx N || ny 0 || ny M) continue; if (maze[nx][ny] 1) continue; if (dist[nx][ny] ! -1) continue; dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } cout dist[N - 1][M - 1] endl; } return 0; }BFS的框架是很固定的关键就是不要漏掉任何判断。我当年在这道题上栽过一次就是因为提前判断了起点和终点障碍物的特殊情况却在方向扩展时把越界判断和障碍物判断的顺序写反了——先判断障碍物再判断越界当某个方向坐标已经负数时访问maze[nx][ny]会下标越界导致运行时错误。正确的顺序一定是先判越界再判障碍。这个问题在本地测试时如果用例比较温和可能暴露不出来但换到OJ的边界数据就会直接崩掉。3.4 第四题代码实现滚动数组的循环顺序第四题完整C实现#include iostream #include vector #include algorithm using namespace std; int main() { int N, M; while (cin N M) { vectorint p(N); vectorint v(N); for (int i 0; i N; i) cin p[i] v[i]; vectorint dp(M 1, 0); for (int i 0; i N; i) { for (int j M; j p[i]; --j) { dp[j] max(dp[j], dp[j - p[i]] v[i]); } } cout dp[M] endl; } return 0; }为什么内层循环一定要倒序我当时学背包的时候一直没想通直到自己跑了一次正序遍历才彻底明白。正序遍历时dp[j]可能已经包含了第i件商品再更新dp[j p[i]]时就会把同一件商品用两次这是在允许同一件商品无限用的情况下的逻辑。0/1背包要求每件最多选一次所以必须倒序dp[j]更新时只会从dp[j - p[i]]取状态而j - p[i]一定小于j逆序操作时当前商品还没有被用过所以不会出现重复使用的问题。这个细节是0/1背包和完全背包的分水岭笔试题里经常把这两种模型混在题干里看到“每种商品最多买一件”就要条件反射写倒序。如果M特别大比如M 100000N 100这个O(N*M)的复杂度是能过的。但如果M到了10^7级别二维dp数组加一维滚动数组就直接内存溢出了这时候可以考虑把状态压缩成1维但复杂度还是下不来只能换思路比如按价格排序后用贪心或者搜索剪枝。不过在校招笔试的常规数据范围内标准0/1背包写法完全够用。下面补一个Python版的背包实现现在很多公司的在线笔试已经支持Python了while True: try: N, M map(int, input().split()) p [] v [] for _ in range(N): pi, vi map(int, input().split()) p.append(pi) v.append(vi) dp [0] * (M 1) for i in range(N): for j in range(M, p[i] - 1, -1): dp[j] max(dp[j], dp[j - p[i]] v[i]) print(dp[M]) except EOFError: breakPython写起来确实清爽但要注意在数据量大时Python的纯循环比C慢很多。如果你目标公司笔试用Python建议在牛客的练习模式里多提交几次观察一下自己写法和用PyPy提交的区别提前熟悉性能边界。4. 复盘过程中的常见问题与避坑清单4.1 那些年我在线笔试踩过的坑把四道题重刷一遍之后我整理出了一个很典型的“易错点清单”。第一道题的自定义分割是典型的画蛇添足直接用流式输入就可以我省略了手动切分反而又稳又快。第二道题最容易忘的是回代验证很多同学算完A、B、C直接输出如果遇到矛盾数据就会错。其实在真实笔试里这类“解出来还不算完必须再验证一遍”的陷阱特别多宁可多写几行代码也不要省掉验证逻辑。第三道题是典型的边界条件地狱。起点终点障碍判断、越界判断、障碍判断、访问标记判断四个判断环环相扣漏任何一个都可能出错。第四道题最坑的是题意理解题干里“每种商品最多买一件”这句话没注意的话容易写成完全背包正序遍历导致结果错误。很多人在笔试结束后复盘才发现自己写的代码逻辑其实不难难的是把题目的每个条件都转换成代码里的每一个if分支。4.2 边界条件与极端用例检查在线笔试最怕的不是算法不会而是代码在极端用例下崩溃。第四题我在重写时专门构造了一组极端数据4 0 2 3 1 2 3 4 2 2M0也就是说预算为0一件商品都买不起正确输出应该是0。如果dp数组初始化正确内层循环j从0开始就不会进入任何更新最后输出dp[0]0这个用例能直接验证循环边界是否正确。同理第三题可以构造N1、M1、maze[0][0]0的用例只有一个格子的迷宫起点就是终点正确输出0如果maze[0][0]1正确输出-1。这些极简用例在调试时特别有用千万别嫌简单跑一遍能瞬间定位很多问题。4.3 四道题常见错误速查表我把这四道题可能遇到的典型错误整理成了表格方便大家自查题目常见错误解决思路食材统计手动split字符串处理换行符出错直接用cin word按空白自动切分食材统计用数组存储单词无法快速去重使用set插入后直接输出size糖果方程算完A、B、C直接输出不验证回代四个关系式全部匹配才输出糖果方程忽略奇偶性和负数先判整除再判非负再验算迷宫最短路径越界判断和障碍判断顺序写反先判越界再判障碍再判访问状态迷宫最短路径不处理起点/终点是障碍在BFS前提前检查能直接输出-10/1背包内层循环正序物品被重复使用内层从M到p[i]倒序遍历0/1背包dp数组开小M1写错确认dp大小为M1循环从M开始这张表我后来在刷别家公司的笔试题时也经常拿出来看这些错误不是2017年才有现在依然很常见。5. 从模考到今天的观察5.1 哪些考点被保留哪些变了味重刷这套卷子再对比近两年的校招笔试题我的感觉是考点的集中度反而更高了。集合去重、字符串处理、BFS、DFS、二维DP、贪心、二分这些基础题依然是最常出现的题型。但题面确实变得越来越长场景包装越来越复杂有时候光读懂题就要花好几分钟反而把真正的算法核心藏在很深的描述里。这不是坏事也是一种筛选方式——能在大量干扰信息里快速识别模型的人实际开发中阅读理解需求的能力往往也更强。所以刷题的时候不要只看解法还要训练自己从题干里提炼模型的速度。另一个变化是语言选择。2017年那会儿大部分笔试默认写C或JavaPython虽然能用但偶尔因为性能被判超时。现在很多公司的在线笔试已经明确支持Python而且Python在写BFS、DFS、DP这类题时开发效率确实高很多。我眼下的建议是C打底把指针、数组、STL的常用容器用熟Python作为备选在题目数据量较小或时间紧张时用Python快速提交。这套2017年的题完全可以用两种语言各刷一遍对你理解算法本身没有坏处。5.2 给现在刷题的人三个建议第一刷题一定要模拟真实笔试环境。不要开IDE自动补全不要本地调试完了再粘贴直接在牛客的在线编辑器里写写完直接提交。你平时写代码舒适习惯了上了考场突然发现连编译错误都找不到那才是最难受的。第二建议做一个自己的错题本不用花哨就把每道题的错误原因、正确思路、对应代码贴在一起。这个习惯我坚持到现在面试前翻一翻比自己重新刷题效率高得多。第三不要盲目追求偏题难题。牛客上有很多大神分享题解看起来很有深度但对你笔试提分的帮助很小。你更需要的是把每一道模考题里的常规考点吃透做到看到“最大喜爱度”“最短步数”“种类数”就能立刻反应出对应算法模型。这套2017年牛客模考四模的编程题难度放到今天依然是很好的基础训练材料。我自己在重刷的时候最大的收获不是记住了某个题解而是把“验证边界、确认数据合理性、在草稿纸上演算”这几个习惯真正养成了。这几年再参加各种线上笔试和技术面试遇到的大部分题底子都还是当年这套卷子打下来的那套思维。最后再分享一个小技巧刷完一道题不要急着看题解先在评论区看看别人的提交记录特别是那些超时和越界的错误提交往往比正确题解更能暴露你对题目的理解漏洞。这套卷子我在牛客上翻了不少人的提交记录发现同一个坑能有一百种踩法。你能避开其中几种笔试通过率就已经领先很多人了。
