打开在线笔试系统的那一瞬间心跳往往会快半拍。120分钟、4道编程题、满屏的输入输出样例右上角倒计时从一开始就在走。大多数人的第一反应是急着看第一题先写一个能过的版本再说。但经历过几次笔试之后你会明白真正决定成绩的往往不是你会不会写代码而是你能否在压力下快速判断每道题的类型、估计出复杂度然后用最稳的方式拿到尽可能多的分。这篇内容围绕猿辅导2023校园招聘笔试算法二这套试卷说清楚我当时从读题到提交的完整思考过程包括每道题对应的算法选型、代码实现和几个让我差点翻车的细节。如果你是准备校招算法的同学这套试卷的题型分布和考察重点非常有参考价值如果你只是想巩固算法基础里面的差分数组、拓扑排序和KMP例题也足够你练手。1. 笔试全貌考试安排与分值策略1.1 考什么、怎么考猿辅导的笔试是在牛客网这类在线评测系统上进行的核心代码模式为主一般不会让候选人从头处理文件读写而是像LeetCode那样给你一个函数签名你往里面填逻辑就行。这套算法二整体是4道编程题120分钟难度大致呈阶梯状上升。第一题是送分题通常是贪心或者简单排序给的是20分左右第二题和第三题是中等题常见考点是前缀和/差分、拓扑排序这类需要一点数据结构和算法基础的题型各占25分左右最后一题是压轴题涉及字符串匹配或者更复杂的模型分值在30分上下。这样的分值分布意味着如果你只AC了前两题就已经能超过一部分候选人如果能稳定拿下前三题就已经是相当有竞争力的成绩。1.2 时间分配把这120分钟花在哪我的习惯是前5分钟不写代码先把4道题全部扫一遍。别小看这个过程它有两个直接好处一是能让你对整套题的难度分布有个整体判断避免在最难的题上死磕到时间耗尽二是能让你提前发现哪道题是你最熟悉的模型比如看到先修课程这四个字脑子里应该立刻冒出拓扑排序看到区间选最多就应该想到贪心。具体的时间安排建议是这样第一题控制在20分钟以内如果10分钟还没思路就先跳过第二题和第三题各留30到35分钟其中至少留5分钟来跑边界用例最后一题只给自己25到30分钟如果完全没思路优先写暴力版本保底而不是空在那儿。剩余的时间全部用来复查复查的时候重点看数组下标有没有越界、int有没有溢出、有没有可能死循环。笔试的残酷之处在于一道题从60分改成100分往往靠的不是灵光一现而是这些不起眼的细节。2. 四道核心题型的完整拆解从读题到AC2.1 T1 区间调度验证贪心直觉的一道送分题原题的描述通常是这样的给定n个区间[li, ri]每个区间表示一个活动的开始和结束时间要求选出尽可能多的区间使它们两两不重叠端点重合不算重叠输出最多能选几个。这道题很多人一上来会想到动态规划因为最多选择这些词天然带有DP的暗示。但实际上这是一个经典的贪心模型核心结论只有一句话按照右端点从小到大排序每次选择结束时间最早且与上一个已选区间不冲突的区间。为什么按右端点排序是对的可以这样想对于当前时间点结束越早的区间给后面留下的时间就越多。如果我们选了A而不是B而A的右端点不晚于B的右端点那么A至少不会比B更差。这是一个贪心选择性质的证明思路。如果按左端点排序你需要额外加很多判断条件而且很容易构造出反例比如[1,10], [2,3], [4,5], [6,7]按左端点排序反而会先选[1,10]导致只能选一个。C的参考实现也很短#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int segs(n); for (int i 0; i n; i) { cin segs[i].second segs[i].first; // 把右端点放前面方便排序 } sort(segs.begin(), segs.end()); int ans 0, lastEnd INT_MIN; for (auto [r, l] : segs) { if (l lastEnd) { ans; lastEnd r; } } cout ans endl; return 0; }这里有个细节在线笔试里如果你用的是vectorpairint,intpair默认先比较first再比较second所以把右端点存在first、左端点存在second里排序后天然就是按右端点升序、右端点相同时按左端点升序省去了自定义比较函数。不过你要确认题目的区间定义有的题允许端点重合有的不允许这直接决定还是。2.2 T2 航班预订统计差分数组把暴力O(n*m)降到O(nm)第二题考察的是一个很实用的小技巧——差分数组。题目大概是这样的有n个航班编号从1到n现在有m条预订记录每条记录包含(l, r, k)表示从第l个航班到第r个航班每个航班都预订了k个座位。要求最后输出每个航班的总预订数。暴力的思路很简单对每条记录循环从l到r累加k时间复杂度是O(n*m)。当n和m都到10的5次方甚至10的6次方量级时这个复杂度直接爆炸只能拿部分分。差分数组的思路是我们不需要真的在每个航班上都加一遍k只需要记录从某个位置开始增加k以及到某个位置之后恢复原状这两个变化点。具体来说用一个长度为n2的数组diff对于每条记录执行diff[l] k; diff[r1] - k;最后对diff数组求前缀和得到的结果就是每个航班的总预订数。用一个生活化的类比来理解想象你在记录一条马路上每个路段的车辆增加量。与其每来一批车就把整段路的计数都加一遍不如只在这段路的起点竖一块多了k辆车的牌子在终点后竖一块少了k辆车的牌子。最后你从头走一遍边走边累计牌子上的数就能得到每个位置的真实车流量。参考实现#include bits/stdc.h using namespace std; vectorint corpFlightBookings(vectorvectorint bookings, int n) { vectorint diff(n 2, 0); for (auto b : bookings) { int l b[0], r b[1], k b[2]; diff[l] k; diff[r 1] - k; } vectorint ans(n); int cur 0; for (int i 0; i n; i) { cur diff[i 1]; // 因为航班编号从1开始 ans[i] cur; } return ans; }这个题最容易踩的坑是下标。如果航班编号从1开始而你要返回一个长度为n的数组下标0到n-1中间的映射关系很容易乱。我的建议是在代码里明确标注注释航班编号i对应数组下标i-1并且在提交前用一个n3、实际编号为1到3的小样例走一遍确保diff[r1]不会越界。差分数组长度开成n2而不是n1就是为了让rn时r1仍然有一个安全位置。2.3 T3 课程表拓扑排序的Kahn解法与环检测第三题是经典的课程表问题一共有n门课程编号0到n-1给定若干先修关系[ai, bi]表示学课程bi之前必须先学课程ai要求输出一个合法的学习顺序如果不存在存在环依赖则输出空数组。这道题几乎就是为拓扑排序准备的。拓扑排序的思路是先统计每个节点的入度有多少门课是它的先修课把入度为0的节点先放进队列然后依次取出每取一个节点就把它的所有后继节点的入度减1如果某个后继节点入度变为0就把它也加入队列。最后如果取出的节点数等于总节点数说明拓扑序存在否则说明图里有环。在算法的选择上我建议用Kahn卡恩算法而不是DFS染色法。原因有两个第一Kahn算法天然输出一个合法的拓扑序而DFS的递归写法在输出顺序上需要额外处理很容易把顺序搞反第二Kahn算法在判环时更直观——队列为空但已经取出的节点数不等于总节点数就是有环。这道题对应牛客和LeetCode上的207和210搜一下就能找到原题。参考实现Python更容易读from collections import deque def findOrder(numCourses, prerequisites): indeg [0] * numCourses graph [[] for _ in range(numCourses)] for a, b in prerequisites: graph[b].append(a) indeg[a] 1 q deque([i for i in range(numCourses) if indeg[i] 0]) res [] while q: cur q.popleft() res.append(cur) for nxt in graph[cur]: indeg[nxt] - 1 if indeg[nxt] 0: q.append(nxt) return res if len(res) numCourses else []两个细节值得强调。一是先修关系的方向题目说[ai, bi]表示学bi之前必须先学ai这意味着存在一条从ai指向bi的边所以是graph[ai].append(bi)还是graph[bi].append(ai)要仔细看题。我笔试时就因为方向反了导致连样例都过不了白白耗了十分钟。二是图中有多条边重复出现时入度要按实际边数累加不要因为两个节点之间已经有一条边就跳过否则结果会不一样。2.4 T4 字符串循环节KMP的next数组完全不浪费最后一题是字符串题给定一个非空字符串s判断它是否可以由它的一个子串重复多次构成。比如abab可以由ab重复两次构成abcabcabc可以由abc重复三次构成但ababa不行。很多人的第一反应是用库函数比如把s加上s再找子串或者暴力枚举所有可能的重复长度。但面试官和评测系统显然期待你用KMP来解决因为这道题的背后是KMP算法中next数组的一个优美性质。KMP的next数组前缀函数定义是next[i]表示s的前缀s[0..i]中最长的相等的真前缀和真后缀的长度。对于整个字符串s长度nlen - next[n-1]得到的是一个候选的循环周期。如果len % (len - next[n-1]) 0那么s可以由前面这个子串重复构成否则不能。这个性质可以这样理解如果字符串是由某个长度为p的子串重复构成的那么它的最长公共前后缀长度一定是n-p整个字符串去掉最后一段后剩下的部分既是前缀又是后缀。反过来如果next[n-1]不是n-p说明不存在这样整齐的周期结构。C实现class Solution { public: bool repeatedSubstringPattern(string s) { int n s.size(); vectorint next(n, 0); for (int i 1, j 0; i n; i) { while (j 0 s[i] ! s[j]) { j next[j - 1]; } if (s[i] s[j]) { j; } next[i] j; } int cycle n - next[n - 1]; return cycle ! n n % cycle 0; } };这个代码里的while循环就是KMP的核心当字符匹配失败时不是从头开始而是利用已经算好的next数组回退到一个可能匹配的位置。对于abacaba这个模式串它的next数组算出来是[0, 0, 1, 0, 1, 2, 3]next[6] 3n - next[6] 4而7 % 4 ! 0所以abacaba不是由某个子串重复构成的。笔试的时候我建议把这类小例子手动算一遍再提交因为next数组下标的细微错误会导致死循环或者结果错乱这种错在纸面上很好排查。3. 笔试中最容易翻车的四类坑踩坑实录3.1 输入输出cin、getline和耗时优化的那些事校招笔试的输入格式大体分两种一种先给T表示有几组测试数据另一种是单组数据直接读到底。很多同学今天写LeetCode写习惯了一到要自己处理输入就手忙脚乱。常见的坑有三个。第一是cin和getline混用先用cin n读一个整数后输入缓冲区里还留着一个换行符紧接着用getline(cin, str)会直接读到空行。解决方法是读完后加一句getline(cin, str)把换行符吃掉或者统一用getline读整行再解析。第二是关闭同步的问题在代码开头写上ios::sync_with_stdio(false); cin.tie(nullptr);能明显加速但如果你后面又混用了scanf/printf这个优化就会出错所以要么全用C风格要么全用C风格不要混。第三是循环处理T组数据时变量忘记重置比如上一组的vector没有clear导致累加结果出错。这类问题通过每组数据都新建局部变量就能规避。3.2 边界条件空集、单元素和溢出边界条件是最容易让思路完全正确的代码拿到WAWrong Answer的原因。举几个我在笔试里真实踩过的例子数组长度为0或1时你的主逻辑是否还能正常工作很多贪心和DP代码在长度小于2时会越界或直接走空循环。排序后第一个元素和最后一个元素相等的情况比如所有区间都是[1,1]你的答案应该是1还是n整数溢出题目如果没说明数值范围假设输入是10^9量级两个数相加就可能超过int的范围。稳妥的做法是直接用long long虽然内存多一点但安全性高得多。负数与0的运算比如差分数组里diff[r1] - k如果k可以是负数你要确保后续的前缀和逻辑不受影响。我的建议是每写完一道题不要急着提交先构造三组测试数据空输入、单元素、所有元素相同。这三种极端情况能暴露90%以上的边界问题。3.3 复杂度与爆栈样例过了但WA/TLE的隐藏原因样例过了但提交超时TLE或内存超限MLE是笔试中最让人崩溃的情况。这里有几个容易被忽略的细节递归爆栈如果你的DFS深度达到10^5甚至10^6很多在线评测系统的默认栈空间是撑不住的会直接段错误。解决方案是改成显式栈的迭代写法或者把递归深度缩小一个量级。在循环里初始化大数组比如每组测试数据都要memset一个100万长度的数组如果T很大这个清零操作本身就是O(T*n)会拖慢整体速度。更优的做法是用变量记录哪些位置被更新过最后只清理这些位置。vector开得太随意二维vector如果大小是1000x1000初始化还行但如果是1000x10000初始化可能就会卡顿。建议用一维数组来模拟二维下标或者明确预估内存一个int是4字节1000万int大约是40MB已经接近不少在线评测系统的内存上限了。3.4 思维惯性拿到题就写DP结果贪心更简单参加笔试次数多了你会发现人很容易陷入思维惯性。比如看到最多、最少、最优就默认是动态规划看到字符串匹配就默认是KMP。但事实上很多题贪心比DP更简洁暴力加优化比经典算法更不容易出错。以T1区间调度为例如果你一上来就认定它是DP不是不能做但状态定义、转移方程都会复杂很多消耗的时间足够你把T2差分数组做完了。这里的关键判断标准是这个问题是否具备贪心选择性质简单说就是每一步都选当前看起来最优的最终结果是否一定最优如果能构造反例才考虑DP。反之如果你看不出反例那贪心大概率是出题人想要的解法。我建议在正式写代码前先花30秒钟在草稿纸上画几个小例子用不同策略推一遍。这个习惯能帮你避免写到一半发现方向错了的大事故。4. 复盘为什么这套题要这样设计4.1 从T1到T4的难度阶梯在考什么这套算法二的题目分布其实反映了校招算法笔试出题的一个共性思路不是要你背多少冷门算法而是要考察你面对不同复杂度问题时的应对能力。T1考的是识别能力——能不能看穿区间调度背后的贪心模型T2考的是优化意识——能否把显而易见的O(n*m)暴力优化到O(nm)T3考的是经典算法熟练度——拓扑排序是图论里最高频的考点之一必须做到看到先修关系就能条件反射T4考的是对算法原理的深度理解——KMP很多人都背过模板但真正理解next数组的数学含义、并把它迁移到循环节问题上的人远没有想象中那么多。从这些维度看出题人其实并不追求考倒你而是在筛选真正动手写过代码、思考过算法原理的候选人。只会背模板的人在T4会卡住只会暴力的人在T2就会暴露而平时刷题爱看题解、不爱手写推导的人很可能在T3的边方向上翻车。4.2 差分数组、拓扑排序与KMP背后的通用能力这三类算法表面上是三个独立的知识点但背后有一条统一的线索用更巧妙的表示方式降低计算复杂度。差分数组的核心是把区间更新转化为端点更新拓扑排序的核心是把关系约束转化为处理顺序KMP的核心是把已匹配的信息缓存下来避免重复匹配。它们都在做同一件事——不重复计算已经知道的东西。理解了这条线索你就能举一反三。比如看到区间加、区间求和的多次操作你会自然想到线段树或树状数组看到依赖关系、顺序约束你会想到拓扑排序甚至强连通分量看到大量字符串匹配你会想到KMP、AC自动机或Trie。这种由题目特征映射到算法家族的能力才是笔试真正在考察的东西。备考的时候不要只刷题每周花一点时间做归纳总结把每道题归到它所属的算法家族里你会发现刷题效率提升得很明显。4.3 这些考点在后端面试和工程中的延伸很多同学会问校招笔试考这些算法工作以后真的用得上吗我的答案是比较肯定的直接用的场景不多但这些算法的思维方式在工作中无处不在。拓扑排序的依赖解析是构建工具、包管理器、任务调度系统的核心逻辑。你在前端npm install时看到循环依赖报错背后的检测算法就和T3里判环的逻辑类似。KMP和字符串匹配在搜索引擎、敏感词过滤、日志分析里都有应用。差分数组这种端点标记、前缀和还原的思路在很多数据统计场景中甚至能替代一部分线段树的活。所以在笔试复盘时我建议你把每一道题背后的算法和你实习或者项目里可能遇到的场景关联一下。这不仅让复习变得更有趣也让你在后续面试中当面试官问你了解哪些算法在实际系统中的应用时能给出有真实感的回答。5. 备考实战给学弟学妹的刷题路线5.1 算法笔试知识点清单与优先级这里列一份我在准备校招笔试时用的知识点清单标注了优先级希望能帮你节省一些选择时间。优先级知识点典型题型推荐刷题量高频数组、哈希表、栈、队列两数之和、括号匹配、滑动窗口每天2~3题持续20天高频排序与二分快排、归并、二分查找变种10~15题高频贪心区间调度、跳跃游戏、分发饼干10~15题高频动态规划基础背包、最长子序列、编辑距离20题以上中频树与递归二叉树遍历、最近公共祖先、路径和15~20题中频图论基础拓扑排序、最短路、并查集10~15题中频字符串KMP、Trie、字符串哈希10题左右低频复杂DP状态压缩、数位DP、树形DP按需刷低频高级数据结构线段树、树状数组、平衡树按需刷不建议一上来就死磕冷门算法先把高频题型的正确率稳定在80%以上再去拓展中低频内容。笔试考的是在规定时间内稳定拿分而不是什么都会一点但什么都不熟。5.2 两个月冲刺计划可落地版本如果你的笔试还有两个月左右可以参考我总结的阶段划分第一个月是基础期。每天花两个小时刷题按类型分组进行比如这一周只做数组和哈希表下一周只做链表和栈。每道题做完后不看题解自己能再推导一遍复杂度并且尝试用另一种方法实现。这个阶段目标是建立看到题目能联想到算法的直觉。第二个月是专项模拟期。前两周集中攻克中频考点特别是动态规划和图论后两周开始刷真题模拟用牛客网或者LeetCode的比赛功能严格控制时间。模拟的时候不要一边刷题一边翻答案最好是完整地记下每道题的分值和时间模拟完再复盘。笔试前一周重点回归重新看一遍自己刷过的错题和笔记把KMP模板、拓扑排序模板、差分数组模板这类高频模板代码默写一遍。模板代码必须熟到可以在5分钟内写完因为笔试时你不会有多少时间来回忆代码细节。5.3 笔试当天的小技巧最后分享几个笔试当天可以立刻用上的实操技巧。第一进入在线评测系统后先把编译器语言选好如果支持本地IDE测试就先用本地IDE写好再粘贴但粘贴后一定要检查有没有引入本地才有的头文件或调试语句。第二遇到一道题十分钟没有思路立刻跳过把后面会的题先做完再回来。第三对于压轴题即使想不到最优解也要写一个暴力版本提交很多时候评测系统会按样例比例给部分分空着和暴力拿到的分数是有本质区别的。第四如果允许使用本地IDE你可以开一个Word或记事本把每道题的思路和关键样例随手记下来回到题目时能快速恢复上下文。还有一点很多人会忽略在线笔试的代码编辑器通常没有自动补全如果你平时重度依赖IDE提示那么考前一定要习惯在纯文本环境下手写代码把需要的头文件、常用类名、排序接口都记在脑子里。这个习惯上的小调整可能比多刷五十道题更有用。我自己在备考后期就养成了一个习惯每天睡前在纸上默写一次KMP的next数组计算过程和拓扑排序的Kahn算法伪代码。笔试题不会每次都考它们但这类手到擒来的感觉会在整个笔试过程中给我一种踏实的掌控感。算法笔试说到底就是一场在限时内的检索调用验证练习你平时练习得越贴近真实环境考场上的表现就越稳定。