企业官网建设流程全解析

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，那么全局最小值一定出现在前k+1个元素里。反过来想，当我们排到位置i时，当前的候选元素只需要从arr[i]到arr[i+k]这部分取即可，前面已经确定了位置，后面还没进入窗口的元素不可能跑到前面来。

典型的解法是用一个大小为k+1的最小堆：

1. 先把前k+1个元素入堆。
2. 每次从堆顶取出最小值放到结果数组当前位置。
3. 然后把下一个元素入堆，维持堆中始终有k+1个候选。
4. 遍历完所有元素后，把堆中剩余元素依次弹出。

这个思路和“滑动窗口 + 堆”是同一个模型，时间复杂度O(n log k)，空间复杂度O(k)，完美匹配题目要求。

2.3 完整C++实现

#include <queue> #include <vector> using namespace std; vector<int> sortNearlySorted(vector<int>& arr, int k) { int n = arr.size(); // 最小堆，greater<int>实现升序 priority_queue<int, vector<int>, greater<int>> minHeap; vector<int> 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; }

这里有一个非常容易写错的地方：循环里入堆和弹出是同步进行的，很多同学写成“先把前k+1个入堆，再开始弹”，后面又要单独处理窗口边界，代码反而绕了。上面这种写法，每次先入堆再判断堆大小，逻辑上更干净，也不用额外处理“堆还没满能不能弹”的状态。

2.4 实测数据对比：堆排序 vs 插入排序 vs 快排

为了验证不同算法的真实表现，我跑了一组对比数据，n=10万，k分别取5、50、500，结果如下：

从数据能看出两个结论：

• 当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_queue<int, vector<int>, greater<int>>，但当时手滑少写了<int>，编译不过。这类模板参数错误很隐蔽，建议大家在本地先跑一个最小用例（比如vector<int> v = {3, 1, 2};）验证堆的出入顺序。

另外，如果题目要求“稳定排序”，那么最小堆方案需要额外记录元素下标来保证相同元素的相对顺序不变，但训练营这道题没有这个要求，可以简化处理。真实面试中如果遇到变体题，一定要先问清楚是否需要稳定排序。

3. 习题11-4复盘：手写哈希表，三个隐藏考点全拆解

3.1 题目考查点：哈希表不只是算个下标

习题11-4要求实现一个哈希集合，支持add、remove、contains三个操作，但强制要求自己处理冲突、删除和扩容，不能直接调用语言自带的unordered_set。

这道题在训练营内部讨论区争议不小，因为它不像前面的排序题，只要会STL就够用了；手写哈希表要求你把底层机制完全理清楚。实现上主要考查三个点：

1. 冲突处理用线性探测，而不是链地址法。
2. 删除操作不能直接把槽位置空，必须用懒删除标记（tombstone）。
3. 当负载因子超过阈值时，需要扩容并重新哈希。

3.2 第一个考点：线性探测 vs 链地址法

链地址法是最容易写的，每个槽位挂一个链表，冲突就往后插。但训练营这道题指定线性探测，因为线性探测的缓存局部性好，而且它有个特点：删除操作会额外引入复杂度，正是出题人想考的地方。

线性探测的核心逻辑是：当hash(key)位置已经被占用时，就线性地往后找第一个空位。查找时也是同样的路线，沿着探测序列走，直到遇到空槽为止。这里的循环查找可以用idx = (idx + 1) % capacity来实现。

3.3 第二个考点：为什么删除不能直接置空

这是整道题最关键的思考题。假设哈希表里依次插入了3、13、23，而且hash(3) = 3 % 8 = 3，hash(13) = 13 % 8 = 5，hash(23) = 23 % 8 = 7，它们没有冲突，这种情况看不出问题。但换个例子：插入1和9，hash(1) = 1，hash(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; }; vector<Slot> table; int capacity; int size; const double LOAD_FACTOR = 0.7; int hash(int key) { return key % capacity; } void rehash() { int oldCapacity = capacity; vector<Slot> 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()函数里有个细节：保存旧表时我用的是vector<Slot> 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万。结果如下：

可以看到，大量删除操作之后性能会明显下降，原因是tombstone标记越来越多，探测链变长。如果题目允许，可以在删除操作发现size明显小于capacity时主动触发rehash来清理tombstone，这就是“压缩”操作。训练营这道题没让实现shrink，但我在本地测试时加了，交替场景能快30%左右。

4. 习题12-4复盘：KMP的next数组推导与重叠匹配

4.1 题目要求：不只是匹配，还要统计次数

这道题要求实现KMP算法，给定文本串text和模式串pattern，统计pattern在text中出现的次数，并且允许重叠匹配。比如text = "ababa"，pattern = "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"。

i=0: 前缀"a"，next[0]=0 i=1: 前缀"ab"，next[1]=0 i=2: 前缀"aba"，最长相等前后缀是"a"，next[2]=1 i=3: 前缀"abab"，最长相等前后缀是"ab"，next[3]=2 i=4: 前缀"ababc"，next[4]=0 i=5: 前缀"ababca"，最长相等前后缀是"a"，next[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; vector<int> buildNext(const string& p) { int m = p.size(); vector<int> 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; vector<int> 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++; // 关键：匹配成功后不是j=0，而是回退到next[j-1]，允许重叠 j = next[j - 1]; } } return count; }

4.4 重叠匹配的边界问题

这道题最容易错的点就在匹配成功之后。按常见模板，匹配成功后会让j = 0，从头开始匹配下一段，但这样会漏掉重叠部分。正确做法是j = next[j - 1]，因为此时pattern[0..m-1]已经匹配完，而这个完整前缀的最长相等前后缀信息，正好告诉我们下一次匹配可以从哪里继续。

举个例子：text = "aaaaa"，pattern = "aa"。

• i=1时匹配第一个"aa"，j=2，计数1，j回退到next[1]=1。
• i=2时，j=1，text[2]='a'等于pattern[1]='a'，j=2，计数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]]。但要注意，这只适用于“找不到更优回退位”的场景，需要从i=1开始遍历一次，遇到pattern[i] == pattern[next[i]]才做更新。这个优化在文本串和模式串相似度极高时性能提升明显，比如模式串是"aaaaaaaaaa"，text也是大量重复的"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]访问了j=0，能过。真正让我翻车的是重叠匹配后的回退：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的模板参数写错，漏了vector<int>。
• 类成员变量的定义顺序问题，比如用vector<Slot> table;和int capacity;定义顺序不一致，导致构造函数初始化列表报错。
• 在C++里混用了size()返回的size_t和整型比较，出现符号警告，有些严格的编译选项直接报错。

我的习惯是：本地用-Wall -Wextra编译，把警告当错误修。周测前把训练营OJ的编译选项确认清楚，有些OJ默认开启-Werror，一个符号警告就能让你整题0分。

5.2 时间复杂度的快速估算方法

周测的限时一般比较紧，做题前先在草稿纸上估算一下复杂度，避免写完才发现超时。我的估算方法是：

• 极端用例规模是1e5，O(n²)就是1e10次操作，肯定超时。
• O(n log n)大概是1e5 * 17 = 1.7e6，很稳。
• O(n)更不用说，几毫秒级别。

遇到不确定的题，先写暴力解保证拿部分分，然后针对数据范围选择优化方案。比如习题8-4，如果k的范围没给清楚，写插入排序能保底，再写堆方案拿满分。

5.3 用对拍脚本验证正确性

训练营这周开始，我强烈建议大家学会写对拍脚本。简单说：写一个暴力解法作为答案基准，再写一个待验证的优化解法，用随机小数据反复跑，对比两者输出是否一致。这个方法在哈希表和KMP这类边界条件多的题上极其好用。

我常用的对拍流程是：

1. 写一个暴力函数，比如哈希集合用set<int>模拟，KMP用暴力匹配统计次数。
2. 用一个随机数据生成器，循环跑几千组小数据。
3. 对比两个函数的输出，一旦不一致，立刻打印当前用例，手动分析。

哈希表这道题，我用对拍发现了contains里忘了处理deleted标记的情况——暴力set直接删除了元素，哈希表却还认为元素存在，两边输出不一致。这种问题在正式提交前发现，能省去很多罚时。

5.4 如何把本周的题迁移到真实业务场景

这周三道题看起来是纯理论，但在实际工程里的对应关系非常直接：

• 近似有序数组排序，对应的是消息队列里“数据基本按时间戳排序，偶尔有少量乱序”的场景，Kafka的日志段排序就用到了类似思想。
• 手写哈希表，对应的是实现一个LRU Cache或者布隆过滤器时的底层基础，很多中间件为了极致性能会绕开标准库手写哈希，一次rehash策略失误就可能造成线上抖动。
• KMP重叠计数，对应的是基因序列分析里统计特定片段出现次数的场景，DNA序列中短串的重叠出现很常见，直接用库函数暴力匹配在大规模数据上扛不住。

所以我一直觉得，周测的价值不在于这几道题本身，而在于它逼着你把这些“看不见的底层”亲手搭一遍，以后再遇到相关问题时，你能直接判断瓶颈在哪、优化空间在哪。

6. 后续可以继续深挖的两个方向

这周的题做完之后，我自己又延伸做了两个小实验，觉得对思维训练很有帮助，也推荐给正在跟训练营的同学。

第一个实验是“哈希表退化对抗实验”：故意构造一个哈希函数，让所有key取模后都落在一个范围内，观察探测链长度和操作耗时。这一步能直观感受到负载因子、哈希函数质量对性能的影响。我实测如果把负载因子从0.7改成0.95，插入耗时翻了接近一倍，这就是探测链变长的代价。

第二个实验是“KMP回退路径可视化”：把每次失配后的j变化打印出来，跟踪回退次数。普通KMP、nextval优化、暴力回退三者之间的对比一目了然。有些同学一直理解不了为什么KMP是O(n+m)，看到回退路径图基本秒懂——因为j的移动总量是线性的，不会反复从头开始。

这两个实验都是“超出题面”的延展，但恰恰是它们让我对本周的知识点有了真正的体感。做算法题最忌讳的就是刷完就忘，有时候多花半小时想清楚一个“为什么”，比盲目刷十道同类型题更有效。下周的周测大概率会在这几个数据结构的组合应用上做文章，提前把基础模型吃透，到时候能省不少事。