2020年8月8日下午我参加了一场在线算法岗笔试。这场笔试整体难度不算温和题量也不小三个小时里我经历了“前面顺风顺水、中间卡成狗、最后仓促提交”的典型过程。考完当天晚上我把每道题重新梳理了一遍今天写这篇算法岗笔试复盘把题目模型、解题思路、考场上踩过的坑以及后续准备方法一起整理出来。如果你也在准备算法类岗位的在线笔试这篇文章应该能帮你少走一点弯路。笔试整体并不是堆模板而是把常见的算法模型包在业务场景里考察的是“识别模型”和“稳定输出”的能力。比如第一题是服务器任务区间本质是区间重叠第二题是字符串编辑代价本质是动态规划第三题是钥匙迷宫本质是状态压缩BFS。如果你能快速看穿这层外衣剩下就是熟练度的问题。1. 笔试基本信息与整体策略1.1 在线笔试的题型与时间安排整场笔试共120分钟前60分钟做10道选择题和填空题后60分钟做3道编程题。不过实际页面上所有题目同时可见可以自己分配时间。我的策略是快速扫一遍所有题目先判断哪部分性价比高而不是傻傻地从选择题第一题开始按顺序往下做。选择题集中在机器学习基础、概率统计和少量数据结构概念上编程题则是比较典型的算法实现。在线评测环境自带一个简易编辑器没有本地IDE的自动补全写完代码必须手动提交测试一旦有语法错误或者边界条件问题窗口期就会很快被消耗掉。这个环境本身就是一个隐藏考点如果平时只在本地IDE里跑题、依赖编译器的错误提示到这种环境里会非常难受。1.2 拿到卷子后的前15分钟决策我没有急着开始敲代码而是先把3道编程题全部读了一遍并在草稿纸上记下每道题的模型和预估复杂度。第一题是给出若干任务的开始和结束时间求同时运行的最大任务数以及对应时间点。这明显是区间重叠问题排序加扫描线就能解决。第二题是字符串变换给出三种操作的代价问最小总代价这是带权编辑距离标准二维DP。第三题是迷宫中有几把钥匙和几扇门需要拿钥匙开门到达终点这是典型的BFS加状态压缩。三题难度递进我把做题顺序定为T1、T2、T3目标很明确先把稳的分牢牢抓住再冲难题。不少同学拿到题目就直接沉浸在第一题里结果在边界条件上反复折腾后面时间不够用。提前花15分钟看清全貌看起来是“浪费时间”实际上是在给后面的自己争取时间。2. 第一题区间重叠峰值计算2.1 题目复述与示例题目大意是系统里有若干定时任务每个任务用一个区间表示运行时间段。假设区间端点也算运行时间需要算出任意时刻最多有多少个任务同时在运行并输出这个最大数量以及最早达到该数量的时刻。举个具体的输入例子4 1 3 2 5 3 6 4 7任务区间分别是[1,3]、[2,5]、[3,6]、[4,7]。在时间3前三个任务都在运行数量是3在时间4后三个任务也在运行数量也是3。题目要求最早达到最大重叠的时刻所以答案是“3 3”。当时我一看这题就知道是经典扫描线但它在题意上加了一个很容易忽略的约束区间是闭区间开始和结束在同一时刻也算重叠。这个小小的定义差异直接决定了排序规则怎么写。2.2 为什么用排序加扫描线而不是双重循环最朴素的做法是枚举每个时间点检查所有区间是否包含它。如果时间范围很大比如最大到10^9根本不可能开数组。另一种朴素做法是每两个区间两两判断重叠再统计重叠次数但复杂度是O(n^2)题目数据量一上来就会超时。扫描线的核心思想是把区间拆成事件区间开始时把当前重叠数加1区间结束时把当前重叠数减1。把所有事件按时间排序后依次处理事件过程中维护重叠数的峰值。这样时间复杂度是O(n log n)主要花在排序上空间复杂度O(n)是这类问题的标准解法。难点在于事件排序的细节。因为区间是闭区间同一个时间点上可能既有任务结束又有任务开始。比如[1,2]和[2,3]在时间2时两个任务同时存在重叠数应该是2。如果排序时结束事件排在开始事件前面扫描到时间2时会先把重叠数减1再加1峰值就漏掉了。所以必须保证同一时刻开始时事件先处理。2.3 参考代码与边界说明我当时写了一份C代码核心逻辑大概是下面这样#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int events; for (int i 0; i n; i) { int l, r; cin l r; events.push_back({l, 0}); // 0表示开始事件 events.push_back({r, 1}); // 1表示结束事件 } sort(events.begin(), events.end()); int cur 0, best 0, ansTime -1; for (auto e : events) { int t e.first; int type e.second; if (type 0) { cur; if (cur best) { best cur; ansTime t; } } else { --cur; } } cout best ansTime \n; return 0; }这里用pair排序pair会先比较时间再比较类型。因为开始事件type是0结束事件type是1所以同一时刻开始事件会排在结束事件前面正好符合闭区间重叠的定义。这个细节非常关键。如果题目改成开区间也就是端点不重叠那么只需要把结束事件排在开始事件前面或者在区间结束时刻处理为减1前先处理开始事件。很多区间题目喜欢在这一点上做文章所以读题时一定要先搞清楚区间开闭。2.4 我在现场踩的坑这题我一开始写得很顺但提交后有一组用例没过。排查后发现不是算法问题而是输出格式的锅。题目要求先输出最大数量再输出最早时刻中间用空格分隔。我写成了cout ansTime best把两个值反了本地样例恰好又看不出问题因为数量和时间值不一样时才明显。这种低级错误很伤士气之后我遇到输出两个以上数值的题目都会特意对照样例检查一遍顺序。另一个坑是我最初在结束事件时也尝试更新一下最大值结果虽然不会报错但ansTime可能被指向错误的时刻。仔细想了一下最大值只可能由一个新的开始事件触发所以只需要在事件类型为开始时更新峰值和对应时间。这样不仅逻辑清晰也能保证“最早达到最大重叠的时刻”是准确的。3. 第二题带权编辑距离的动态规划3.1 题设与三种操作代价第二题的字符串变换问题本质上是一个带权编辑距离。题目给出两个字符串只允许对第一个字符串做三种操作插入任意一个字符代价为1删除任意一个字符代价为2替换任意一个字符为其他字符代价为3。问把字符串a变成字符串b的最小总代价。例如a为catb为cut一种方式是直接把a中的a替换成u代价3。虽然也可以先删除a再插入u但总代价是213两者一样所以答案是3。如果替换代价不是3而是5那么明显删除加插入更便宜。这里的关键是操作成本不对称不能直接用经典编辑距离的无权版本去套。现场我第一反应是“不就是编辑距离吗”差点按照经典转移直接写。还好多看了一眼代价表意识到删除代价和插入代价不同初始化时不能一律用1后续转移也要区分。题目故意把三个代价设置得不一样就是为了拦住那些只会背模板的人。3.2 状态定义与转移方程设dp[i][j]表示字符串a的前i个字符变成字符串b的前j个字符所需要的最小代价。这里a和b的下标都从1开始计数代码中取字符时要记得下标减1。对于当前状态dp[i][j]可以从三种前置状态转移过来从dp[i-1][j]转移表示删掉a的第i个字符然后继续把a的前i-1个字符变成b的前j个字符代价是dp[i-1][j] 删除代价2。从dp[i][j-1]转移表示先让a的前i个字符变成b的前j-1个字符再往末尾插入b的第j个字符代价是dp[i][j-1] 插入代价1。从dp[i-1][j-1]转移表示看a的第i个字符和b的第j个字符是否相等如果相等不需要额外操作代价是dp[i-1][j-1]如果不相等可以把a的第i个字符替换成b的第j个字符代价是dp[i-1][j-1] 替换代价3。三者取最小值即可。注意这里之所以有“插入”和“删除”两个方向是因为“把a变成b”的过程中a里多余的字符会被删掉b里需要但a没有的字符会被插入。理解这个方向后初始化就非常自然了dp[0][0] 0空字符串变成空字符串不需要任何操作。dp[i][0]表示a的前i个字符全部删掉变成空字符串代价为i * 2。dp[0][j]表示从空字符串变成b的前j个字符需要全部插入代价为j * 1。很多人在初始化时想当然认为dp[i][0] idp[0][j] j在有不对称代价的题目里直接就错了。我现场也一度把删除和插入的代价弄反导致所有测试点输出偏大。3.3 参考代码与滚动数组优化下面的实现直接使用二维数组思路最直观#include bits/stdc.h using namespace std; int main() { string a, b; cin a b; int n a.size(), m b.size(); int insCost 1, delCost 2, repCost 3; vectorvectorint dp(n 1, vectorint(m 1, 1e9)); dp[0][0] 0; for (int i 1; i n; i) dp[i][0] i * delCost; for (int j 1; j m; j) dp[0][j] j * insCost; for (int i 1; i n; i) { for (int j 1; j m; j) { int val min(dp[i - 1][j] delCost, dp[i][j - 1] insCost); if (a[i - 1] b[j - 1]) { val min(val, dp[i - 1][j - 1]); } else { val min(val, dp[i - 1][j - 1] repCost); } dp[i][j] val; } } cout dp[n][m] \n; return 0; }如果字符串长度到几千甚至上万二维数组可能内存超标可以优化成一维滚动数组。因为dp[i][j]只依赖当前行左边的dp[i][j-1]、上一行的dp[i-1][j]和左上角的dp[i-1][j-1]。滚动数组需要保存上一行当前列的值和左上角值写起来容易出错。在线做题如果内存足够我建议先写二维版把正确性保住再去想优化不要一上来就炫技能。3.4 这题真正的隐藏扣分点编辑距离相关题目尤其喜欢考边界一个字符串为空。不少解法把dp数组初始化为0然后从i1,j1开始转移结果空串的用例全部出错。我在现场一开始也踩了这个坑因为样例中两个字符串都不为空看起来很正确但提交后包含空串的测试点立刻暴露问题。另一个容易被忽略的是“替换代价可能大于删除加插入”。比如替换代价是10删除代价是2插入代价是1那么把字符x替换成y的最优操作往往不是替换而是先删除x再插入y总代价3远小于10。好在状态转移方程已经自动考虑了这种情况只要把替换代价写进转移公式DP会自己选择更便宜的路径。只要初始化正确这个隐藏点不会造成问题。4. 第三题钥匙迷宫的最短路问题4.1 题设与状态压缩思路第三题是一个网格迷宫题N行M列格子上有起点S、终点E、障碍#、空地.以及最多3把钥匙和3扇门。钥匙编号分别是1、2、3门分别对应A、B、C。只有拿到对应钥匙才能通过门比如没有钥匙1时遇到门A不能走。问从起点到终点的最少步数如果无法到达输出-1。普通BFS的特点是每个格子第一次被访问时到达它的步数就是最短步数。但在这个问题里同一个格子可能会被访问多次因为第一次到达时可能没有某把钥匙第二次到达时有了钥匙能继续走的路就完全不同了。这时候必须把“当前拥有哪些钥匙”也纳入状态于是状态就变成了(x, y, mask)其中mask是一个最多3位的二进制数表示目前拥有了哪几把钥匙。比如mask3二进制是011表示已经拿到了钥匙1和钥匙2还没拿钥匙3。三把钥匙的所有组合一共是2^38种所以访问标记数组可以开成vis[N][M][8]空间非常小。这就是状态压缩BFS的典型套路。4.2 为什么必须用BFS而不是DFS看到求最少步数第一反应就应该是BFS因为BFS天然按层扩展第一次到达目标状态的步数一定是最短步数。DFS也能找到一条路径但无法保证最短除非用迭代加深或者记录全局最优并剪枝那样复杂度通常会高很多。在这个题里每一步的移动代价都是1普通队列就能完成BFS。不需要优先队列也不需要Dijkstra。这也让问题简化了很多关键就在于状态的定义和转移要写对。4.3 参考代码与关键细节这里是我的实现思路#include bits/stdc.h using namespace std; const int dx[4] {0, 0, 1, -1}; const int dy[4] {1, -1, 0, 0}; struct Node { int x, y, state, step; }; int main() { int n, m; cin n m; vectorstring grid(n); int sx 0, sy 0, ex 0, ey 0; for (int i 0; i n; i) { cin grid[i]; for (int j 0; j m; j) { if (grid[i][j] S) { sx i; sy j; } if (grid[i][j] E) { ex i; ey j; } } } bool vis[50][50][8] {false}; queueNode q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] true; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x ex cur.y ey) { cout cur.step \n; return 0; } for (int d 0; d 4; d) { int nx cur.x dx[d]; int ny cur.y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; int ns cur.state; char c grid[nx][ny]; if (c 1 c 3) { ns | (1 (c - 1)); } if (c A c C) { int need c - A; if ((ns (1 need)) 0) continue; } if (!vis[nx][ny][ns]) { vis[nx][ny][ns] true; q.push({nx, ny, ns, cur.step 1}); } } } cout -1 \n; return 0; }这里有一个小坑当格子是钥匙时即使没听过它的编号进入格子后钥匙会自动被拾取所以走到有钥匙的格子后状态一定要更新。如果忘了更新state就会出现“明明踩到了钥匙却打不开门”的滑稽错误。另一个坑是门的判断要放在钥匙更新之后。如果当前格子里有钥匙同时这个格子也是一扇门这种设计在题目里不会出现但代码顺序如果写反可能会影响新状态的可达性。4.4 现场我在第三题上翻车的点这道题我只拿了部分分原因是时间不够还有一个理解偏差。我当时看到“最多三把钥匙”后下意识认为必须集齐所有钥匙才能走到终点于是把终点判断写成了“到达E并且state等于7”。结果写完后测试样例时发现有一条最短路径明明不需要经过某把钥匙却被我拦住了。我最后把判断改成了只要到达E就输出步数才让逻辑正确。回头想题目描述里说的是“可以打开对应门”并不是“必须打开所有门”。这说明读题时不能自我加戏特别是BFS的终止条件一定要严格按题目要求来。如果题目真的要求集齐钥匙那state (1 3) - 1的判断自然没错但如果没有这个要求加上去就是画蛇添足。5. 选择填空复盘机器学习与概率统计5.1 一道几何分布的概率题选择题里有一道很基础的概率题连续抛一枚公平硬币直到第一次出现正面就停止问平均需要抛多少次硬币。这是典型的几何分布期望等于1/p。正面概率p0.5所以期望次数是2。这类题表面简单但容易在变形上出错。比如如果问“至少抛10次还没有出现正面的概率”那其实是前10次都是反面概率是(1/2)^10。如果题目改成“出现连续两次正面就停止”期望就不是2了而是用期望方程求解答案是6。考场上一旦遇到这种变形直接套几何分布公式会掉坑所以在复盘时我习惯把变式也一起想清楚。5.2 机器学习基本概念过拟合与特征缩放选择题里还有几道机器学习基础题。比如“下列哪些方法可以缓解过拟合”选项里有正则化、增加训练数据、降低模型复杂度、交叉验证、dropout。交叉验证通常用来评估模型效果并不能本身减少过拟合它只是让你更准确地知道模型在新数据上的表现。真正干预模型复杂度的手段是正则化、简化模型、数据增强、早停等。如果对这种区别不清楚很容易多选错选。还有一道特征缩放的题问为什么要对特征做标准化。答案是为了让不同量纲的特征在梯度下降时收敛得更快防止某些数值范围大的特征主导距离计算。这和归一化的目的要区分开归一化是缩放到[0,1]标准化是调整为均值0方差1。两者都服务于同一类目的但适用场景稍有差异。5.3 我的丢分点数据泄漏和随机森林有两道题我印象很深都是那种“以为自己会但选项里埋着概念陷阱”的题。一道是数据泄漏。题目给了四句话其中一句是“先对整个数据集做标准化再划分训练集和测试集”。这句话看起来很正常实际上已经引入了数据泄漏因为测试集的统计信息在训练前就被模型间接看到了。正确的做法是先划分训练集和测试集再单独对训练集拟合标准化参数然后用同样的参数转换测试集。另一道是随机森林的随机性体现在哪些地方。我当时选了“样本随机”和“特征随机”但漏了“决策树随机选择分裂点时的随机性”。严格来说随机森林的随机性主要就是样本有放回抽样和特征子集随机选择我也许是对“分裂点随机”这个说法过于敏感导致犹豫后选错。这种概念题没有捷径只能靠平时多抠细节。5.4 算法岗笔试不等于纯算法题这次笔试给我的一个重要提醒是算法岗的笔试并不只有代码题机器学习、概率统计、线性代数这些基础理论同样占不少分值。如果只刷LeetCode而没有系统复习机器学习基础选择题部分会非常吃亏。我以前总觉得选择题都是送分题但实际操作中很多概念题喜欢把“相似但不相同”的说法放在一起比如“交叉验证缓解过拟合”这种错误选项。准备阶段最好能定期过一遍经典教材的笔记把概念之间的边界理清楚而不是只看结论。6. 现场时间分配与踩坑记录6.1 一张时间分配表很多人看到在线笔试只有一个计时器就以为必须按题目顺序做。实际上所有题目的提交入口都在同一个页面完全可以自己安排顺序。我这次的时间分配大致如下时间段做的事情状态0-15分钟浏览全部题目记录模型和做题顺序比较从容15-40分钟完成T1通过全部测试点顺利40-65分钟完成T2但陷入初始化问题有些急躁65-90分钟修复T2开始T3时间仍够90-110分钟提交T3部分通过继续思考紧张110-120分钟快速检查选择题最后提交T3仓促从这张表能看出前两题顺的话第三题本来是有充足时间写完的。但我在T2的初始化上纠结了很久导致T3没有足够时间调试。这也是我复盘时最想改进的一点。6.2 在线评测的输入输出陷阱在线笔试环境最容易被忽略的问题是输入输出。有些题目有多组测试数据需要while (cin n)循环读取直到文件结束。如果只读一次就只能通过第一组样例。我当时T1的输入只有一组没遇到这个问题但以前在其他模拟笔试里吃过亏所以看见“多组输入”这几个字会格外小心。还有输出格式多了一个空格、少了一个换行都可能直接判WA。尤其是输出多个数字的题比如T1输出最大重叠数和对应时刻一定得检查顺序。建议在本地也建立一个跟在线系统一致的测试习惯写完代码先对照样例输出再提交。另外在线编辑器没有代码格式化也不会有“括号不匹配”的即时提示。平时在本地IDE里写久了很容易写出大括号忘记闭合的代码交上去才发现编译错误。现在每次写完我都会手动数一遍括号或者先在本地跑通再复制到系统里。6.3 心态管理卡题超过20分钟必须止损这次笔试让我最深刻的教训不是算法不会而是不会取舍。T2的初始化问题其实很小我却在上面花了将近20分钟明知道还有一道更难的T3等着却放不下。如果当时先停一下把T2的暴力版本提交上去拿部分分然后立刻转战T3很可能两道题都能得分而不是T3只做了一半。后续准备中我开始给自己定一个规则单题卡壳超过20分钟先写一版确定能过的代码并提交能拿多少分是多少分再考虑继续优化。尤其是线上笔试稳定比完美更重要。7. 这次笔试沉淀下来的方法7.1 把经典题型训练成条件反射算法岗笔试的题目看似五花八门但内核大多是经典模型。区间处理问题一定是排序加扫描线字符串最小编辑代价一定是动态规划网格图求最短步数一定是BFS看到“第K大”大概率是堆或二分看到状态数量很小的集合就要想到状态压缩。我现在的习惯是每做完一道题在题解旁边用一句话总结“什么特征对应什么模型”。比如“出现多个区间求重叠峰值 → 扫描线出现多把钥匙小集合 → BFS 位压缩”。这样刷题多了以后看到题目描述就能在几秒内判断出方向而不是在考场上临时从零推导。7.2 复盘比刷题数量更重要考完当天晚上我把三道编程题都用最合适的解法重新写了一遍然后对比现场代码总结出错点。这个过程比刷三道新题更有价值因为错误往往不是知识盲区而是习惯问题。我给自己建了一份错题卡内容包括扫描线同时间开始事件优先排序DP初始化要根据操作代价逐个赋值不能直接memset 0BFS状态是否包含第三维要由关键限制条件决定输出多个数字时先对照样例确认顺序。这些东西写下来之后后续再遇到类似题我会特意先检查这些位置节省了不少时间。7.3 给准备算法岗笔试的同学一些实操建议如果离笔试还有两三周我建议多安排几次完整模拟严格按真实考试的时长和题目结构来做。模拟时不要只挑熟悉的题做要逼自己从零开始读题、建模、写码、调试完整经历一次“从看懂到提交”的过程。实战训练时还要练习读题速度。这次三道编程题里有两道都有自定义的“闭区间包含端点”和“不强制收集全部钥匙”这类细节。很多人不是不会做而是读题太粗糙把题做成了另一道题。所以我在模拟时会刻意把题目里的关键限制用笔圈出来比如“包含端点”“代价不同”“最多三把钥匙”再开始思考算法。另外不要忽视选择题里的基础概念。每天抽出半小时过一遍机器学习常见的面试题比临考前突击有用得多。特别是数据泄漏、过拟合、正则化、贝叶斯公式这些高频考点要做到能分辨相近说法。考完那天晚上我把三道题重新做了一遍把现场所有写错的细节都改了过来。后来我越来越觉得算法岗笔试考察的并不是你背了多少模板而是短时间内把陌生问题抽象成已知模型的速度和准确性。这次笔试暴露出来的三个问题一是对经典模型不够敏感二是初始化这种细节重视不够三是时间管理太理想化。如果你也在准备算法岗笔试不要只沉浸在刷题的舒适区按时完整地做几次模拟题把“会做”变成“稳做”至少能让现场少一半翻车概率。 
长河君 · 2026/10/14 17:50:05 · 阅读 1.2k 算法岗在线笔试复盘：扫描线、编辑距离与状态压缩BFS实战解析
2020年8月8日下午我参加了一场在线算法岗笔试。这场笔试整体难度不算温和题量也不小三个小时里我经历了“前面顺风顺水、中间卡成狗、最后仓促提交”的典型过程。考完当天晚上我把每道题重新梳理了一遍今天写这篇算法岗笔试复盘把题目模型、解题思路、考场上踩过的坑以及后续准备方法一起整理出来。如果你也在准备算法类岗位的在线笔试这篇文章应该能帮你少走一点弯路。笔试整体并不是堆模板而是把常见的算法模型包在业务场景里考察的是“识别模型”和“稳定输出”的能力。比如第一题是服务器任务区间本质是区间重叠第二题是字符串编辑代价本质是动态规划第三题是钥匙迷宫本质是状态压缩BFS。如果你能快速看穿这层外衣剩下就是熟练度的问题。1. 笔试基本信息与整体策略1.1 在线笔试的题型与时间安排整场笔试共120分钟前60分钟做10道选择题和填空题后60分钟做3道编程题。不过实际页面上所有题目同时可见可以自己分配时间。我的策略是快速扫一遍所有题目先判断哪部分性价比高而不是傻傻地从选择题第一题开始按顺序往下做。选择题集中在机器学习基础、概率统计和少量数据结构概念上编程题则是比较典型的算法实现。在线评测环境自带一个简易编辑器没有本地IDE的自动补全写完代码必须手动提交测试一旦有语法错误或者边界条件问题窗口期就会很快被消耗掉。这个环境本身就是一个隐藏考点如果平时只在本地IDE里跑题、依赖编译器的错误提示到这种环境里会非常难受。1.2 拿到卷子后的前15分钟决策我没有急着开始敲代码而是先把3道编程题全部读了一遍并在草稿纸上记下每道题的模型和预估复杂度。第一题是给出若干任务的开始和结束时间求同时运行的最大任务数以及对应时间点。这明显是区间重叠问题排序加扫描线就能解决。第二题是字符串变换给出三种操作的代价问最小总代价这是带权编辑距离标准二维DP。第三题是迷宫中有几把钥匙和几扇门需要拿钥匙开门到达终点这是典型的BFS加状态压缩。三题难度递进我把做题顺序定为T1、T2、T3目标很明确先把稳的分牢牢抓住再冲难题。不少同学拿到题目就直接沉浸在第一题里结果在边界条件上反复折腾后面时间不够用。提前花15分钟看清全貌看起来是“浪费时间”实际上是在给后面的自己争取时间。2. 第一题区间重叠峰值计算2.1 题目复述与示例题目大意是系统里有若干定时任务每个任务用一个区间表示运行时间段。假设区间端点也算运行时间需要算出任意时刻最多有多少个任务同时在运行并输出这个最大数量以及最早达到该数量的时刻。举个具体的输入例子4 1 3 2 5 3 6 4 7任务区间分别是[1,3]、[2,5]、[3,6]、[4,7]。在时间3前三个任务都在运行数量是3在时间4后三个任务也在运行数量也是3。题目要求最早达到最大重叠的时刻所以答案是“3 3”。当时我一看这题就知道是经典扫描线但它在题意上加了一个很容易忽略的约束区间是闭区间开始和结束在同一时刻也算重叠。这个小小的定义差异直接决定了排序规则怎么写。2.2 为什么用排序加扫描线而不是双重循环最朴素的做法是枚举每个时间点检查所有区间是否包含它。如果时间范围很大比如最大到10^9根本不可能开数组。另一种朴素做法是每两个区间两两判断重叠再统计重叠次数但复杂度是O(n^2)题目数据量一上来就会超时。扫描线的核心思想是把区间拆成事件区间开始时把当前重叠数加1区间结束时把当前重叠数减1。把所有事件按时间排序后依次处理事件过程中维护重叠数的峰值。这样时间复杂度是O(n log n)主要花在排序上空间复杂度O(n)是这类问题的标准解法。难点在于事件排序的细节。因为区间是闭区间同一个时间点上可能既有任务结束又有任务开始。比如[1,2]和[2,3]在时间2时两个任务同时存在重叠数应该是2。如果排序时结束事件排在开始事件前面扫描到时间2时会先把重叠数减1再加1峰值就漏掉了。所以必须保证同一时刻开始时事件先处理。2.3 参考代码与边界说明我当时写了一份C代码核心逻辑大概是下面这样#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorpairint, int events; for (int i 0; i n; i) { int l, r; cin l r; events.push_back({l, 0}); // 0表示开始事件 events.push_back({r, 1}); // 1表示结束事件 } sort(events.begin(), events.end()); int cur 0, best 0, ansTime -1; for (auto e : events) { int t e.first; int type e.second; if (type 0) { cur; if (cur best) { best cur; ansTime t; } } else { --cur; } } cout best ansTime \n; return 0; }这里用pair排序pair会先比较时间再比较类型。因为开始事件type是0结束事件type是1所以同一时刻开始事件会排在结束事件前面正好符合闭区间重叠的定义。这个细节非常关键。如果题目改成开区间也就是端点不重叠那么只需要把结束事件排在开始事件前面或者在区间结束时刻处理为减1前先处理开始事件。很多区间题目喜欢在这一点上做文章所以读题时一定要先搞清楚区间开闭。2.4 我在现场踩的坑这题我一开始写得很顺但提交后有一组用例没过。排查后发现不是算法问题而是输出格式的锅。题目要求先输出最大数量再输出最早时刻中间用空格分隔。我写成了cout ansTime best把两个值反了本地样例恰好又看不出问题因为数量和时间值不一样时才明显。这种低级错误很伤士气之后我遇到输出两个以上数值的题目都会特意对照样例检查一遍顺序。另一个坑是我最初在结束事件时也尝试更新一下最大值结果虽然不会报错但ansTime可能被指向错误的时刻。仔细想了一下最大值只可能由一个新的开始事件触发所以只需要在事件类型为开始时更新峰值和对应时间。这样不仅逻辑清晰也能保证“最早达到最大重叠的时刻”是准确的。3. 第二题带权编辑距离的动态规划3.1 题设与三种操作代价第二题的字符串变换问题本质上是一个带权编辑距离。题目给出两个字符串只允许对第一个字符串做三种操作插入任意一个字符代价为1删除任意一个字符代价为2替换任意一个字符为其他字符代价为3。问把字符串a变成字符串b的最小总代价。例如a为catb为cut一种方式是直接把a中的a替换成u代价3。虽然也可以先删除a再插入u但总代价是213两者一样所以答案是3。如果替换代价不是3而是5那么明显删除加插入更便宜。这里的关键是操作成本不对称不能直接用经典编辑距离的无权版本去套。现场我第一反应是“不就是编辑距离吗”差点按照经典转移直接写。还好多看了一眼代价表意识到删除代价和插入代价不同初始化时不能一律用1后续转移也要区分。题目故意把三个代价设置得不一样就是为了拦住那些只会背模板的人。3.2 状态定义与转移方程设dp[i][j]表示字符串a的前i个字符变成字符串b的前j个字符所需要的最小代价。这里a和b的下标都从1开始计数代码中取字符时要记得下标减1。对于当前状态dp[i][j]可以从三种前置状态转移过来从dp[i-1][j]转移表示删掉a的第i个字符然后继续把a的前i-1个字符变成b的前j个字符代价是dp[i-1][j] 删除代价2。从dp[i][j-1]转移表示先让a的前i个字符变成b的前j-1个字符再往末尾插入b的第j个字符代价是dp[i][j-1] 插入代价1。从dp[i-1][j-1]转移表示看a的第i个字符和b的第j个字符是否相等如果相等不需要额外操作代价是dp[i-1][j-1]如果不相等可以把a的第i个字符替换成b的第j个字符代价是dp[i-1][j-1] 替换代价3。三者取最小值即可。注意这里之所以有“插入”和“删除”两个方向是因为“把a变成b”的过程中a里多余的字符会被删掉b里需要但a没有的字符会被插入。理解这个方向后初始化就非常自然了dp[0][0] 0空字符串变成空字符串不需要任何操作。dp[i][0]表示a的前i个字符全部删掉变成空字符串代价为i * 2。dp[0][j]表示从空字符串变成b的前j个字符需要全部插入代价为j * 1。很多人在初始化时想当然认为dp[i][0] idp[0][j] j在有不对称代价的题目里直接就错了。我现场也一度把删除和插入的代价弄反导致所有测试点输出偏大。3.3 参考代码与滚动数组优化下面的实现直接使用二维数组思路最直观#include bits/stdc.h using namespace std; int main() { string a, b; cin a b; int n a.size(), m b.size(); int insCost 1, delCost 2, repCost 3; vectorvectorint dp(n 1, vectorint(m 1, 1e9)); dp[0][0] 0; for (int i 1; i n; i) dp[i][0] i * delCost; for (int j 1; j m; j) dp[0][j] j * insCost; for (int i 1; i n; i) { for (int j 1; j m; j) { int val min(dp[i - 1][j] delCost, dp[i][j - 1] insCost); if (a[i - 1] b[j - 1]) { val min(val, dp[i - 1][j - 1]); } else { val min(val, dp[i - 1][j - 1] repCost); } dp[i][j] val; } } cout dp[n][m] \n; return 0; }如果字符串长度到几千甚至上万二维数组可能内存超标可以优化成一维滚动数组。因为dp[i][j]只依赖当前行左边的dp[i][j-1]、上一行的dp[i-1][j]和左上角的dp[i-1][j-1]。滚动数组需要保存上一行当前列的值和左上角值写起来容易出错。在线做题如果内存足够我建议先写二维版把正确性保住再去想优化不要一上来就炫技能。3.4 这题真正的隐藏扣分点编辑距离相关题目尤其喜欢考边界一个字符串为空。不少解法把dp数组初始化为0然后从i1,j1开始转移结果空串的用例全部出错。我在现场一开始也踩了这个坑因为样例中两个字符串都不为空看起来很正确但提交后包含空串的测试点立刻暴露问题。另一个容易被忽略的是“替换代价可能大于删除加插入”。比如替换代价是10删除代价是2插入代价是1那么把字符x替换成y的最优操作往往不是替换而是先删除x再插入y总代价3远小于10。好在状态转移方程已经自动考虑了这种情况只要把替换代价写进转移公式DP会自己选择更便宜的路径。只要初始化正确这个隐藏点不会造成问题。4. 第三题钥匙迷宫的最短路问题4.1 题设与状态压缩思路第三题是一个网格迷宫题N行M列格子上有起点S、终点E、障碍#、空地.以及最多3把钥匙和3扇门。钥匙编号分别是1、2、3门分别对应A、B、C。只有拿到对应钥匙才能通过门比如没有钥匙1时遇到门A不能走。问从起点到终点的最少步数如果无法到达输出-1。普通BFS的特点是每个格子第一次被访问时到达它的步数就是最短步数。但在这个问题里同一个格子可能会被访问多次因为第一次到达时可能没有某把钥匙第二次到达时有了钥匙能继续走的路就完全不同了。这时候必须把“当前拥有哪些钥匙”也纳入状态于是状态就变成了(x, y, mask)其中mask是一个最多3位的二进制数表示目前拥有了哪几把钥匙。比如mask3二进制是011表示已经拿到了钥匙1和钥匙2还没拿钥匙3。三把钥匙的所有组合一共是2^38种所以访问标记数组可以开成vis[N][M][8]空间非常小。这就是状态压缩BFS的典型套路。4.2 为什么必须用BFS而不是DFS看到求最少步数第一反应就应该是BFS因为BFS天然按层扩展第一次到达目标状态的步数一定是最短步数。DFS也能找到一条路径但无法保证最短除非用迭代加深或者记录全局最优并剪枝那样复杂度通常会高很多。在这个题里每一步的移动代价都是1普通队列就能完成BFS。不需要优先队列也不需要Dijkstra。这也让问题简化了很多关键就在于状态的定义和转移要写对。4.3 参考代码与关键细节这里是我的实现思路#include bits/stdc.h using namespace std; const int dx[4] {0, 0, 1, -1}; const int dy[4] {1, -1, 0, 0}; struct Node { int x, y, state, step; }; int main() { int n, m; cin n m; vectorstring grid(n); int sx 0, sy 0, ex 0, ey 0; for (int i 0; i n; i) { cin grid[i]; for (int j 0; j m; j) { if (grid[i][j] S) { sx i; sy j; } if (grid[i][j] E) { ex i; ey j; } } } bool vis[50][50][8] {false}; queueNode q; q.push({sx, sy, 0, 0}); vis[sx][sy][0] true; while (!q.empty()) { Node cur q.front(); q.pop(); if (cur.x ex cur.y ey) { cout cur.step \n; return 0; } for (int d 0; d 4; d) { int nx cur.x dx[d]; int ny cur.y dy[d]; if (nx 0 || nx n || ny 0 || ny m) continue; if (grid[nx][ny] #) continue; int ns cur.state; char c grid[nx][ny]; if (c 1 c 3) { ns | (1 (c - 1)); } if (c A c C) { int need c - A; if ((ns (1 need)) 0) continue; } if (!vis[nx][ny][ns]) { vis[nx][ny][ns] true; q.push({nx, ny, ns, cur.step 1}); } } } cout -1 \n; return 0; }这里有一个小坑当格子是钥匙时即使没听过它的编号进入格子后钥匙会自动被拾取所以走到有钥匙的格子后状态一定要更新。如果忘了更新state就会出现“明明踩到了钥匙却打不开门”的滑稽错误。另一个坑是门的判断要放在钥匙更新之后。如果当前格子里有钥匙同时这个格子也是一扇门这种设计在题目里不会出现但代码顺序如果写反可能会影响新状态的可达性。4.4 现场我在第三题上翻车的点这道题我只拿了部分分原因是时间不够还有一个理解偏差。我当时看到“最多三把钥匙”后下意识认为必须集齐所有钥匙才能走到终点于是把终点判断写成了“到达E并且state等于7”。结果写完后测试样例时发现有一条最短路径明明不需要经过某把钥匙却被我拦住了。我最后把判断改成了只要到达E就输出步数才让逻辑正确。回头想题目描述里说的是“可以打开对应门”并不是“必须打开所有门”。这说明读题时不能自我加戏特别是BFS的终止条件一定要严格按题目要求来。如果题目真的要求集齐钥匙那state (1 3) - 1的判断自然没错但如果没有这个要求加上去就是画蛇添足。5. 选择填空复盘机器学习与概率统计5.1 一道几何分布的概率题选择题里有一道很基础的概率题连续抛一枚公平硬币直到第一次出现正面就停止问平均需要抛多少次硬币。这是典型的几何分布期望等于1/p。正面概率p0.5所以期望次数是2。这类题表面简单但容易在变形上出错。比如如果问“至少抛10次还没有出现正面的概率”那其实是前10次都是反面概率是(1/2)^10。如果题目改成“出现连续两次正面就停止”期望就不是2了而是用期望方程求解答案是6。考场上一旦遇到这种变形直接套几何分布公式会掉坑所以在复盘时我习惯把变式也一起想清楚。5.2 机器学习基本概念过拟合与特征缩放选择题里还有几道机器学习基础题。比如“下列哪些方法可以缓解过拟合”选项里有正则化、增加训练数据、降低模型复杂度、交叉验证、dropout。交叉验证通常用来评估模型效果并不能本身减少过拟合它只是让你更准确地知道模型在新数据上的表现。真正干预模型复杂度的手段是正则化、简化模型、数据增强、早停等。如果对这种区别不清楚很容易多选错选。还有一道特征缩放的题问为什么要对特征做标准化。答案是为了让不同量纲的特征在梯度下降时收敛得更快防止某些数值范围大的特征主导距离计算。这和归一化的目的要区分开归一化是缩放到[0,1]标准化是调整为均值0方差1。两者都服务于同一类目的但适用场景稍有差异。5.3 我的丢分点数据泄漏和随机森林有两道题我印象很深都是那种“以为自己会但选项里埋着概念陷阱”的题。一道是数据泄漏。题目给了四句话其中一句是“先对整个数据集做标准化再划分训练集和测试集”。这句话看起来很正常实际上已经引入了数据泄漏因为测试集的统计信息在训练前就被模型间接看到了。正确的做法是先划分训练集和测试集再单独对训练集拟合标准化参数然后用同样的参数转换测试集。另一道是随机森林的随机性体现在哪些地方。我当时选了“样本随机”和“特征随机”但漏了“决策树随机选择分裂点时的随机性”。严格来说随机森林的随机性主要就是样本有放回抽样和特征子集随机选择我也许是对“分裂点随机”这个说法过于敏感导致犹豫后选错。这种概念题没有捷径只能靠平时多抠细节。5.4 算法岗笔试不等于纯算法题这次笔试给我的一个重要提醒是算法岗的笔试并不只有代码题机器学习、概率统计、线性代数这些基础理论同样占不少分值。如果只刷LeetCode而没有系统复习机器学习基础选择题部分会非常吃亏。我以前总觉得选择题都是送分题但实际操作中很多概念题喜欢把“相似但不相同”的说法放在一起比如“交叉验证缓解过拟合”这种错误选项。准备阶段最好能定期过一遍经典教材的笔记把概念之间的边界理清楚而不是只看结论。6. 现场时间分配与踩坑记录6.1 一张时间分配表很多人看到在线笔试只有一个计时器就以为必须按题目顺序做。实际上所有题目的提交入口都在同一个页面完全可以自己安排顺序。我这次的时间分配大致如下时间段做的事情状态0-15分钟浏览全部题目记录模型和做题顺序比较从容15-40分钟完成T1通过全部测试点顺利40-65分钟完成T2但陷入初始化问题有些急躁65-90分钟修复T2开始T3时间仍够90-110分钟提交T3部分通过继续思考紧张110-120分钟快速检查选择题最后提交T3仓促从这张表能看出前两题顺的话第三题本来是有充足时间写完的。但我在T2的初始化上纠结了很久导致T3没有足够时间调试。这也是我复盘时最想改进的一点。6.2 在线评测的输入输出陷阱在线笔试环境最容易被忽略的问题是输入输出。有些题目有多组测试数据需要while (cin n)循环读取直到文件结束。如果只读一次就只能通过第一组样例。我当时T1的输入只有一组没遇到这个问题但以前在其他模拟笔试里吃过亏所以看见“多组输入”这几个字会格外小心。还有输出格式多了一个空格、少了一个换行都可能直接判WA。尤其是输出多个数字的题比如T1输出最大重叠数和对应时刻一定得检查顺序。建议在本地也建立一个跟在线系统一致的测试习惯写完代码先对照样例输出再提交。另外在线编辑器没有代码格式化也不会有“括号不匹配”的即时提示。平时在本地IDE里写久了很容易写出大括号忘记闭合的代码交上去才发现编译错误。现在每次写完我都会手动数一遍括号或者先在本地跑通再复制到系统里。6.3 心态管理卡题超过20分钟必须止损这次笔试让我最深刻的教训不是算法不会而是不会取舍。T2的初始化问题其实很小我却在上面花了将近20分钟明知道还有一道更难的T3等着却放不下。如果当时先停一下把T2的暴力版本提交上去拿部分分然后立刻转战T3很可能两道题都能得分而不是T3只做了一半。后续准备中我开始给自己定一个规则单题卡壳超过20分钟先写一版确定能过的代码并提交能拿多少分是多少分再考虑继续优化。尤其是线上笔试稳定比完美更重要。7. 这次笔试沉淀下来的方法7.1 把经典题型训练成条件反射算法岗笔试的题目看似五花八门但内核大多是经典模型。区间处理问题一定是排序加扫描线字符串最小编辑代价一定是动态规划网格图求最短步数一定是BFS看到“第K大”大概率是堆或二分看到状态数量很小的集合就要想到状态压缩。我现在的习惯是每做完一道题在题解旁边用一句话总结“什么特征对应什么模型”。比如“出现多个区间求重叠峰值 → 扫描线出现多把钥匙小集合 → BFS 位压缩”。这样刷题多了以后看到题目描述就能在几秒内判断出方向而不是在考场上临时从零推导。7.2 复盘比刷题数量更重要考完当天晚上我把三道编程题都用最合适的解法重新写了一遍然后对比现场代码总结出错点。这个过程比刷三道新题更有价值因为错误往往不是知识盲区而是习惯问题。我给自己建了一份错题卡内容包括扫描线同时间开始事件优先排序DP初始化要根据操作代价逐个赋值不能直接memset 0BFS状态是否包含第三维要由关键限制条件决定输出多个数字时先对照样例确认顺序。这些东西写下来之后后续再遇到类似题我会特意先检查这些位置节省了不少时间。7.3 给准备算法岗笔试的同学一些实操建议如果离笔试还有两三周我建议多安排几次完整模拟严格按真实考试的时长和题目结构来做。模拟时不要只挑熟悉的题做要逼自己从零开始读题、建模、写码、调试完整经历一次“从看懂到提交”的过程。实战训练时还要练习读题速度。这次三道编程题里有两道都有自定义的“闭区间包含端点”和“不强制收集全部钥匙”这类细节。很多人不是不会做而是读题太粗糙把题做成了另一道题。所以我在模拟时会刻意把题目里的关键限制用笔圈出来比如“包含端点”“代价不同”“最多三把钥匙”再开始思考算法。另外不要忽视选择题里的基础概念。每天抽出半小时过一遍机器学习常见的面试题比临考前突击有用得多。特别是数据泄漏、过拟合、正则化、贝叶斯公式这些高频考点要做到能分辨相近说法。考完那天晚上我把三道题重新做了一遍把现场所有写错的细节都改了过来。后来我越来越觉得算法岗笔试考察的并不是你背了多少模板而是短时间内把陌生问题抽象成已知模型的速度和准确性。这次笔试暴露出来的三个问题一是对经典模型不够敏感二是初始化这种细节重视不够三是时间管理太理想化。如果你也在准备算法岗笔试不要只沉浸在刷题的舒适区按时完整地做几次模拟题把“会做”变成“稳做”至少能让现场少一半翻车概率。