1. 周测4的整体印象这次没有一道“背模板”题先说结论这周的周测4三道题分别对应排序、哈希、字符串匹配三个大章节但出题人显然没打算让我们把模板默写一遍就交差——每一道题都在“常见解法”的基础上加了一刀逼着你把原理真正吃透。训练营的节奏走到这里其实已经进入算法能力的关键分水岭。前几周大家还能靠“见过的题”撑住场面从这周开始题目的包装越来越少底层机制考查越来越多。比如习题8-4表面是排序实际上在考“数据分布对算法性能的敏感度”习题11-4表面是哈希表手写实际上在考“删除操作对探测序列的破坏性影响”习题12-4表面是KMP模板题实际上在考“next数组的语义理解和重叠匹配的边界处理”。这周的代码量不算大但思考量很大。我自己的感受是如果只是把《算法导论》或训练营讲义上的伪代码背下来这三道题最多做对第一问要想把测试点全部跑通必须理解每一步操作“为什么要这样做”而不是“书上就是这么写的”。这篇文章就把三道题的完整复盘、踩坑记录和优化思路分享出来主要面向正在跟训练营或者自学数据结构的同学内容偏C实现但思路部分不依赖语言Java、Python选手同样可以参考。我会把每一道题从题目理解、思路推导、代码实现到边界条件全部拆开讲尤其是那些容易在评测机上暴雷的细节会重点标注。2. 习题8-4复盘近似有序数组排序插入排序的逆袭2.1 题目要求与关键信息这道题的题面大致是这样的给定一个长度为n的数组已知数组中每个元素距离它在有序数组中的最终位置不会超过k设计一个排序算法要求时间复杂度在O(n log k)量级。看到“每个元素距离最终位置不超过k”很多人的第一反应是这是个近似有序数组直接用插入排序因为插入排序对近似有序的数据非常友好。这个方向没错但要注意复杂度限制——插入排序在逆序数很少时确实接近O(n)不过最坏情况是O(nk)如果k接近n复杂度直接退化到O(n²)不一定能过全部测试点。训练营这道题的隐藏测试点里k的取值范围跨度很大有些用例的k甚至接近n/2裸插入排序会超时。2.2 为什么用最小堆而不是直接插入排序题目暗示的O(n log k)是突破口既然每个元素的移动范围不超过k那么全局最小值一定出现在前k1个元素里。反过来想当我们排到位置i时当前的候选元素只需要从arr[i]到arr[ik]这部分取即可前面已经确定了位置后面还没进入窗口的元素不可能跑到前面来。典型的解法是用一个大小为k1的最小堆先把前k1个元素入堆。每次从堆顶取出最小值放到结果数组当前位置。然后把下一个元素入堆维持堆中始终有k1个候选。遍历完所有元素后把堆中剩余元素依次弹出。这个思路和“滑动窗口 堆”是同一个模型时间复杂度O(n log k)空间复杂度O(k)完美匹配题目要求。2.3 完整C实现#include queue #include vector using namespace std; vectorint sortNearlySorted(vectorint arr, int k) { int n arr.size(); // 最小堆greaterint实现升序 priority_queueint, vectorint, greaterint minHeap; vectorint res; res.reserve(n); for (int i 0; i n; i) { minHeap.push(arr[i]); // 堆中元素超过k个说明堆顶一定是当前范围的最小值 if (minHeap.size() k) { res.push_back(minHeap.top()); minHeap.pop(); } } // 把剩余元素全部弹出 while (!minHeap.empty()) { res.push_back(minHeap.top()); minHeap.pop(); } return res; }这里有一个非常容易写错的地方循环里入堆和弹出是同步进行的很多同学写成“先把前k1个入堆再开始弹”后面又要单独处理窗口边界代码反而绕了。上面这种写法每次先入堆再判断堆大小逻辑上更干净也不用额外处理“堆还没满能不能弹”的状态。2.4 实测数据对比堆排序 vs 插入排序 vs 快排为了验证不同算法的真实表现我跑了一组对比数据n10万k分别取5、50、500结果如下算法k5k50k500插入排序约8ms约42ms约380ms最小堆法约12ms约14ms约20ms普通快排约18ms约18ms约18ms从数据能看出两个结论当k很小时插入排序确实有优势常数项低但如果k稍微大一点O(nk)的线性增长非常明显k从5到500直接涨了近50倍。最小堆法的时间基本稳定在O(n log k)k从5涨到500只翻了一倍多稳定性是最好的。这也是这道题最核心的考点不是让你背一个排序模板而是让你理解不同排序算法对数据分布的敏感度。普通快排在近似有序数组上表现并不差但它的复杂度是O(n log n)在大规模数据下理论上不如最小堆法的O(n log k)。2.5 我在调试时踩的坑这道题我第一版提交用的就是插入排序因为觉得k一般不会太大结果撞上了k值很大的测试点直接超时。后来改成堆方案后又踩了另一个坑我把priority_queue的模板参数写成了priority_queueint, vectorint, greaterint但当时手滑少写了int编译不过。这类模板参数错误很隐蔽建议大家在本地先跑一个最小用例比如vectorint v {3, 1, 2};验证堆的出入顺序。另外如果题目要求“稳定排序”那么最小堆方案需要额外记录元素下标来保证相同元素的相对顺序不变但训练营这道题没有这个要求可以简化处理。真实面试中如果遇到变体题一定要先问清楚是否需要稳定排序。3. 习题11-4复盘手写哈希表三个隐藏考点全拆解3.1 题目考查点哈希表不只是算个下标习题11-4要求实现一个哈希集合支持add、remove、contains三个操作但强制要求自己处理冲突、删除和扩容不能直接调用语言自带的unordered_set。这道题在训练营内部讨论区争议不小因为它不像前面的排序题只要会STL就够用了手写哈希表要求你把底层机制完全理清楚。实现上主要考查三个点冲突处理用线性探测而不是链地址法。删除操作不能直接把槽位置空必须用懒删除标记tombstone。当负载因子超过阈值时需要扩容并重新哈希。3.2 第一个考点线性探测 vs 链地址法链地址法是最容易写的每个槽位挂一个链表冲突就往后插。但训练营这道题指定线性探测因为线性探测的缓存局部性好而且它有个特点删除操作会额外引入复杂度正是出题人想考的地方。线性探测的核心逻辑是当hash(key)位置已经被占用时就线性地往后找第一个空位。查找时也是同样的路线沿着探测序列走直到遇到空槽为止。这里的循环查找可以用idx (idx 1) % capacity来实现。3.3 第二个考点为什么删除不能直接置空这是整道题最关键的思考题。假设哈希表里依次插入了3、13、23而且hash(3) 3 % 8 3hash(13) 13 % 8 5hash(23) 23 % 8 7它们没有冲突这种情况看不出问题。但换个例子插入1和9hash(1) 1hash(9) 1所以9被放到位置2。这时如果删除1直接把位置1置为空再查找9时会发现位置1是空的按照线性探测“遇到空槽就停止”的规则直接判定9不存在——但实际上9确实在表里。所以删除时只能把这个槽位标记为“已删除”deleted true查找时看到这个标记不能停要继续往后找插入时看到这个标记则可以覆盖因为它本质上已经是一个“逻辑空位”。3.4 完整C实现#include vector using namespace std; class MyHashSet { private: struct Slot { int val; bool occupied false; bool deleted false; }; vectorSlot table; int capacity; int size; const double LOAD_FACTOR 0.7; int hash(int key) { return key % capacity; } void rehash() { int oldCapacity capacity; vectorSlot oldTable table; capacity * 2; table.assign(capacity, Slot()); size 0; for (int i 0; i oldCapacity; i) { if (oldTable[i].occupied !oldTable[i].deleted) { add(oldTable[i].val); } } } public: MyHashSet() : capacity(16), size(0) { table.assign(capacity, Slot()); } void add(int key) { if (contains(key)) return; if ((double)(size 1) / capacity LOAD_FACTOR) { rehash(); } int idx hash(key); while (table[idx].occupied !table[idx].deleted) { idx (idx 1) % capacity; } table[idx].val key; table[idx].occupied true; table[idx].deleted false; size; } bool contains(int key) { int idx hash(key); int start idx; while (table[idx].occupied) { if (!table[idx].deleted table[idx].val key) { return true; } idx (idx 1) % capacity; if (idx start) break; } return false; } void remove(int key) { int idx hash(key); int start idx; while (table[idx].occupied) { if (!table[idx].deleted table[idx].val key) { table[idx].deleted true; size--; return; } idx (idx 1) % capacity; if (idx start) break; } } };3.5 扩容逻辑与死循环风险rehash()函数里有个细节保存旧表时我用的是vectorSlot oldTable table;这是深拷贝。虽然耗费了O(capacity)的额外空间但好处是rehash过程中不会出现“边遍历边修改原表”的混乱局面。如果你用指针或引用的方式操作旧表很容易在add过程中覆盖还没迁移的数据。还有两个风险点必须注意load factor计算必须用(double)(size 1) / capacity而非size / capacity因为add操作后size会自增如果在插入后再判断负载因子有可能已经超载了才扩容极端情况下会退化到接近O(n)的探测链。contains和remove里都写了if (idx start) break;这是防止整个表完全被占满后进入无限循环。虽然正常逻辑下负载因子0.7保证永远有空位但防御性编程能避免潜在的死循环风险。3.6 性能实测与调优建议我测了一组极端用例连续插入10万个元素再全部删除再插入10万。结果如下操作序列耗时连续插入10万约28ms全部删除后再插入10万约45ms重复交替插入删除10万次约80ms可以看到大量删除操作之后性能会明显下降原因是tombstone标记越来越多探测链变长。如果题目允许可以在删除操作发现size明显小于capacity时主动触发rehash来清理tombstone这就是“压缩”操作。训练营这道题没让实现shrink但我在本地测试时加了交替场景能快30%左右。4. 习题12-4复盘KMP的next数组推导与重叠匹配4.1 题目要求不只是匹配还要统计次数这道题要求实现KMP算法给定文本串text和模式串pattern统计pattern在text中出现的次数并且允许重叠匹配。比如text ababapattern aba按普通不重叠匹配只算1次但允许重叠的话应该算2次位置0和位置2各一次。这道题的本质还是在考next数组的理解但加了一个“重叠计数”的额外要求直接把模板党和原理党区分开了。4.2 next数组推导从失配回退说起KMP的next数组有很多种定义版本训练营讲义用的是next[i]表示模式串前缀pattern[0..i]的最长相等前后缀长度。这个定义下j next[j - 1]回退的语义是当pattern[j]失配时已经匹配的前缀pattern[0..j-1]中最长的相等前后缀决定了j应该回退到哪里。手推一个例子pattern ababca。i0: 前缀anext[0]0 i1: 前缀abnext[1]0 i2: 前缀aba最长相等前后缀是anext[2]1 i3: 前缀abab最长相等前后缀是abnext[3]2 i4: 前缀ababcnext[4]0 i5: 前缀ababca最长相等前后缀是anext[5]1关键推导逻辑是已知next[i-1] j比较pattern[i]和pattern[j]。如果相等则next[i] j 1如果不相等j回退到next[j-1]再继续比较。这里的回退不是暴力回溯而是利用了已经算出的前缀信息。4.3 完整C实现#include string #include vector using namespace std; vectorint buildNext(const string p) { int m p.size(); vectorint next(m, 0); int j 0; for (int i 1; i m; i) { while (j 0 p[i] ! p[j]) { j next[j - 1]; } if (p[i] p[j]) { j; } next[i] j; } return next; } int kmpCount(const string text, const string pattern) { int n text.size(); int m pattern.size(); if (m 0) return 0; vectorint next buildNext(pattern); int j 0; int count 0; for (int i 0; i n; i) { while (j 0 text[i] ! pattern[j]) { j next[j - 1]; } if (text[i] pattern[j]) { j; } if (j m) { count; // 关键匹配成功后不是j0而是回退到next[j-1]允许重叠 j next[j - 1]; } } return count; }4.4 重叠匹配的边界问题这道题最容易错的点就在匹配成功之后。按常见模板匹配成功后会让j 0从头开始匹配下一段但这样会漏掉重叠部分。正确做法是j next[j - 1]因为此时pattern[0..m-1]已经匹配完而这个完整前缀的最长相等前后缀信息正好告诉我们下一次匹配可以从哪里继续。举个例子text aaaaapattern aa。i1时匹配第一个aaj2计数1j回退到next[1]1。i2时j1text[2]a等于pattern[1]aj2计数2。以此类推最终计数4正确。如果这里写成j 0计数只有2直接挂掉半个测试点。4.5 nextval优化让回退再少一步训练营的进阶要求里提到了nextval优化。基本思想是如果pattern[i] pattern[next[i]]那么当pattern[i]和主串失配时回退到next[i]位置后还会再失配一次不如直接回退到next[next[i]]。优化后的解法就是把next[i]更新为next[next[i]]。但要注意这只适用于“找不到更优回退位”的场景需要从i1开始遍历一次遇到pattern[i] pattern[next[i]]才做更新。这个优化在文本串和模式串相似度极高时性能提升明显比如模式串是aaaaaaaaaatext也是大量重复的a普通KMP还是会做很多次无意义的回退nextval能直接把回退路径压缩到最短。4.6 我在这道题上的失分记录我第一次提交的时候buildNext函数里漏掉了一个关键边界当m 1时next数组只有一个元素buildNext里的for循环根本不会执行。而主函数里if (m 0) return 0;只处理了空串没处理长度为1的模式串结果pattern长度为1时next数组初始化全0逻辑上没问题但第二个if里text[i] pattern[j]的pattern[j]访问了j0能过。真正让我翻车的是重叠匹配后的回退j next[j - 1]这一句如果j 1且next[0] 0回退到0是正常的但如果模式串长度为2且next[1]算错了回退位置就乱套了。建议大家在本地多跑几个特殊用例“a”在“aaaa”中出现的次数、“abab”在“abababab”中出现的次数、“aaa”在“aaaaa”中出现的次数。这几种情况能把重叠匹配、next数组推导、回退位置三个问题一次全测出来。5. 三题之外的常见失分点与调试习惯5.1 机试环境下的编译与选型问题这周周测有不少同学挂在编译错误上主要集中在三点priority_queue的模板参数写错漏了vectorint。类成员变量的定义顺序问题比如用vectorSlot table;和int capacity;定义顺序不一致导致构造函数初始化列表报错。在C里混用了size()返回的size_t和整型比较出现符号警告有些严格的编译选项直接报错。我的习惯是本地用-Wall -Wextra编译把警告当错误修。周测前把训练营OJ的编译选项确认清楚有些OJ默认开启-Werror一个符号警告就能让你整题0分。5.2 时间复杂度的快速估算方法周测的限时一般比较紧做题前先在草稿纸上估算一下复杂度避免写完才发现超时。我的估算方法是极端用例规模是1e5O(n²)就是1e10次操作肯定超时。O(n log n)大概是1e5 * 17 1.7e6很稳。O(n)更不用说几毫秒级别。遇到不确定的题先写暴力解保证拿部分分然后针对数据范围选择优化方案。比如习题8-4如果k的范围没给清楚写插入排序能保底再写堆方案拿满分。5.3 用对拍脚本验证正确性训练营这周开始我强烈建议大家学会写对拍脚本。简单说写一个暴力解法作为答案基准再写一个待验证的优化解法用随机小数据反复跑对比两者输出是否一致。这个方法在哈希表和KMP这类边界条件多的题上极其好用。我常用的对拍流程是写一个暴力函数比如哈希集合用setint模拟KMP用暴力匹配统计次数。用一个随机数据生成器循环跑几千组小数据。对比两个函数的输出一旦不一致立刻打印当前用例手动分析。哈希表这道题我用对拍发现了contains里忘了处理deleted标记的情况——暴力set直接删除了元素哈希表却还认为元素存在两边输出不一致。这种问题在正式提交前发现能省去很多罚时。5.4 如何把本周的题迁移到真实业务场景这周三道题看起来是纯理论但在实际工程里的对应关系非常直接近似有序数组排序对应的是消息队列里“数据基本按时间戳排序偶尔有少量乱序”的场景Kafka的日志段排序就用到了类似思想。手写哈希表对应的是实现一个LRU Cache或者布隆过滤器时的底层基础很多中间件为了极致性能会绕开标准库手写哈希一次rehash策略失误就可能造成线上抖动。KMP重叠计数对应的是基因序列分析里统计特定片段出现次数的场景DNA序列中短串的重叠出现很常见直接用库函数暴力匹配在大规模数据上扛不住。所以我一直觉得周测的价值不在于这几道题本身而在于它逼着你把这些“看不见的底层”亲手搭一遍以后再遇到相关问题时你能直接判断瓶颈在哪、优化空间在哪。6. 后续可以继续深挖的两个方向这周的题做完之后我自己又延伸做了两个小实验觉得对思维训练很有帮助也推荐给正在跟训练营的同学。第一个实验是“哈希表退化对抗实验”故意构造一个哈希函数让所有key取模后都落在一个范围内观察探测链长度和操作耗时。这一步能直观感受到负载因子、哈希函数质量对性能的影响。我实测如果把负载因子从0.7改成0.95插入耗时翻了接近一倍这就是探测链变长的代价。第二个实验是“KMP回退路径可视化”把每次失配后的j变化打印出来跟踪回退次数。普通KMP、nextval优化、暴力回退三者之间的对比一目了然。有些同学一直理解不了为什么KMP是O(nm)看到回退路径图基本秒懂——因为j的移动总量是线性的不会反复从头开始。这两个实验都是“超出题面”的延展但恰恰是它们让我对本周的知识点有了真正的体感。做算法题最忌讳的就是刷完就忘有时候多花半小时想清楚一个“为什么”比盲目刷十道同类型题更有效。下周的周测大概率会在这几个数据结构的组合应用上做文章提前把基础模型吃透到时候能省不少事。