猿辅导2023校招笔试算法一复盘：核心考点与解题思路

又是一年校招季，身边不少学弟学妹都在刷算法题、做各家公司笔试。如果你投的是算法岗或后端研发岗，大概率会碰到“猿辅导2023校园招聘笔试（算法一）”这套卷子。这套题以纯算法编程题为主，整体难度中等偏上，既考基础数据结构，也考字符串处理、贪心、动态规划这些高频考点，特别适合用来检验自己突击阶段的真实水平。

这篇文章我会站在复盘的角度，把这套卷子的题型设计、核心考点、典型题目解题过程和踩坑点一次性讲清楚。不管你是刚开始刷题的大三学生，还是准备冲刺秋招的同学，只要能吃透这套题背后的算法思想，后面再遇到类似的校招笔试都会从容很多。

1. 笔试整体设计与思路拆解

1.1 题目构成与考察范围

我印象里“猿辅导2023校园招聘笔试（算法一）”这套卷子并不是考一堆概念题，而是以 4 到 6 道编程题为主，要求在限定时间内完成。题目类型基本集中在下面几个方向：

• 字符串处理：重点考察 KMP 算法、前缀函数、回文串判断等经典问题；
• 排序与查找：不会直接让你背快排模板，而是把排序当作工具，结合自定义比较器解决实际问题；
• 贪心算法：常与区间调度、任务安排场景结合，比如课程排期、教室使用等；
• 动态规划：背包问题、最长上升子序列这类经典 DP 模型出现的频率很高；
• 树与图的基础遍历：二叉树层序遍历、最近公共祖先、拓扑排序等也有不小概率出现。

这套卷子比较有代表性的地方在于，它不会给特别偏难怪的题，但会在边界条件、输入输出格式、代码效率上“卡”很多人。也就是说，题目本身你见过，但能不能一遍写对、能否在复杂数据下不超时，才是拉开差距的关键。

1.2 为什么这样出题：从业务场景反推考点

在复盘这套题之前，我建议大家先想一个问题：为什么猿辅导笔试偏爱字符串和区间问题？这和它的业务背景有关。作为教育科技公司，业务里有很多文本处理、题库检索、课程排期、直播调度等场景。比如学情分析中要对文本做关键词匹配，排课系统要处理大量时间段冲突问题，推荐系统要做 TopK 聚合。这些场景落到笔试题目里，就会变成 KMP 匹配、区间贪心、堆排序这些问题。

所以准备这类笔试，不能只背模板。你需要理解每个算法的适用场景和复杂度边界，因为面试官出题的本质不是考记忆，而是考你在真实业务场景中能否选出合适的算法方案。

1.3 时间分配与做题顺序建议

我的建议是拿到卷子先花 3 到 5 分钟把所有题目通读一遍，按自己熟练度排序。不要被题号顺序带着走，因为题目难度不一定递增。一般优先做自己有把握的中等题，先把保底分拿到手，再回头啃难题。

如果卡在一道题超过 20 分钟，先跳过。笔试时间通常比较紧张，把时间耗在一道题上导致后面的简单题没时间做，是最可惜的情况。另外，很多笔试采用“部分用例通过”的计分方式，即使想不出最优解，也可以用暴力法或特殊数据分支多拿一点分，这个策略在后面的章节我会单独讲。

2. 核心算法知识点解析与实操要点

2.1 字符串处理：KMP 算法与 next 数组的完整推导

字符串匹配是算法岗笔试的高频题，而 KMP 算法中唯一的难点就是 next 数组的求解。如果你只背代码，不理解推导过程，一旦题目换一种 next 数组定义方式，很容易写错。

先明确两个常见定义。一种是“前缀函数” pi[i]，表示模式串 p[0..i] 的最长相等前后缀长度（不包括整个子串自身）。另一种是失配跳转用的 next 数组，表示当模式串第 i 位失配时，j 应该回退到哪个位置。两者有对应关系，但笔试里不同题目可能用不同定义，拿到题先看清题干标注。

以字符串 p = "abacaba" 为例，推导前缀函数值。

• i = 0，子串 "a"，没有相等前后缀，pi[0] = 0；
• i = 1，子串 "ab"，前缀和后缀没有相等，pi[1] = 0；
• i = 2，子串 "aba"，最长相等前后缀是 "a"，长度为 1，pi[2] = 1；
• i = 3，子串 "abac"，无相等前后缀，pi[3] = 0；
• i = 4，子串 "abaca"，最长相等前后缀是 "a"，pi[4] = 1；
• i = 5，子串 "abacab"，最长相等前后缀是 "ab"，pi[5] = 2；
• i = 6，子串 "abacaba"，最长相等前后缀是 "aba"，pi[6] = 3。

所以 p = "abacaba" 的前缀函数数组为 pi = [0, 0, 1, 0, 1, 2, 3]。

如果题目要求的是失配跳转版 next 数组，通常做法是先把 pi 求出来，再用 pi[i-1] 填充 next[i]，并令 next[0] = -1。这类数组错一位的问题非常容易踩坑，一定要先拿几个小例子手工验证一遍再写代码。

KMP 匹配的核心逻辑是：主串指针 i 一直前进，模式串指针 j 根据失配情况回退。匹配成功后记录位置，再让 j = pi[j-1] 继续找下一个匹配。下面是一份 C++ 实现，可以直接套用：

#include <bits/stdc++.h> using namespace std; vector<int> prefixFunction(const string& s) { int n = s.size(); vector<int> pi(n, 0); for (int i = 1; i < n; i++) { int j = pi[i - 1]; while (j > 0 && s[i] != s[j]) j = pi[j - 1]; if (s[i] == s[j]) j++; pi[i] = j; } return pi; } vector<int> kmpSearch(const string& text, const string& pat) { vector<int> pi = prefixFunction(pat); vector<int> res; int j = 0; for (int i = 0; i < (int)text.size(); i++) { while (j > 0 && text[i] != pat[j]) j = pi[j - 1]; if (text[i] == pat[j]) j++; if (j == (int)pat.size()) { res.push_back(i - (int)pat.size() + 1); j = pi[j - 1]; } } return res; }

这里特别注意，j是 int 类型，而pat.size()返回 size_t，比较时一定要强转，否则j == pat.size()在 j 为负时会出问题。我见过不止一个同学因为这种小问题在本地跑通、平台上一分不拿。

2.2 排序算法：不背模板，要理解复杂度边界

排序在算法笔试里很少单独考，但很多题目的前置步骤都离不开排序。比如区间调度要先按结束时间排序，TopK 问题要用堆或者快排思想。所以你必须对常见排序的复杂度、稳定性、适用场景有清晰认知。

笔试时如果没有特殊要求，直接用语言自带的排序函数即可。C++ 的sort()底层是混合排序策略：数据量小用插入排序，量大用快速排序，递归深度过深会切换堆排序，综合性能很稳。你只需要写好自定义比较函数。

这里有个很容易被忽略的点：C++ 的sort要求比较器必须满足严格弱序。如果比较条件写得不严格，比如该相等时返回了 true，在极端数据下程序会直接报错甚至内存越界。比如按区间结束时间升序时，代码应该这样写：

sort(intervals.begin(), intervals.end(), [](const vector<int>& a, const vector<int>& b) { return a[1] < b[1]; });

如果你要按结束时间升序、开始时间也升序做二级排序，就把条件完整写上，不要偷漏a[0] < b[0]那部分。这类细节在笔试中一旦触发未定义行为，很难排查。

2.3 贪心与动态规划：两类易混题型的判断标准

贪心和动态规划是笔试区分度最大的两种题型。很多同学看到每类题都背了一堆模板，但真正题目出来后又分不清该用哪个。

一个比较实用的判断标准是：如果每一步做局部最优选择后，剩余问题仍然是独立的同类子问题，并且这个选择不会影响后面选择时的子问题状态，那大概率是贪心。如果需要枚举所有可能的状态转移，并且存在重叠子问题，那就该用动态规划。

以“无重叠区间”为例，题目给出一组区间，让你移除最少的区间使剩余区间互不重叠。这个问题就是典型贪心，核心结论是：每次优先选择结束时间最早的区间，能保留的区间数就最多。因为结束越早，给后面区间留下的空间越大。反证法可以证明这不是巧合，而是全局最优策略。如果选开始时间最早或者区间长度最短，都会找到反例。

而以 01 背包问题为例，每个物品只能选或不选，这就是动态规划。贪心策略在这里完全不成立，因为选择单位价值最高的物品并不总能带来整体最大价值。二者之间的判断，一定要靠“选择后是否会影响子问题状态”来思考，而不是靠感觉。

2.4 数据结构的组合应用：堆、栈、哈希表的实战结合

除了单一算法，笔试还常考数据结构之间的组合使用。这里我说三个出现频率最高的组合场景。

第一，TopK 问题用堆。求 N 个数里最大的 K 个数，维护一个大小为 K 的小顶堆，堆顶就是当前第 K 大的数。C++ 可以用priority_queue<int, vector<int>, greater<int>>实现小顶堆。注意如果求最小的 K 个，要用大顶堆，这个细节一颠倒结果全错。

第二，括号匹配用栈。处理表达式、验证括号合法性时，栈是最自然的工具。常见变形题包括带通配符的括号匹配、最长有效括号长度等，核心都是利用栈记录下标而不是只记录字符。

第三，前缀和与哈希表组合。求连续子数组和等于 K 的个数，如果暴力枚举左右端点复杂度是 O(n²)，大概率超时。高效做法是维护一个前缀和变量 cur，同时用哈希表记录每个前缀和出现的次数，每遍历一个位置就查询 cur - K 是否存在。这类问题把“区间和”转化为“前缀和的差值”，是笔试中特别常用的套路。

3. 典型真题复盘与核心环节实现

3.1 真题一：字符串匹配（KMP 方向）

我把这套卷子中的一道有代表性的字符串题还原出来，题目大意是：给定文本串 text 和模式串 pattern，求模式串在文本串中出现的所有起始下标，按升序输出。数据范围 text 长度和 pattern 长度都可能达到 10⁵，显然不允许 O(n*m) 暴力匹配。

这个题就是标准 KMP 模板题。解题过程分三步：

• 第一步：对模式串求前缀函数数组 pi；
• 第二步：用 pi 进行匹配，维护指针 j；
• 第三步：当 j 等于模式串长度时，记录当前文本下标减去模式串长度加一，然后回退 j 为 pi[j-1]，继续匹配。

这里我特别想强调最后一步的回退。很多第一次写 KMP 的同学，匹配成功后直接把 j 清零，这在文本串包含重叠匹配时会漏掉答案。比如 text = "abababa"，pat = "aba"，正确输出应该是 0、2、4，因为匹配位置可以重叠。清零的话就只能得到 0 和 4，直接丢分。

时间复杂度方面，前缀函数计算是 O(m)，主串匹配是 O(n)，整体 O(n+m)，完全满足 10⁵ 数据范围的要求。

3.2 真题二：区间调度（贪心方向）

第二类高频题是排课问题。我印象中题目是这样：给出 n 个课程的时间段 [start, end]，要求选择尽可能多的课程，使得所选课程时间不重叠，返回最多能选几节。

这类题解法已经非常固定，三步走：

• 按结束时间 end 对所有区间升序排序；
• 初始化 lastEnd = -∞，ans = 0；
• 遍历排序后的区间，如果当前区间 start >= lastEnd，就选择它，ans++，并更新 lastEnd = end。

这里为什么按结束时间排序？因为一个区间结束得越早，留给后续区间的空档就越大。这个思路用一个简单的反例就能记住：如果按开始时间排序，可能选到一个开始很早、但跨度特别长的区间，反而把后面所有区间都挡住了；如果按区间长度排序，可能选到一个时间上夹在中间的小区间，把两边都截断。只有按结束时间排序能保证每一步都留给后续最多的选择空间。

代码实现并不复杂，但要注意区间可能是乱序输入，也可能包含 start == end 的情况。这类区间如果题目没特别说明，通常视作不产生时间占用，可以直接纳入。遇到题首先要想清楚定义，不要凭直觉判断。

贪心类题目在笔试中给分通常比较稳，边界条件少、码量小，属于“必须拿下”的题型，建议多刷几道巩固手感。

3.3 真题三：01 背包变体（动态规划方向）

动态规划题目在这套卷子里一般会放在中等偏后的位置。有一道题比较有代表性：给定 n 门课程，每门课程需要花费一定时间 cost，并能获得价值 value，在总学习时间上限 total 内，最多能获得多少价值。每门课只能选择学或者不学。

这是一个标准 01 背包问题。如果用二维 dp[i][j] 表示前 i 门课在总时间不超过 j 时的最大价值，状态转移方程为：

dp[i][j] = max(dp[i-1][j], dp[i-1][j - cost[i]] + value[i])

笔试中一般推荐用一维滚动数组优化空间，代码如下：

vector<int> dp(total + 1, 0); for (int i = 0; i < n; i++) { for (int j = total; j >= cost[i]; j--) { dp[j] = max(dp[j], dp[j - cost[i]] + value[i]); } }

这里内层循环必须从 total 向左遍历到 cost[i]。原因很简单：如果正向遍历，dp[j - cost[i]] 可能已经被当前物品更新过，相当于同一门课被重复选择，那就退化成了完全背包。这是 01 背包最容易写错的地方。

如果题目中的数据范围很大，比如 total 达到 10⁵ 级别，而 n 较小，可以考虑用二进制拆分或单调队列优化处理多重背包变体。不过校招笔试能写出一维滚动数组已经能覆盖大部分用例，先保证拿到基础分，再考虑优化。

3.4 真题四：二叉树层序遍历（数据结构方向）

树的问题也出现在这套题里，常见的考法是层序遍历的变形题。比如“二叉树每层的最大值”：给定一棵二叉树，返回每一层节点值的最大值，按层序输出。

核心解法是用 BFS 加队列，并用当前队列长度控制每层的节点数量。这是一个非常经典的模板：

vector<int> largestValues(TreeNode* root) { vector<int> ans; if (!root) return ans; queue<TreeNode*> q; q.push(root); while (!q.empty()) { int sz = q.size(); int mx = INT_MIN; for (int i = 0; i < sz; i++) { TreeNode* cur = q.front(); q.pop(); mx = max(mx, cur->val); if (cur->left) q.push(cur->left); if (cur->right) q.push(cur->right); } ans.push_back(mx); } return ans; }

这里有几个关键点需要提醒。第一，queue的元素如果是指针，注意判空，空树不要直接访问根节点。第二，每层遍历前先记录sz = q.size()，这个操作必须在循环外，因为入队子节点会改变队列大小，如果在循环内实时计算q.size()就会出错。第三，节点值可能是负数，所以每层最大值初始化为INT_MIN，不能初始化为 0。

层序遍历的变体还包括锯齿形遍历、右侧视图、每层平均值等。只要把“记录每层节点数量”这个模板吃透，这些题都可以快速套用。

4. 实战过程中的常见问题与排查技巧

4.1 笔试环境与输入输出处理

校招笔试和 LeetCode 最大的区别在于输入输出要自己处理。很多人做惯了核心代码模式，一换到 ACM 模式就吃不消，经常在 IO 上浪费大量时间。

C++ 输入数据量较大时，必须在主函数开头加一行：

ios::sync_with_stdio(false); cin.tie(0);

不加的话，cin 的缓冲区同步开销会导致大数据下运行时间翻倍，原本能过的复杂度也可能被判超时。Python 则建议用sys.stdin.readline，不要用input()一行行慢慢读。

读取未知行数的输入也是个高频问题。C++ 里用while (cin >> x)可以一直读到文件结束符，适合“第一行是测试用例数，后面跟着多行数据”的题目。Python 里可以用：

import sys def main(): data = sys.stdin.read().strip().split() # 再按位置解析每个数字

一次性读取全部输入再解析，是处理复杂输入格式最稳妥的方式，也避免了逐行input()可能遇到空行的坑。

4.2 边界条件与极端用例

我复盘这套卷子时最大的感受是，很多同学跪在边界条件上，而不是算法本身。常见的几类边界问题我列在下面：

笔试前可以在草稿纸上给自己出几个极端用例，比如 n=0、n=1、全部元素相等、答案非常大的情况，把代码过一遍。很多时候平台返回“答案错误”而不是“运行超时”，就是因为你在某个边界上多算或少算了 1。

4.3 复杂度预判与算法取舍

拿到一道题不要急着写代码，先看数据范围。数据范围直接决定了你能用什么复杂度的算法，这是一个非常重要的经验。

• 如果 n ≤ 20，可以暴力枚举、状态压缩；
• 如果 n ≤ 10³，O(n²) 的算法可以接受；
• 如果 n ≤ 10⁵，就必须用 O(n log n) 或 O(n)；
• 如果 n ≤ 10⁹，常规遍历基本没戏，通常要二分、数学公式或矩阵快速幂。

以 2.3 中提到的“连续子数组和等于 K”为例，如果 n 是 10⁵，O(n²) 枚举子数组会超时，这时候就应该立刻想到前缀和加哈希表，而不是继续调暴力代码。这个“先看数据范围、再定算法”的习惯，能帮你在考场上省下大量试错时间。

4.4 心态与时间管理

最后说点实际建议。笔试过程中卡题是常态，一套卷子每道题都是满分的人很少。遇到没思路的题，先把能拿的分数拿到，比如暴力法解决 30% 的测试用例，也比交白卷强。很多平台的判分规则是“通过的用例数占该题总用例数的比例”来计算得分，所以不要轻易放弃任何一道题。

我的做题习惯是：先花 2 分钟看数据范围和数据特征，如果可以暴力，立刻写一版暴力保底；如果写出暴力后还有时间，再继续优化成正解。这样既不会因为空题导致 0 分，也能在有限时间内最大化收益。

复盘“猿辅导2023校园招聘笔试（算法一）”这套题时，我最真实的感受是：它并没有故意刁难人，考的都是主流算法，但非常看重基本功是否扎实。KMP 的 next 数组理解不透、01 背包内层循环方向写反、BFS 分层时队列大小没先存下来，这些细节才是真正决定你能不能过的那道坎。

如果时间允许，建议把 KMP、前缀和加哈希、区间贪心、01 背包、二叉树层序遍历这五个模板练到闭着眼睛能写出来的程度，再配合几套真题模拟掐时间训练，比盲目刷几百道题更有用。笔试拼的不是谁见过的题多，而是谁在压力下把基础题写得更稳。