企业官网建设流程全解析

小米2019秋招算法笔试题（B）这套卷子，我前前后后刷了三遍。第一遍是照着网上的回忆版硬做，卡在 KMP 的 next 数组上；第二遍是整理考点，发现它几乎把算法笔试最核心的模块都覆盖了；第三遍再刷，已经是拿它当面试前的自测清单用了。如果你正在准备算法岗的秋招或春招，或者只是想看看自己的算法基本功有没有退化，这套题都值得认真过一遍。

先说结论：这套 B 卷放在当年大厂笔试里，难度不算最变态，但很“小米”——不追求偏题怪题，更看重基础是否扎实、代码是否干净。题型大致是选择、填空、编程题混合，覆盖了字符串匹配、排序、动态规划、贪心、图论这几大块。网上热词里反复出现的 KMP、堆排序、Dijkstra、贪心算法，基本就是当年考场上的真实画风。

1. 先看全局：B卷的考点分布与命题风格

1.1 题型结构与时间分配

2019 年小米秋招算法 B 卷并没有公开的官方版本，现在能看到的都是考过的同学回忆出来的题。我根据回忆版和自己的考场经验，把结构整理成了一张参考表。具体题号可能记不准确，但考察范围基本是确定的。

这个时间分配是我自己模拟考的时候验证过的。选择题和填空题看着分少，但特别拉分，因为算法岗的简历初筛很看重笔试成绩，一道概念题错了可能就掉一个档。编程题是主战场，但不宜死磕某一题，卡了 15 分钟还没思路就先跳过，把能拿的分都拿了再回来。

1.2 高频考点画像

我复盘的时候把高频考点和网上的算法热词做了个对照，B 卷真正想筛的其实就是下面这几块：

粒子群算法、模拟退火这类智能优化算法，偶尔也会出现在选择或判断题里，但通常只是让你判断“哪个属于确定性算法”或者“哪个不适用于离散优化”，属于扩展知识。B 卷的主旋律还是经典数据结构和通用算法，所以备考重心不用放在那些花哨的名词上。

2. 核心考点深度拆解

2.1 KMP 的 next 数组到底怎么算

KMP 算法是整套 B 卷里最出名的一道题，因为网上讨论最多的就是“模式串 p='abacaba' 的 next 数组是多少”。这个考点看起来简单，但它同时考察了三层能力：懂不懂前缀和后缀的概念、能不能手算、能不能用代码递推出来。

先明确一个基础定义。对于模式串的一个前缀子串，它的最长相等真前后缀长度，指的是这个子串中，既是前缀又是后缀、且长度小于子串本身的最长部分的长度。比如子串abab，前缀有a, ab, aba，后缀有b, ab, bab，最长公共前后缀是ab，长度是 2。

对于p="abacaba"，我们逐位算一下最长相等真前后缀长度：

这里就引出了很多同学栽跟头的地方：next 数组有两种常见定义。一种是“前缀函数数组”，记作 pi[i]，直接存上面表格里的最长相等真前后缀长度；另一种是“失配跳转数组”，表示第 i 位失配时应该跳到哪个位置继续匹配。这两种定义在笔试题里都出现过，如果题目没有给明确公式，一定要先看它要求的是哪一个。

如果题目要求的是“第 i 位失配时跳到 next[i]”，其中 next[0] = -1，那么p="abacaba"的 next 数组应该是：

next = [-1, 0, 0, 1, 0, 1, 2]

这个结果怎么来的？把上一张表的长度往右移动一位，空出来的 next[0] 填 -1 就行。next[1] 对应 pi[0]=0，next[2] 对应 pi[1]=0，next[3] 对应 pi[2]=1，以此类推。如果题目下标从 1 开始，那么可能写成[0, 0, 0, 1, 0, 1, 2]。所以做题之前先看下标习惯，别把所有版本混在一起。

提示：KMP next 数组题，最容易犯的错误不是不会算最长前后缀，而是不清楚题目用的是前缀函数还是失配跳转。拿到题先看定义再动手。

2.2 排序算法：复杂度与稳定性是选择题重灾区

排序算法在笔试里的地位非常稳定，几乎必考。因为一个排序问题可以延伸出很多维度：时间复杂度、空间复杂度、是否稳定、是否原地排序、最好最坏情况、比较次数、适合数据规模等等。选择题想拉开差距，出排序是最划算的。

我当时整理的速查表是这样的：

笔试里快速排序的出现频率最高，因为代码短但细节多。小米 B 卷有一道选择题印象很深：“快速排序在什么情况下退化到 O(n²)？”答案是当每次 partition 选到的 pivot 都恰好是当前区间最小或最大值时，比如对已经有序的数组固定取第一个元素作为 pivot。这个点本身不难，但很多人只记得平均复杂度，忽略了退化条件。

另外，堆排序和归并排序也常被用来考察“稳定性”这个概念。很多前端或者客户端方向的候选人容易混淆，因为 JavaScript 的Array.prototype.sort()在不同引擎里的稳定性都不一样。笔试题基本都是基于经典教材的定义，别拿工程实践来杠。

手写排序算法是编程题的一个备选项，我后面会单独拿一节来讲快排的完整写法。

2.3 动态规划：先定状态，再写转移

B 卷的编程题里，动态规划的出镜率极高。小米的算法岗笔试不可能不考 DP，因为 DP 最能看一个人的逻辑归纳能力。

我复盘时遇到最有代表性的一个题是最长上升子序列（LIS）。题目很简单：给定一个无序整数数组，找最长严格递增子序列的长度。比如[10, 9, 2, 5, 3, 7, 101, 18]的答案是 4，对应[2, 3, 7, 101]。

DP 的第一步是定义状态。定义dp[i]表示以nums[i]结尾的最长上升子序列长度。这里的关键词是“以 nums[i] 结尾”，因为只有确定了结尾，才能判断下一个元素能不能接上去。

第二步是初始化。每个元素都可以独自成为一个子序列，所以dp[i]初始为 1。

第三步是转移方程。对于每个i，遍历它前面所有j < i，如果nums[j] < nums[i]，说明nums[i]可以接在以nums[j]结尾的子序列后面，此时dp[i] = max(dp[i], dp[j] + 1)。

最后答案就是dp数组的最大值。

def lengthOfLIS(nums): n = len(nums) dp = [1] * n for i in range(n): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp) if n > 0 else 0

这个解法的时间复杂度是 O(n²)，在 n 不大的情况下够用。如果 n 到 10⁵，就必须用贪心加二分优化成 O(n log n)。这个优化思路叫“耐心排序”，维护一个 tails 数组，tails[k]表示长度为 k+1 的上升子序列的最小末尾值，然后对每个元素二分查找它的插入位置。写法不一样，但背后的状态含义更抽象。笔试时如果时间允许，建议先写 O(n²) 版，因为不容易错；如果明确给了大数据范围，再写二分优化版。

2.4 贪心与图论：从“看起来对”到“证明对”

贪心算法的题在 B 卷里往往以中等难度出现，最经典的模型是区间问题。比如“给定一系列区间，选出尽量多的互不重叠区间”或者“用最少的点覆盖所有区间”。这类题的共同点是：先排序，再按某种策略逐个决策。

以“最多互不重叠区间”为例，正确策略是按照区间结束时间从小到大排序，然后依次选择第一个结束的区间，再跳过所有与它重叠的区间。这个策略的直观解释是：结束得越早，后面能留下的空间越大，所以越可能选到更多区间。笔试里除了写出代码，还要能说清楚“为什么贪心策略是对的”，这在简答题里很加分。

图论部分，B 卷经常涉及 Dijkstra 和拓扑排序。Dijkstra 考得最多的是一个判断题：“Dijkstra 算法为什么不能处理负权边？”标准回答是：Dijkstra 每轮从当前未访问的点中选一个距离最小的点，把它当成已确定最短路的点，这个“已确定”依赖当前距离已经是最小值；如果存在负权边，后面可能出现“通过负权边达到更小距离”的情况，但这个点已经被标记完成了，无法再更新。记忆方法就是，Dijkstra 本质是贪心，贪心的前提是局部最优等于全局最优，负权边会破坏这个前提。

拓扑排序也有一个经典实现套路，叫做 Kahn 算法。维护一个入度表，先把所有入度为 0 的点入队，然后逐个出队，每出队一个点，就把和它相邻的点入度减 1，如果某个相邻点入度变成 0，就继续入队。队列为空时，如果访问过的点数不等于总点数，说明图里有环。

def topoSort(n, edges): from collections import deque indeg = [0] * n graph = [[] for _ in range(n)] for u, v in edges: graph[u].append(v) indeg[v] += 1 q = deque([i for i in range(n) if indeg[i] == 0]) res = [] while q: u = q.popleft() res.append(u) for v in graph[u]: indeg[v] -= 1 if indeg[v] == 0: q.append(v) return res if len(res) == n else []

如果返回空列表，说明存在环。这段代码在笔试中的通过率很高，因为逻辑固定，不太需要现场发挥，但前提是你真的理解了入度表的含义。

3. 实战复盘：高频题手写全过程

3.1 手写快排，从递归到边界处理

快排在小米 B 卷里既可能出现在选择题，也可能出现在编程题第一题。我建议所有人把快排背成肌肉记忆，因为它是很多复杂算法的底子，比如 Top-K 问题可以用快排的 partition 思想做部分排序。

我常用的快排实现是双指针版本：

void quickSort(vector<int>& nums, int left, int right) { if (left >= right) return; // 空区间或单元素直接返回 int i = left, j = right; int pivot = nums[(left + right) / 2]; // 取中间元素作基准 while (i <= j) { while (nums[i] < pivot) i++; // 左边找大于等于 pivot 的值 while (nums[j] > pivot) j--; // 右边找小于等于 pivot 的值 if (i <= j) { swap(nums[i], nums[j]); i++; j--; } } quickSort(nums, left, j); quickSort(nums, i, right); }

这里有两个细节容易犯错。第一，pivot 不要固定取nums[left]，否则遇到已经有序的数组会退化到 O(n²)，取中间元素能在绝大多数情况下避免这个坑。第二，循环条件是while (i <= j)而不是while (i < j)，因为这样才能保证分区后左边和右边都严格小于原区间，不会出现无限递归。我见过很多人在这个条件上写错，递归栈溢出直接白给。

如果笔试环境不支持递归，可以改成显式栈模拟递归，但一般情况下 Java 和 C++ 的递归深度足够处理 10⁵ 的数据，不需要自己实现栈。

3.2 KMP next 数组现场计算演示

前面已经讲了手算 next 数组，这里再补一个代码版本。如果题目要你写一个函数来计算 next 数组，最稳妥的方式是用前缀函数思想递推：

vector<int> buildNext(const string& p) { int m = p.size(); vector<int> pi(m, 0); int j = 0; for (int i = 1; i < m; i++) { while (j > 0 && p[i] != p[j]) { j = pi[j - 1]; } if (p[i] == p[j]) { j++; } pi[i] = j; } return pi; }

这段代码算出来的是前缀函数pi。如果你要的是失配跳转数组，还需要把pi整体右移一位，next[0] = -1。具体到这个题目模式串p="abacaba"，算出来的pi是[0, 0, 1, 0, 1, 2, 3]，右移后得到[-1, 0, 0, 1, 0, 1, 2]。这一步在很多题解里没有写清楚，但恰恰是考试最容易丢分的地方。

3.3 编辑距离的两种写法

编辑距离是 DP 题里另一个高频面孔。题目描述是：给两个字符串 word1 和 word2，允许插入、删除、替换三种操作，求把 word1 变成 word2 的最少操作次数。

状态定义是dp[i][j]表示word1前 i 个字符变成word2前 j 个字符需要的最少操作数。

初始化：dp[i][0] = i，因为要把一个长度为 i 的字符串变成空串，只能删除 i 次；同理dp[0][j] = j。

转移方程考虑三种操作：

• 删除：dp[i-1][j] + 1
• 插入：dp[i][j-1] + 1
• 替换：如果word1[i-1] == word2[j-1]，则dp[i-1][j-1]，否则dp[i-1][j-1] + 1

取三者最小值。

def minDistance(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], dp[i][j-1], dp[i-1][j-1]) + 1 return dp[m][n]

由于每一行只依赖上一行和当前行，可以用两个一维数组滚动更新，把空间复杂度从 O(mn) 降到 O(n)。笔试时如果没要求优化，先写二维版本，因为编码更直接，不容易漏初始化。

3.4 贪心小题：区间选点

B 卷的贪心题很可能给一个具体场景，比如“有一些课程，每门课有开始时间和结束时间，选尽可能多的课程，不能冲突”。这就是经典的区间调度问题，直接用贪心。

def intervalSchedule(intervals): intervals.sort(key=lambda x: x[1]) count = 0 last_end = float('-inf') for start, end in intervals: if start >= last_end: count += 1 last_end = end return count

按结束时间排序是这类问题的通用解法。关键是为什么不能按开始时间排序？因为一个开始早的区间可能很长，会挡住后面很多区间；而结束时间越早，给后面留下的空间越大。这种反例在考试中一定要会举，比如区间[1, 100]和[2, 3]、[4, 5]，如果按开始时间排序，选了[1, 100]就只能选 1 个，而按结束时间排序可以选 2 个。

4. 刷题血泪史：笔试里的常见坑与排查技巧

4.1 next 数组定义不清导致功亏一篑

这个坑我栽过，而且是实实在在在模拟笔试里栽的。当时题目写的是next[i]定义为“当第 i 位失配时，模式串跳转到的位置”，但我脑子里默认用了前缀函数的定义，结果填出来的数组完全对不上。后来我发现，很多培训机构讲 KMP 时用的是“最长相等前后缀长度”作为 next 值，而考研教材和互联网笔试题又常常用“失配跳转位置”作为 next 值。两种定义之间只差一个右移，但题目不会告诉你它用的是哪种。

我的建议是：考场上看到 next 数组题，先看题目有没有给出定义公式。如果给了，严格按照公式算；如果没给，优先采用失配跳转位置的定义，也就是next[0] = -1或next[1] = 0的版本，因为这是大厂笔试最常见的写法。同时，为了保险，可以把两种定义都写在草稿纸上对比一下，再填答案。

4.2 数据范围决定算法选型

算法笔试里最难受的不是不会做，而是“我明明写出了正确代码，但超时”。小米 B 卷的编程题不会明着告诉你数据范围，但它会在题目描述里给一些隐含线索，比如“数组长度不超过 10⁵”。看到这个量级，基本可以排除 O(n²) 的暴力解法，应该直接往 O(n log n) 或 O(n) 方向想。

我自己的习惯是：拿到题目先看数据范围，心里估算一下。10³ 以内可以用 O(n²)，10⁵ 左右要用 O(n log n)，10⁶ 以上基本要 O(n) 或者接近 O(n)。动态规划题尤其要关注这一点，因为 DP 的朴素写法往往就是 O(n²)。

如果代码写完了突然发现复杂度不对，不要慌，先看能不能优化。比如最长上升子序列可以从 O(n²) 优化到 O(n log n)，编辑距离可以用滚动数组优化空间，快排可以用随机 pivot 优化退化情况。这些都是笔试考场上性价比很高的操作。

4.3 输入输出与调试技巧

在线笔试的输入输出格式和本地刷题很不一样。小米用的笔试系统当年是赛码网，输入可能有多组测试用例，每组之间用空行隔开。很多人不是不会做，而是卡在读取数据上。

经验教训是：笔试前先熟悉常见输入模板。比如 C++ 用cin读取不知道有多少组的输入时，用while (cin >> n)；Java 用hasNext()；Python 用sys.stdin按行读。另外，输出格式一定要精确到空格和换行，有的题要求“每个答案占一行”，有的要求“答案之间用空格分隔”，少一个空格就是 Wrong Answer。

还有一个调试技巧：本地测试时，除了题目示例，一定要自己造几个极端小数据，尤其是空数组、单元素数组、全相等数组、最大数据范围。这些边界情况最容易暴露出代码里的隐患。我在笔试时吃过亏的是求数组最大值时初始值设为 0，结果数组里全是负数，答案直接错了。正确的初始值应该是nums[0]或者INT_MIN。

4.4 时间分配：先做编程还是先做填空？

这可能是因人而异的，但我的建议是先做有把握的填空和选择，因为它们拿分快，能建立信心。KMP next 数组这种填空题，只要定义看清了，两分钟就能写完。然后立刻跳去做相对简单的编程题，至少拿到一题的完整分数。最后把时间留给最难的 DP 或图论题。

千万不要在一道编程题上死磕超过 20 分钟。因为算法岗笔试的通过标准往往不是满分，而是看总排名。如果你把时间耗在一道 30% 通过率的难题上，可能连基础题都来不及写。我刷这套 B 卷时做过一个测试：先做编程题后做选择，总分反而低了，因为时间被长代码吃掉了。所以“先易后难，先快后慢”是我目前最推荐的时间策略。

5. 从B卷看算法面试的底层逻辑

5.1 复杂度直觉比题目本身更重要

这套 B 卷刷到最后，我最大的感触是：它并不想靠偏题怪题难倒你，而是想通过经典题看你有没有“复杂度直觉”。比如看到 KMP，第一反应是 O(m+n) 的字符串匹配；看到 LIS，第一反应是 O(n log n) 可以优化；看到区间调度，第一反应是按结束时间排序。这个直觉不是背题背出来的，而是需要大量刷题和复盘才能形成的条件反射。

面试官出题的时候也一样，他们看重的不是你把这道题做对了，而是你分析问题的路径：能不能先暴力，再优化，最后说清楚每种方案的复杂度和适用场景。如果你的答案里能主动说出“当数据量大时需要换一种思路”，会比闷头写代码好很多。

5.2 错题归因：把每道错题归到知识点

我整理这套 B 卷的时候，做了一个简单的错题表，把每道错题归到对应的知识点，并标注错误原因：是概念不熟、边界没考虑，还是代码实现有问题。比如 KMP next 数组那道题，我标的是“定义混淆”；LIS 那道题，我标的是“忘了考虑空数组”。这样做的好处是，后续复习时不用重头再来，只需要看错题表里高频出现的知识点就行。

5.3 复盘模板：题目、思路、复杂度、容易错点

最后分享一个适合所有人的复盘模板。每做一道题，不管对错，都在笔记里按四栏记录：题目简要描述、核心思路、复杂度、容易错点。小米这套 B 卷做完，我的笔记大概长这样：

这套模板用熟了之后，你会发现很多题其实是在重复考同一个知识点。比如编辑距离、最长公共子序列、最长上升子序列，本质上都是二维或一维 DP，状态定义一换，代码逻辑就很相似。把这些共同点提炼出来，笔试的备考效率会提高很多。

最后说个我自己的小习惯。每次笔试结束，不管考得好不好，我都会趁热把没写对的题重新归类，写进同一个复盘文档，并标上错误原因。小米这套 B 卷的 KMP 题，我当时就写了四个字：定义混淆。等下次再看到类似的 next 数组题，我会先在草稿纸上把两种定义都列出来再动手。笔试本来就是个熟练活，复盘到位了，下一次才能真正避开同一个坑。