企业官网建设流程全解析

1. “1998的最大小不同质数和”：筛出质数表再双指针夹逼

1.1 先把题面拆明白：这类题到底在问什么

题目原文“1998 的最大小不同质数和”，字面非常短，不同题库里表述也有差异。最常见的出题口径是：给定正整数 1998，找出所有满足条件的质数对(p, q)，其中p和q是不同的质数，且p + q = 1998；如果题目要求“最大小”，通常指的是在所有可行组合里，分别找出质数最大的一组和质数最小的一组，或者直接输出全部组合。

不管最终输出哪种，第一步都是同一个：拿到 1998 以内的全部质数。这里有个容易踩的坑，就是题目要求“不同质数”，意味着p = q = 999这种分身组合必须排除，而且因为 1998 是偶数，质数对里的 2 也参与不了（2 + 1996，而 1996 显然不是质数），实际跑起来会省掉一批无用功。

这种题本身数值范围不大，1998 连“大数据”都算不上，但它的算法骨架值得单独拿出来讲：质数筛法 + 有序数组上的双指针。这个骨架在“两数之和”“三数之和”那一类题里反复出现，先练熟它，后面能省很多事。

1.2 判断质数：别一上来就写埃氏筛

很多人一看到质数题，条件反射就写埃氏筛。小范围题目里这不算错，但如果只是判断单个数字是不是质数，试除法更直接，代码也更短。

试除法的核心是：对于一个数x，只需要检查2到√x之间有没有能整除它的整数。为什么是√x而不是x/2？因为如果x = a * b，a和b不可能同时大于√x，所以只要小的因子没找到，大的因子就一定不存在。实现时用i * i <= x来避免调用sqrt()产生浮点误差：

bool isPrime(int x) { if (x < 2) return false; for (int i = 2; i * i <= x; i++) { if (x % i == 0) return false; } return true; }

注意两点：第一，x = 2要单独返回true，别被循环条件挡掉；第二，i * i在极端大的数据下可能溢出，但 1998 这个范围完全不用担心。真到int撑不住的时候，就该换埃氏筛或者线性筛了。

1.3 埃氏筛与线性筛：生成质数表的标准姿势

如果要多次判断质数，或者题目范围是10^6、10^7，逐个试除就不划算了。埃氏筛的思路是开一个布尔数组，先假定全是质数，然后从 2 开始，把每个质数的倍数全部标成合数。实现里有两个优化可以立刻做：外层循环只需要到sqrt(n)，内层从i * i开始标记，因为比i * i小的倍数已经被更小的质数标过了。

vector<int> sieve(int n) { vector<bool> isPrime(n + 1, true); isPrime[0] = isPrime[1] = false; for (int i = 2; i * i <= n; i++) { if (isPrime[i]) { for (int j = i * i; j <= n; j += i) { isPrime[j] = false; } } } vector<int> primes; for (int i = 2; i <= n; i++) { if (isPrime[i]) primes.push_back(i); } return primes; }

如果数据范围再大，或者题目要求每个数求出最小质因子，就上线性筛（欧拉筛）。线性筛的关键是每个合数只被它的最小质因子筛掉一次，复杂度严格O(n)。算法题里“埃氏筛够用，线性筛保平安”，这句话基本成立。

1.4 双指针统计质数对：为什么不用两层循环

拿到升序质数表后，找p + q = 1998最直观的做法是两层循环枚举所有组合，复杂度O(m^2)，m是质数个数。对于 1998 完全可行，但既然质数表已经有序，用双指针可以压到O(m)，而且代码几乎同样简单：

int target = 1998; int l = 0, r = primes.size() - 1; while (l < r) { int sum = primes[l] + primes[r]; if (sum == target) { cout << primes[l] << " + " << primes[r] << endl; l++; r--; } else if (sum < target) { l++; } else { r--; } }

双指针正确性的前提是数组有序。当sum < target时，说明右指针已经到头了，只有把左指针向右移动才能让和变大；反之亦然，整个过程不会漏掉任何一组配对。注意循环条件是l < r，这样天然规避了“两个不同质数”的要求，不需要额外判断p != q。

跑完 1998 之后你会发现，满足条件的质数对是有限的，输出顺序也是确定的。这里顺手做一个小优化：如果题面只要求“最大质数组合”和“最小质数组合”，那第一次命中就是最小质数组合，最后一次命中就是最大质数组合，不需要把中间结果全部存下来。

1.5 这个题还能怎么扩展

把题目换成“给定范围[L, R]内偶数能拆成几组不同质数和”，思路完全一样，只是多了边界处理：先筛出R以内的质数表，再对每个偶数跑一次双指针。再往上走，如果范围到10^7，双指针 + 埃氏筛依然是首选。如果追求极致，可以用 bitset 压缩标记数组，把内存降到原来的八分之一，这在很多 OJ 上能卡过更极限的数据。

我这里再强调一次：筛法函数是这类题的“基础设施”，建议把埃氏筛和线性筛都背成肌肉记忆，写的时候不要看资料。

2. 集合 M 的前 100 个数：生成候选、去重、排序，一步都不能省

2.1 先确定 M 到底是什么

“集合 M 的前 100 个数”这句话单独看是不完整的，完整题面通常会给出 M 的定义。在我这里，既然前一道题刚刚算完 1998 的质数对，那我顺理成章地把 M 定义为：

• M 是所有不超过 1998 的正整数n，且n可以被写成两个不同质数之和。

这个定义和上一题紧密衔接，也让整套博文的代码可以复用。如果你的题库里 M 另有定义，比如“所有形如2^a * 3^b * 5^c的数”或者“由某个递推式生成的数”，完全不用慌，处理套路是通用的：按规则生成候选 → 去重 → 排序 → 截取前 100 项。下面这套方法论的每一环都值得看清楚。

2.2 从质数表出发，直接生成 M

因为 M 的定义是“可写成两个不同质数之和”，而我们手里已经有 1998 以内的质数表，直接双重循环枚举两个不同质数的和，然后标记进布尔数组就行：

const int LIMIT = 1998; vector<bool> isPrime = sieve(LIMIT); vector<bool> inM(LIMIT + 1, false); int primeCount = primes.size(); for (int i = 0; i < primeCount; i++) { for (int j = i + 1; j < primeCount; j++) { int sum = primes[i] + primes[j]; if (sum <= LIMIT) { inM[sum] = true; } } } int count = 0; for (int x = 1; x <= LIMIT; x++) { if (inM[x]) { count++; if (count <= 100) { cout << x << " "; } } if (count == 100) break; }

这里j从i + 1开始，既保证了两个质数不同，也天然去掉了重复组合，比如(3, 5)和(5, 3)只会被统计一次。用inM布尔数组去重的原理在于，一个数字可能被多组质数对命中，但集合里只能出现一次。最后从小到大扫描数组，取前 100 个就是升序结果。

这个做法的时间复杂度是O(m^2 + LIMIT)，其中m是质数个数。1998 以内质数大约 300 个，九万次枚举完全无压力。真正要注意的是LIMIT和100这两个边界：如果你把集合上限改大，或者要求输出第 1000 项，内存和时间的量级要提前算清楚。

2.3 通用化：丑数、快乐数、任意规则生成的前 N 项

“集合 M 的前 100 个数”在数据结构教材里最经典的变体是丑数：只包含质因子 2、3、5 的正整数，按从小到大的顺序排列，求第 n 个。这类题比上一节的“两两质数和”更常见，解法也更值得记。

最直观的做法是用小根堆：每次从堆里弹出最小值，然后把它的 2 倍、3 倍、5 倍压回堆里，同时用一个集合去重。代码如下：

#include <queue> #include <unordered_set> using namespace std; int nthUglyNumber(int n) { priority_queue<long long, vector<long long>, greater<long long>> pq; unordered_set<long long> seen; pq.push(1); seen.insert(1); vector<long long> res; while ((int)res.size() < n) { long long cur = pq.top(); pq.pop(); res.push_back(cur); for (int f : {2, 3, 5}) { long long nxt = cur * f; if (!seen.count(nxt)) { seen.insert(nxt); pq.push(nxt); } } } return res[n - 1]; }

堆里每次弹出的是当前最小值，所以res天然就是升序排列。时间复杂度O(n log n)，空间也是O(n)，n 到10^4级别都能跑。更快的解法是三指针动态规划，每个丑数都是之前某个丑数乘 2、3、5 得到的最小值，用三个指针分别记录乘到哪一位，可以做到O(n)。这两种解法建议都手写一遍，面试问到“如何高效生成第 n 个丑数”时，至少能给出两种方案。

2.4 这类题最隐蔽的三个坑

第一个坑是“前 100 个”和“第 100 个”的区别。前者要求把所有元素存下来，后者只要维护一个堆或者计数到目标位置就行，很多写出超内存的同学就是没分清这个。第二个坑是集合元素从哪一项开始。如果 M 的定义包含 1，那答案列表的第一个元素是 1；如果不包含，起始位置不同，后面全错。第三个坑是生成顺序不等于最终顺序，比如“两两质数和”的枚举结果显然不是升序的，必须先收集再去重排序，不能直接边生成边输出。

个人经验是：遇到任何“集合 M 前 N 个”的题，先在纸上把 M 的生成规则写清楚，再决定用枚举还是递推。定义不明确时，宁可与出题人确认，也不要自己猜，这一步比代码本身更决定成败。

3. 二叉排序树排序：为什么中序遍历就是答案

3.1 建树的过程比排序本身更容易出错

二叉排序树（BST）的规则一句话就能说清：对于任意节点，左子树所有值都小于它，右子树所有值都大于它（或者全部不小于）。排序算法的思路就是把待排序元素依次插入 BST，然后做一遍中序遍历，输出结果就是升序序列。

建树时的核心是插入函数。绝大多数教材版本长这样：

struct TreeNode { int val; TreeNode* left; TreeNode* right; TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} }; TreeNode* insert(TreeNode* root, int val) { if (!root) return new TreeNode(val); if (val < root->val) { root->left = insert(root->left, val); } else if (val > root->val) { root->right = insert(root->right, val); } // 相等时什么也不做，等价于去重排序 return root; }

看到这里，细心的读者会发现问题：如果序列里有重复元素，相等值的第二个元素去哪了？上面这段代码会让它消失，也就是说排序结果会去重。这是真实的坑。如果你希望保留重复元素，插入逻辑要改成“相等时仍然插到右子树”，比如把else分支改成root->right = insert(root->right, val)，这样中序遍历时相等的值会连续输出。实际工程里到底怎么处理重复值，完全取决于需求，但作为排序算法，通常要保留重复项。

3.2 中序遍历：递归三行，迭代十行

中序遍历的递归版本是二叉树的通用模板：

void inorder(TreeNode* root, vector<int>& res) { if (!root) return; inorder(root->left, res); res.push_back(root->val); inorder(root->right, res); }

递归版本简洁，但面试官常会追问“不用递归怎么写”。迭代版本要用显式栈模拟递归过程，关键在于先一路向左压栈，弹出后转向右子树：

vector<int> inorderIterative(TreeNode* root) { vector<int> res; stack<TreeNode*> st; TreeNode* cur = root; while (cur || !st.empty()) { while (cur) { st.push(cur); cur = cur->left; } cur = st.top(); st.pop(); res.push_back(cur->val); cur = cur->right; } return res; }

我个人的建议是：递归和迭代都要会在五分钟内写对。不是因为面试一定会考迭代，而是写迭代的过程中，你对“中序遍历 = 左根右”这个顺序的理解会踏实很多，递归版反而更像背模板。

3.3 复杂度真相：平均很美，最坏很惨

先说平均情况。对n个随机排列的元素构建 BST，每个节点插入的期望深度是O(log n)，所以建树总时间是O(n log n)，中序遍历是O(n)，空间额外O(n)。这个复杂度看起来和快速排序、归并排序一个级别，但 BST 排序有一个致命弱点：如果输入本身是升序或降序，每次插入的新节点永远挂在根节点同一侧，树直接退化成链表，插入变成O(n)，总复杂度变成O(n^2)。

我拿实测数据解释这句话：给一个已经排好序的 10000 个元素的数组构建 BST，树的深度就是 10000，程序跑起来明显卡顿；给随机打乱的同规模数据，深度大概只有 30 左右，差距肉眼可见。

解决退化有两个方向。一个是建树前先把输入洗牌，最简单粗暴，但有些场景不允许改变输入顺序。另一个是用平衡树，比如 AVL 树或红黑树，插入后通过旋转保持高度平衡。更偏算法竞赛的做法是用 Treap：每个节点附一个随机优先级，整棵树既满足 BST 的值序，又满足堆的优先级序，随机化保证期望深度O(log n)，代码量比 AVL 小很多。

3.4 BST 排序和快排、归并、堆排放在一起看

BST 排序对比其他算法，最大优势不是排序本身的性能，而是它维护的是一个动态有序结构。排序只是顺带的能力，真正的价值在于插入、删除、查找都能在O(log n)完成，而且随时能取中位数、找前驱后继。如果你只需要一次性给一个静态数组排序，老老实实用快排或归并；如果数据是流式到达、需要动态有序，BST 这套数据结构的思路才是核心。

有一点要提醒：BST 排序的空间开销包含每个节点的左右指针，实际占用比数组大不少。追求节省内存时不要选它，这也是为什么工程排序库基本都是内省排序而不是 BST 排序。

4. 通配符字符串匹配：从指数级回溯到 DP，再到贪心双指针

4.1 题目约定：'?' 和 '*' 的语义要记牢

通配符匹配是 LeetCode 44 的原题，也是各大厂面试爱考的经典题。题面是这样约定的：给定一个文本串s和一个模式串p，模式串里的?可以匹配任意单个字符，*可以匹配任意长度的任意序列，包括空序列。注意这里的*和正则表达式里的*完全不同，正则里*是修饰前一个字符出现的次数，通配符场景里*是独立存在的，能一口气吃掉任意多个字符。这个区别面试时几乎必问，先搞清楚再写代码。

最笨的方法是递归回溯。匹配到*的时候，分两种情况尝试：要么让*匹配空串，要么让它吃掉当前字符再继续。这个思路逻辑上完全正确，但复杂度是指数级的，因为*每遇到一个新字符都可能产生一次分支，遇到"***...*"这种模式时直接爆炸。这也是所有字符串匹配题里“朴素解法为什么不可行”的标准答案。

4.2 二维 DP：状态转移的四个分支一次理清

设dp[i][j]表示文本串s的前i个字符s[0..i-1]是否能被模式串p的前j个字符p[0..j-1]匹配。最终答案就是dp[n][m]，其中n = s.length()，m = p.length()。

初始化分两部分。dp[0][0] = true表示空串匹配空串。dp[0][j]表示空文本能否被p[0..j-1]匹配，显然只有当p[0..j-1]全部是*时才可能，因为*能匹配空串，?不行、具体字符也不行。

状态转移时看p[j-1]的值：

• 如果p[j-1] == '?'：必须要求s[i-1]存在，且当前字符被?消耗掉，所以dp[i][j] = dp[i-1][j-1]。
• 如果p[j-1]是普通字符：要求s[i-1] == p[j-1]，同时dp[i][j] = dp[i-1][j-1]。
• 如果p[j-1] == '*'：这是核心。*可以匹配空串，也就是消耗掉模式串的这一个*但文本串不动，对应dp[i][j-1]；*也可以吃掉当前字符，也就是文本串前进一步但模式串不动，对应dp[i-1][j]。两种情况只要有一种成立即可，所以dp[i][j] = dp[i][j-1] || dp[i-1][j]。

说实话，dp[i][j-1]和dp[i-1][j]这两个方向第一次看容易混。我的记忆方法是：j-1是“模式串退一格”，表示这个*这次不吞字符；i-1是“文本串退一格”，表示之前的某个时刻*已经吞掉了一个字符。反复在小样例上手动推一遍，很快就顺了。

完整代码如下：

bool isMatch(string s, string p) { int n = s.size(), m = p.size(); vector<vector<bool>> dp(n + 1, vector<bool>(m + 1, false)); dp[0][0] = true; for (int j = 1; j <= m; j++) { if (p[j - 1] == '*') dp[0][j] = dp[0][j - 1]; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (p[j - 1] == '?') { dp[i][j] = dp[i - 1][j - 1]; } else if (p[j - 1] == '*') { dp[i][j] = dp[i][j - 1] || dp[i - 1][j]; } else { dp[i][j] = dp[i - 1][j - 1] && (s[i - 1] == p[j - 1]); } } } return dp[n][m]; }

我在本地用这几个用例验证过，建议你拿到代码后也先跑一遍再做修改：isMatch("adceb", "*a*b")返回true；isMatch("acdcb", "a*c?b")返回false；isMatch("", "****")返回true；isMatch("aa", "a")返回false。尤其是第三个，空串配全星号，最容易被初始化代码挡在门外。

4.3 空间优化：滚动数组把二维压成一维

二维 DP 的时间复杂度是O(n*m)，这个一般没法再降，但空间可以。观察转移方程可以发现，dp[i][j]只依赖dp[i-1][j]（上一行同一列）和dp[i][j-1]（当前行前一列），与更早的行无关。所以可以用一维数组dp[j]滚动，按行从左到右更新。需要注意：更新dp[j]前，dp[j]里存的还是上一行的值，正好就是dp[i-1][j]；而dp[j-1]刚被更新过，正好就是dp[i][j-1]。这个“错位复用”是滚动数组的精髓。

bool isMatch_1D(string s, string p) { int n = s.size(), m = p.size(); vector<bool> dp(m + 1, false); dp[0] = true; for (int j = 1; j <= m; j++) { if (p[j - 1] == '*') dp[j] = dp[j - 1]; } for (int i = 1; i <= n; i++) { bool prev = dp[0]; // 即 dp[i-1][0] dp[0] = false; // 非空文本一定匹配不了空模式 for (int j = 1; j <= m; j++) { bool temp = dp[j]; // 保存旧的 dp[j]，即 dp[i-1][j] if (p[j - 1] == '?') { dp[j] = prev; } else if (p[j - 1] == '*') { dp[j] = dp[j] || dp[j - 1]; } else { dp[j] = prev && (s[i - 1] == p[j - 1]); } prev = temp; } } return dp[m]; }

这里prev变量存的是上一行的dp[j-1]，也就是二维数组里的dp[i-1][j-1]。第一次写滚动数组很容易在?和普通字符分支里用错值，我的建议是先在草稿纸上把二维的前三行手推一遍，再去对照一维代码。

4.4 贪心 + 双指针：时间 O(n+m)、空间 O(1) 的解法

DP 解法已经能过大部分面试，但还有更高阶的解法：贪心配合双指针。思路是维护四个变量：i扫文本串，j扫模式串，starIdx记录最近一个*在模式串里的位置，matchIdx记录这个*当前匹配到文本串的哪个位置。匹配规则如下：

• 如果s[i]和p[j]相等，或p[j] == '?'，两者都前进；
• 如果p[j] == '*'，记录starIdx = j，把matchIdx = i，然后只把j前进，先假设*匹配空串；
• 如果失配，但之前遇到过*，就回溯：让j = starIdx + 1，i = ++matchIdx，表示让*再多吃一个字符；
• 如果失配且没有*可用，直接返回false。

bool isMatch_Greedy(string s, string p) { int i = 0, j = 0; int n = s.size(), m = p.size(); int starIdx = -1, matchIdx = -1; while (i < n) { if (j < m && (s[i] == p[j] || p[j] == '?')) { i++; j++; } else if (j < m && p[j] == '*') { starIdx = j; matchIdx = i; j++; } else if (starIdx != -1) { j = starIdx + 1; i = ++matchIdx; } else { return false; } } while (j < m && p[j] == '*') j++; return j == m; }

这个解法的正确性建立在“*尽量多匹配字符，等到发现后面匹配不上再回头扩展”这一策略上。最后的while循环很关键，因为模式串末尾多余的*都能匹配空串，不能漏掉。实测s = "aab"、p = "c*a*b"这类例子时，第一次失配发生在i=0,j=0，因为没有*记录，直接返回false，逻辑完全正确。

两个解法的取舍：DP 思路直观、容易扩展到更复杂的匹配规则；贪心双指针在长文本和长模式串上性能远胜，现场手写也更华丽。我建议先把二维 DP 跑熟，再花半小时理解贪心回溯，面试时两者至少能讲一个。

4.5 通配符匹配最容易翻车的三个细节

细节一：初始化永远先测空文本串。dp[0][j]只有在p的前j个字符全是*时才是true，写错这一行，后面全错。细节二：贪心解法里i的回溯位置是matchIdx的后一位，不是i本身，写错会让*反复匹配同一个字符，造成死循环。细节三：区分通配符匹配和正则匹配，"*"在通配符里能匹配任意串，在正则里却是个修饰符，别混。

这四道题做完，我的体感是它们恰好代表算法面试里最高频的四类工具：筛法与夹逼、集合生成与截取、二叉树的构造与遍历、字符串 DP 与贪心。如果目标是应付笔试面试，把这几份代码都练到“不看资料 20 分钟写对”的程度，比刷几十道同类型题更有效果。我个人还有一个习惯：每题跑完后不要马上看下一题，先 PRINT 一下中间结果，把集合 M 的前二十个数、BST 的中序遍历序列、DP 的二维表都打印出来对一眼。很多你以为写对了的边界，打印出来才发现差了一个数，这个小动作能省下不少 debug 时间。