2019年小米秋招的算法B卷到现在我还能想起当时交卷前几分钟手心冒汗的感觉。题目不算偏但覆盖得很扎实字符串、动态规划、贪心、图论、数值计算几乎把计算机专业最核心的那几块基本功都点了一遍。尤其像KMP里next数组的计算、贪心和DP的区别判断、Dijkstra堆优化这类题目谁都会说“我学过”但放到限时在线评测里能不能一次写对就是另一回事了。如果你正在准备算法岗的秋招这篇内容可以当成一份B卷风格的复习坐标轴。我会把当时做题时踩过的坑、考场上验证过的判断方法以及一些“早知道就好了”的细节一起整理出来。1. 先说清楚小米B卷到底在考察什么1.1 笔试平台与答题体验小米校招那几年的在线笔试基本都挂在牛客网这类OJ平台上B卷给我的第一个感觉是题量和时间比想象中紧张形式也很直接——给一个题目描述、限时、提交代码、按测试用例打分。平台一般不允许你本地随意调试太久也没有IDE的自动补全那么舒服。所以平时刷题用什么语言考场上就老老实实用什么语言临时换语言是大忌。尤其是C选手用了Python的库函数或者Python选手在循环里写了大量字符串拼接都可能因为细节吃亏。这种形式决定了笔试考察的不只是“会不会”还包括“在压力下能不能稳定写对”。1.2 算法岗B卷的出题侧重点从我当时刷过的多套卷子和周围同学的反馈来看小米B卷的内容集中在几个方向上模块常见题型出现频率字符串KMP的next数组、模式匹配、前缀函数高动态规划背包、LIS、编辑距离、区间DP高贪心区间调度、哈夫曼、判断贪心可行性中高排序与堆手写快排、堆排序、TopK中图论最短路径、最小生成树、拓扑排序中数值计算快速幂、取模运算、大数处理中低机器学习基础概念选择题、简单推导视岗位很多人看到“算法岗”三个字以为会考机器学习和深度学习模型细节。笔试阶段其实不是主角那些内容往往放到后续专业面里。而粒子群、模拟退火、KL散度、强化学习这类名词更多是面试聊研究方向时才可能展开。B卷的主战场依然是经典算法和数据结构。1.3 打分机制决定做题策略这里有个很重要的认知在线笔试大多是按测试用例通过比例给分的不是只有ACAccepted和零分两档。你写出一个暴力解如果小数据能过也能拿到部分分。所以做题顺序有一个基本原则先保住简单题满分再冲难题的部分分。别在第三题上死磕四十分钟结果第一题因为一个小边界罚了好几轮。我自己习惯的节奏是前5分钟快速扫完所有题给每道题标一个难度等级先做读题最快的两道简单题保证拿满再做中等题如果20分钟内没有稳定思路先写暴力版拿部分分最后才啃最难的题。这套节奏在高强度笔试里很管用尤其是B卷这种看起来“都学过”、实际上处处埋雷的卷子。2. 字符串与模式匹配KMP的next数组真的读懂了吗2.1 next[i]的两种定义先搞清楚再动手字符串题里KMP几乎是必考题。当时B卷里有一类很经典的考法直接给一个模式串比如pabacaba然后问next[i]的值是什么。这种题表面上是“填空题”实际上考的是你对next数组定义的理解程度。因为网上关于next数组的写法实在太多最常见的两种定义Anext[i]表示p[0..i]这个子串中最长的相等真前后缀长度。真前后缀就是前缀和后缀相等但是不能等于整个子串本身。定义Bnext[i]表示当p[i]失配时j应该跳转到的位置。这种写法经常让next[0] -1。两种定义算出来的数组不一样但在匹配时的用法也不一样。最怕的就是脑子里记的是A定义的代码手上按B定义去理解最后数组输出全乱。2.2 手算abacaba的next数组我用定义A来推一遍pabacaba顺便演示如何用前缀函数的方式手算。先记住一个原则计算next[i]时只看p的前i1个字符。i0子串是a没有真前后缀所以长度为0i1子串是ab前缀有a后缀有b不相等所以长度为0i2子串是aba前缀a等于后缀a所以长度为1i3子串是abac长度为1的前后缀分别是a和c不相等长度0i4子串是abacaa等于a长度1再看ab和ca不等所以是1i5子串是abacab前缀ab等于后缀ab长度2i6子串是abacaba前缀aba等于后缀aba长度3。所以按定义A结果是[0, 0, 1, 0, 1, 2, 3]。i子串最长相等真前后缀长度0a01ab02aba13abac04abaca15abacab26abacaba3如果题目要求输出的是失配跳转位置也就是定义B很多教材会写成[-1, 0, 0, 1, 0, 1, 2]。所以做题第一步永远是看清楚题干的定义再动笔。2.3 从next数组到匹配流程KMP匹配的核心思想是当文本串和模式串失配时文本串的指针i不回退只移动模式串指针j到next[j]的位置继续比。这个操作的时间复杂度是O(nm)直观理解就是j在整个匹配过程中最多增加n次而回退也是有限次的总体线性。这里有一个经常被忽略的细节构建next数组的代码本质上和匹配代码是同一个逻辑。如果你能在构建next时理解“自己匹配自己”这件事后面写匹配函数就顺了。下面是用前缀函数方式实现的Python代码输出定义A的next数组def build_next(p): n len(p) nxt [0] * n for i in range(1, n): j nxt[i - 1] while j 0 and p[i] ! p[j]: j nxt[j - 1] if p[i] p[j]: j 1 nxt[i] j return nxt print(build_next(abacaba))输出[0, 0, 1, 0, 1, 2, 3]和手算结果完全一致。2.4 现场写KMP最常见的坑KMP代码量不大但越短越容易在小地方翻车。我见过最多的几类错误用if代替while。构建next时如果p[i] ! p[j]必须不断回退j nxt[j-1]而不是只判断一次。这是最典型的错误。下标从0开始和从1开始混用。有些教材里的KMP为了处理方便让字符串从下标1开始存next数组含义也跟着变。刷题时最好统一用0基写法别一会儿0一会儿1。在Python里用字符串切片代替字符比较。p[:j]这种写法在模式串很长时会拖慢速度而且语义上也不直接笔试场景没必要。忘掉真前后缀的限制。算next[i]时前后缀不能等于整个子串有些人算aa时会把长度写成2正确答案是1。字符串题就是这样定义清楚了代码就是一页纸的事定义没搞清楚背再多模板也是白搭。3. 贪心与动态规划区分它们比背模板更重要3.1 先用反例快速判断能不能贪心贪心和动态规划在笔试里经常一起出现因为很多DP题如果数据范围小也可以“碰瓷”贪心拿部分分。但反过来把贪心用在必须DP的题上往往是整题全错。有一个很经典的找零钱反例硬币面额是[1, 5, 11]要凑出15。贪心策略先拿11剩下4需要4个1总共5枚最优解3个5总共3枚。这个例子说明局部最优每次拿最大面额并不能保证全局最优。如果在笔试里遇到“每次选看起来最划算的”这种思路先试着构造一个反例。5分钟内构造不出来再放心去贪。3.2 0-1背包为什么必须用DP0-1背包是区分贪心和DP最直白的例子。如果物品可以分成任意比例那是分数背包问题按单位价值从大到小装就行这是贪心但如果每个物品只能整体拿或者不拿贪心就会失效。原因在于0-1背包有一个“背包容量”的全局限制。你现在多放一个单位价值高的物品可能把后面几个组合起来价值更高的物品挤掉了。标准DP解法是dp[i][j] 表示前 i 件物品容量为 j 时能获得的最大价值 转移dp[i][j] max(dp[i-1][j], dp[i-1][j-w[i]] v[i])笔试中高频考到的是滚动数组优化因为空间从O(n*W)降到O(W)# 0-1背包滚动数组版本 dp [0] * (W 1) for i in range(n): # 注意逆序更新 for j in range(W, w[i] - 1, -1): dp[j] max(dp[j], dp[j - w[i]] v[i])这里内层循环必须逆序否则dp[j-w[i]]在更新时可能已经包含了第i件物品导致同一件物品被放进去多次退化成完全背包。3.3 线性DP和区间DP的建模套路除了背包B卷常见的DP题型还有两类。线性DPdp[i]通常表示“以第 i 个元素结尾的某个最优值”。比如最长递增子序列LISdp[i] max(dp[j] 1)其中 j i 且 nums[j] nums[i]这是最简单的建模方式。难点在于很多题不会直接告诉你“求子序列”而是把LIS藏在一些任务调度、排队问题里。这时候识别出“顺序相关、选或不选、需要保持相对顺序”这几个特征就很重要。区间DPdp[i][j]表示区间[i, j]上的最优值。典型的是石子合并dp[i][j] min(dp[i][k] dp[k1][j] cost(i, j))区间DP的代码套路很固定先枚举区间长度再枚举起点再枚举分割点。如果你发现题目描述里出现“合并”“切分”“子区间”这类关键词往区间DP上靠。3.4 状态转移写出来却不对多半是边界没初始化DP的转移方程看起来不难真正扣分的地方经常是初始化。我见过不少人在一道“求最小编辑距离”的题上把dp数组初始化为0结果从左上角一路推下来全是0样例都过不了。经验是求最大值dp初始化为0但要单独处理“不可能的状态”比如背包问题里容量为负的情况求最小值dp初始化为一个大数INF比如10**9防止从未合法状态转移过来滚动数组优化后下一轮开始前要考虑上一轮的数据是否残留。0-1背包因为是逆序更新这个问题不明显但在一些按行更新的DP里要记得在每轮开头把边界位重置。贪心和DP的题做题速度和建模熟练度强相关。刷题时可以刻意训练一种习惯拿到题先问自己“局部最优能不能推出全局最优”不能就立刻转DP。4. 基础数据结构排序、堆与最短路径的“手速关”4.1 排序算法优先掌握手写快排和归并排序在笔试题里很少单独考但经常作为大题的中间步骤。比如“按区间起点排序后再处理”“数组里找第K大的数”这些题要求你对手写排序和堆足够熟练。笔试现场我建议重点掌握三个算法的模板快速排序平均O(n log n)最坏O(n^2)。最坏情况发生在每次选的pivot都是最大或最小值时比如对已经有序的数组做经典快排。一个有效补救是随机选pivot或者在partition时用三数取中法。归并排序稳定、时间稳定O(n log n)。归并排序还能顺带解决“求逆序对”这种题因为合并时左半部分和右半部分比较刚好可以统计逆序数量。堆排序原地、O(1)额外空间但不稳定。笔试里主要用来求TopK和手写优先队列。4.2 手写堆排序的完整实现堆排序是个容易“一看就会一写就废”的算法。关键在sift_down下沉操作以及建堆时从最后一个非叶子节点开始。def sift_down(arr, n, i): # 在 arr 的前 n 个元素中调整 i 节点让其满足大顶堆 while True: largest i left 2 * i 1 right 2 * i 2 if left n and arr[left] arr[largest]: largest left if right n and arr[right] arr[largest]: largest right if largest i: break arr[i], arr[largest] arr[largest], arr[i] i largest def heap_sort(arr): n len(arr) # 从最后一个非叶子节点开始建堆 for i in range(n // 2 - 1, -1, -1): sift_down(arr, n, i) # 依次将堆顶放到末尾 for i in range(n - 1, 0, -1): arr[0], arr[i] arr[i], arr[0] sift_down(arr, i, 0) return arr几个容易踩的坑最后一个非叶子节点的下标是n // 2 - 1不是n // 2sift_down的区间长度是变化的每次交换堆顶后要传i而不是n左右孩子存在的前提是下标小于当前区间长度判断千万不能漏排序时如果要升序就用大顶堆要降序才用小顶堆。4.3 Dijkstra堆优化邻接矩阵会超内存图论题里最短路径是高频考点。原生态的Dijkstra算法复杂度是O(V^2)适合稠密图但B卷很多题的数据规模是10^4甚至10^5个节点邻接矩阵直接爆内存必须用邻接表优先队列。堆优化版Dijkstra的核心是用dist数组记录起点到每个节点的最短距离用优先队列最小堆存(当前距离, 节点)每次弹出距离最小的节点如果弹出来的距离比dist[u]大说明是旧数据跳过遍历该节点的邻接边尝试松弛。import heapq def dijkstra(n, edges, start): graph [[] for _ in range(n)] for u, v, w in edges: graph[u].append((v, w)) graph[v].append((u, w)) # 无向图加反向边 INF 10**18 dist [INF] * n dist[start] 0 pq [(0, start)] while pq: d, u heapq.heappop(pq) if d ! dist[u]: continue for v, w in graph[u]: nd d w if nd dist[v]: dist[v] nd heapq.heappush(pq, (nd, v)) return dist这里有一个特别重要的细节if d ! dist[u]: continue这一行不能省。因为同一个节点可能被多次推入优先队列第一次弹出的是最短距离后面弹出的旧记录如果不跳过会重复做无用松弛虽然结果大概率正确但时间复杂度会退化。4.4 图论题的输入陷阱图论题代码写对一半输入处理再坑掉一半的情况很常见。常踩的坑包括节点编号从0开始还是从1开始。题目说1 u n建图时要么下标都减1要么数组开n1大小千万别混有重边。邻接表存边时重边要取最小值不能直接append两条后不管自环。自环一般不参与最短路更新因为w一定大于等于0但如果题目给负权自环Dijkstra直接没法用无向图要加双向边。少加一条测试用例直接过半失败。这些细节在平时刷题时不一定会暴露因为样例往往比较简单。到了B卷这种多测试用例按比例给分的场景边界输入就变成了区分度所在。5. 快速幂与数值题模运算里的坑要多留个心眼5.1 快速幂的二进制分解原理数值计算题中快速幂几乎是最常考的小知识点。比如求a^b mod p如果b是10^18级别直接循环乘会超时。快速幂的思路是把指数拆成二进制。假设b13二进制是1101那么a^13 a^8 * a^4 * a写代码时可以这样理解我们把a不断自乘得到a^1, a^2, a^4, a^8...同时扫描b的二进制位凡是位为1的就把对应的幂乘到结果里。def quick_pow(a, b, mod): res 1 % mod while b 0: if b 1: res res * a % mod a a * a % mod b 1 return res这里有个小细节res 1 % mod是为了兼容mod1的特殊情况。如果mod1任何数取模都是0直接返回0更安全。5.2 快速幂的经典变体矩阵快速幂笔试里有种进阶考法是把快速幂套在矩阵上典型场景是斐波那契数列。斐波那契的递推式可以写成矩阵形式[F(n) ] [ [1, 1], [1, 0] ]^(n-1) * [F(1), F(0)]这样求F(n)的复杂度就从O(n)降到O(log n)。矩阵乘法的实现和普通快速幂几乎一样只不过把“乘法”换成“矩阵乘法”。如果你看到一道题说“需要求第 N 项的某个递推值N 很大”第一反应就应该往矩阵快速幂方向想。这也是为什么快速幂虽然基础但在笔试里识别度很高。5.3 模运算的细节模运算有几个细节笔试实战中特别容易出错负数取模。在C里-5 % 3 -2不是1。如果题目要求结果非负记得(x % mod mod) % mod乘法溢出。C的long long乘法在mod接近10^9时res * a可能溢出int必须用long long甚至__int128Python的大整数没有上限这是个优点也是陷阱。优点是你可以放心写乘法不需要担心溢出缺点是在某些巨大数据的题目里Python会因为大整数运算变慢而超时。不要因为“不会溢出”就随意放大复杂度。5.4 数值题的检查顺序数值题代码短但返回值边界很容易错。我的自测顺序是指数为0时结果是不是1注意mod1的特殊情况底数很大时会不会溢出模数为1时结果是不是0指数是奇数还是偶数手工算一个小样例对拍。这些检查加在一起也就两分钟但能避免很多低级WA。6. 读题、写码、调试一份能直接用的临场检查清单6.1 动笔前先用数据范围反推算法笔试最忌讳看完题就开始写代码。更合理的第一步是看数据范围。n 20可以枚举子集、状压DPn 10^3O(n^2)可以接受n 10^5必须O(n log n)或更优n 10^7基本只能O(n)或O(n log n)但常数要小。如果你发现题目数据范围是10^5你的思路却是双重循环那大概率方向错了。趁早回头改思路比写完再优化更省时间。6.2 边界条件自测清单每次写完代码花两分钟检查这些边界空输入数组为空、字符串为空、图没有边单元素只有一个节点、只有一个字符全相同所有元素都是同一个值排序题、去重题尤其常见最大值/最小值数据范围两端比如10^9、0、负数无解情况题目让你求路径但起点和终点不连通重复元素排序和二分查找时重复值会影响正确性。这些边界在样例里通常不会出现但评测系统的隐藏测试用例会专门针对它们。提前自测能救回很多分。6.3 时间不够时的抢分策略如果真的卡在难题上不要直接放弃。把暴力解法写出来注释写清楚思路通常能拿到部分分。以下是几个优先级先保证简单题通过且不留任何低级错误中等题暴力版能过几个测试点算几个难题只写思路和伪代码不纠结完整实现宁可交一份能跑的慢代码也不要交一份“写完但没跑过样例”的代码。在线笔试和面试不一样它看的是最终结果。你在注释里写得再天花乱坠评测机也只会编译你的代码。6.4 考后复盘怎么做每次模拟笔试或正式笔试结束后我建议立刻做三件事记录每道题的卡点是建模不会、边界没考虑、还是纯粹手速不够把没AC的题重写一遍直到不看题解也能稳定通过统计自己做题时的时间分配如果某类题总是超时说明需要专项训练。以我个人的体会来说秋招笔试真正的差距往往不在“难题会不会”而在“基础题是否稳定”。KMP的next数组定义、Dijkstra堆优化里那行continue、0-1背包的逆序更新、快速幂对mod1的特殊处理——这些细节单独拿出来都不难但在限时环境下能全部写对确实需要平时一点一点磨出来。最后再分享一个我后来一直在用的方法每周固定时间做一场模拟笔试严格按考试节奏来到点就交。多模拟几次你会发现考场上最可怕的不是题目难而是自己对时间的失控感变得可控了。这套流程坚持下去比考前突击多刷两百道题更踏实。