day36算法练习：质数判定、字符串处理与排序的细节优化

这一天的挑战有点意思——三道题放在一块儿，其实正好覆盖了编程里三个最基础也最容易出问题的环节：数学逻辑、字符串处理、还有集合操作。质数、翻译字符串、分割数字并排序，听起来都是入门题，但真上手写的时候，你会发现坑全在细节里。我做完这组题之后的感受是：题目越简单，越能看出一个人平时写代码的习惯。这篇文章就把我当天的完整思路、踩过的坑、以及最终拿出来的解法都记录下来，希望能给正在刷day36这类综合练习的朋友一些参考。

1. 质数判定：从试除到筛法，复杂度是怎么一步步降下来的

1.1 暴力试除法：逻辑正确，但8成时间被浪费

先看第一题：找出质数。很多人上来就会写最直观的版本——对每个数n，从2一直试除到n-1，只要发现能整除就说明它不是质数。

int is_prime(int n) { if (n < 2) return 0; for (int i = 2; i < n; i++) { if (n % i == 0) return 0; } return 1; }

这段代码逻辑完全没问题，如果只是判断一两个小数字，运行也很快。但问题是，这类题目给的真实场景往往是“找出某个区间内的所有质数”，比如1到100000之间的质数。这时候问题就来了：单次判断的最坏情况是遍历n-2个数，如果对区间内每个数都做一次完整判断，总计算量大约是Σn，也就是从1累加到100000，算下来大概是50亿次取模运算。在普通在线评测环境下，这个量级基本会超时。

我当时第一版跑出来之后，心里想的是：完了，这题没那么简单。踩了这个坑之后我明白了一个道理——看起来最简单的解法，往往只是“能跑”的解法，离“能过”还差很远。

1.2 平方根优化：一行代码立省九成计算

优化思路其实很朴素：如果n有一个大于√n的因子a，那么必然存在一个小于√n的因子b，使得a×b=n。所以判断n是否为质数，只需要检查2到√n之间的整数就够了。

为什么这个结论成立？因为因子是成对出现的。以n=36为例，它的因子对是(1,36)、(2,18)、(3,12)、(4,9)、(6,6)。可以看到，从6开始，因子就开始重复了。所以检查到√n=6就够了，再往后检查的都是重复工作。

36 = 2 × 18 = 3 × 12 = 4 × 9 = 6 × 6 ↑ 检查到6就覆盖了所有因子对

改造代码只动了一个条件：

int is_prime(int n) { if (n < 2) return 0; for (int i = 2; i * i <= n; i++) { if (n % i == 0) return 0; } return 1; }

单次判断的复杂度从O(n)降到了O(√n)。判断1到100000区间内的所有数，计算量从大约50亿次降到大约316万次，整整省了99%的计算量。这个优化是所有质数题的基础，后面的所有方案都是在它之上叠加的。

1.3 埃拉托斯特尼筛法：批量判定的标准答案

如果你的题目是“找出1到N之间的所有质数”，那么就算用了平方根优化，逐个判断每个数仍然是重复劳动。比如判断101和103的时候，你都在重复计算2到√101、2到√103这些试除过程。更优的做法是一次性把所有合数标记出来，剩下的自然就是质数——这就是埃拉托斯特尼筛法。

原理简单说：从2开始，它是质数；把2的所有倍数都标记为合数；然后找下一个未被标记的数，就是3；再把3的所有倍数标记为合数；以此类推。

void sieve(int n, int is_prime[]) { for (int i = 0; i <= n; i++) is_prime[i] = 1; is_prime[0] = is_prime[1] = 0; for (int i = 2; i * i <= n; i++) { if (is_prime[i]) { for (int j = i * i; j <= n; j += i) { is_prime[j] = 0; } } } }

注意内层循环从i×i开始，而不是从2×i开始。这也是一个常见的优化点：因为i的较小倍数在之前已经被更小的质因子筛过了。比如i=5时，5×2=10早被2筛过，5×3=15早被3筛过，5×4=20早被2筛过，所以直接从25开始标记就行。这个优化能让筛法在N很大时明显更快，实测在N=100万时，从i×i开始的版本比从2×i开始的版本快大约15%到20%。

筛法的整体复杂度是O(n log log n)，n=100万时大概只需要几十毫秒。我刚才说Combinatorics这类问题里最常用的质数工具就是它，不是没道理的。

1.4 实际编码中最容易翻车的两个点

质数题翻车的地方反而不在算法本身，而在边界条件和语言细节。

第一个坑是数据类型。判断质数时如果i×i超出int范围就会溢出。比如n是10亿量级时，√n大约是31623，i×i还在int范围内，没问题。但如果你的循环条件是i <= n，然后不加平方根优化，i到10亿级别时i×i直接溢出变成负数，判断条件直接就乱了。所以要么用i*i <= n这种写法并确认n不超过int范围，要么用long long存i。

第二个坑是1和0的处理。0和1既不是质数也不是合数，但如果你忘了特判，很多实现会把1当成质数输出。尤其是筛法初始化全为1时，必须手动将is_prime[0]和is_prime[1]置为0。我见过有人在这上面栽跟头：筛法逻辑全对，边界没查，结果1被当成质数打出来，白白扣分。

2. 字符串"翻译"：逆序、过滤与大小写变换里的细节

2.1 先把需求拆清楚

第二题的描述是“翻译字符串”，这个词在不同版本的题目里意思不太一样。结合配套的热搜词和常见练习来看，这题一般包含三个子任务：字符串逆序输出、过滤非字母数字字符、大小写转换。这三个操作单独拎出来都不难，但合在一起写的时候，很多人会栽在处理顺序上。

我当天的处理顺序是：先逆序，再过滤，最后统一转换大小写。这个顺序的好处是，逆序操作不依赖过滤结果，过滤操作也不依赖大小写状态，每一步的输入输出都很干净。如果你先过滤再逆序，效果一样，只是你得保证过滤逻辑里不误伤大小写判断。顺序无所谓，关键是每一步都要有明确的输入和输出。

2.2 逆序输出与C字符串结束符的坑

C语言里做字符串逆序，最常见的手写方式是用双指针：

void reverse_str(char *s) { int left = 0; int right = strlen(s) - 1; while (left < right) { char tmp = s[left]; s[left] = s[right]; s[right] = tmp; left++; right--; } }

在C++里更简单，直接用std::reverse：

std::reverse(s.begin(), s.end());

这里最大的坑是字符串结束符'\0'。C语言中字符串以'\0'结尾，strlen返回的长度不包括'\0'。如果你在反转时把'\0'也当成普通字符参与交换，结果就是字符串直接变成乱码。举个例子：

原字符串: "abc\0" 错误操作: 把s[0]和s[4]交换（s[4]是'\0'） 结果: "\0cba" → 字符串内容变成空串

正确做法是让right从strlen(s)-1开始，也就是从最后一个有效字符开始，绝不碰'\0'。C++的std::reverse会通过begin()和end()自动避开末尾的'\0'，你不需要担心，但底层逻辑是一样的。还有一点需要注意：如果用字符数组初始化，要确保数组长度比字符数大1，留出'\0'的位置；如果直接用字符串字面量初始化并试图修改，很多编译器会直接报错或运行崩溃，因为字符串字面量往往是只读的。建议声明成char s[] = "hello";而不是char *s = "hello";。

2.3 只保留字母和数字：isalnum的边界行为

“翻译字符串”的第二层操作是过滤掉所有非字母和非数字字符。比如输入"Hello, World! 123"，过滤后应该是"HelloWorld123"。这里的关键工具是isalnum，它在C/C++中的声明在<ctype.h>或<cctype>里。

#include <cctype> std::string filter_alnum(const std::string &s) { std::string result; for (char c : s) { if (std::isalnum(static_cast<unsigned char>(c))) { result += c; } } return result; }

这里有一个非常隐蔽的坑：isalnum接收的是int类型，但标准要求这个int必须能表示为unsigned char或者EOF。如果你直接传入char，在有些平台和编译器组合下，char是signed类型，ASCII码大于127的字符（比如中文字符的某个字节、或者扩展字符集里的字符）会变成负数，传给isalnum就属于未定义行为，表现就是过滤结果里出现奇怪的字符或者行为异常。安全做法是显式强转成static_cast<unsigned char>(c)。这是我在实际写的时候踩过的一个比较深的坑，网上很多教程根本不提这一点，但它在处理带中文或特殊符号的字符串时非常关键。

有人会问，Java里怎么做？Java的Character.isLetterOrDigit(char)就一笔带过了，它接受char，本身是无符号的16位值，没有这个signed问题。C#里的char.IsLetterOrDigit同理。所以这个坑主要坑的是C/C++用户。

2.4 大小写转换与编码边界

最后是大小写转换。如果题目要求把大写转小写、小写转大写，最直接的方式是逐个字符判断并转换：

char swap_case(char c) { if (std::islower(static_cast<unsigned char>(c))) return std::toupper(static_cast<unsigned char>(c)); if (std::isupper(static_cast<unsigned char>(c))) return std::tolower(static_cast<unsigned char>(c)); return c; }

原理上，大写A的ASCII码是65，小写a是97，区间内一一对应，差值为32。所以也可以直接用c ^ 32来切换大小写（只对字母有效），这个技巧在反向切换场景下非常高效，但可读性差一点。我一般不用这个，维护代码的人看了会想打人。

还有一个常见要求是字符串转数字。比如提取字符串中的数字片段，或者直接"翻译"成数值用于后续计算。C++里stoi和atoi有本质区别：stoi会抛出异常，atoi静默返回0。处理用户输入时我倾向用stoi包一层try-catch；处理算法题里保证合法的输入时用atoi更省事。关键的坑是：stoi在遇到第一个非数字字符时停止解析，"123abc"会转成123，不会报错，但很多初学者以为它会整体失败。另外，stoi如果解析不到任何数字会抛std::invalid_argument，超出int范围会抛std::out_of_range，这两个必须分开捕捉。

3. 分割数字并排序：从原始字符串到有序数组的完整链路

3.1 不同语言的split方法：细节全在分隔符上

第三题是“分割数字并排序”，典型的输入是"5, 3, 8, 1"或者"5 3 8 1"，你需要把它拆成数字数组然后升序输出。

不同语言的分割API差异很大，用错了真会翻车：

Java的split最容易踩坑：它的参数是正则表达式。如果你按.分割，直接写"123.456".split(".")返回的是空数组，因为.在正则里表示任意字符。正确写法是split("\\.")。同样，按|分割要写split("\\|")，反正只要是正则元字符都得转义。这个问题在面试和笔试题里出现频率极高。

C++没有内置split函数，最简单的做法是用stringstream处理以空白字符分隔的输入：

#include <sstream> std::vector<int> parse_numbers(const std::string &s) { std::vector<int> nums; std::stringstream ss(s); int num; while (ss >> num) { nums.push_back(num); } return nums; }

注意：stringstream的>>操作符是按空白字符自动分割的，而且会自动跳过前导空白。如果输入是"5, 3, 8, 1"这种带逗号的格式，>>就无能为力了，你需要先把逗号当作分隔符。最稳妥的方法是手写遍历：

std::vector<int> parse_numbers_with_commas(const std::string &s) { std::vector<int> nums; int current = 0; bool has_digit = false; for (char c : s) { if (c >= '0' && c <= '9') { current = current * 10 + (c - '0'); has_digit = true; } else { if (has_digit) { nums.push_back(current); current = 0; has_digit = false; } } } if (has_digit) nums.push_back(current); return nums; }

这段代码的关键是has_digit这个标志位。有了它，连续多个分隔符（比如"5,,,3"）不会产生空的数字项，末尾没有分隔符时最后一个数字也不会丢。这两个问题正好是split类题目最经典的两个坑点。

3.2 字符串转数字的隐藏陷阱

分割字符串得到的子串还都是文本，要参与排序必须先转成数字。这里有两个容易忽略的问题。

第一个是空串。如果输入是"5,,3"，按逗号分割后中间会有一个空字符串。直接对空串执行转换会得到0，或者直接抛异常。处理方式：要么在分割时跳过空串，要么在转换前显式判断if (token.empty())跳过。C#的Split方法自带一个StringSplitOptions.RemoveEmptyEntries选项，Java没有这个，得在循环里手动判断。

第二个是前导零。"007"转成整型是7，这在大多数场景下是期望行为，但如果题目要求保留数字在字符串中的原始形态（比如排序后按原格式输出），那转数字后就丢了信息。我那天做题时特意看了一眼题目描述，它要求输出排序后的数字，所以转成int没问题。但如果题目是“对字符串列表排序”，而数字是作为字符串存在，那你得小心字典序和数值序的区别——"10"在字典序下排在"2"前面，因为'1'比'2'小。一旦涉及排序，先搞清楚按什么序排。

3.3 排序算法选择与稳定性问题

排序是第三题的核心。在实际编码中，最省事的做法是直接用标准库排序：

#include <algorithm> std::sort(nums.begin(), nums.end()); // 升序 std::sort(nums.begin(), nums.end(), std::greater<int>()); // 降序

但如果你在学算法，很容易遇到一个衍生题：让你手写排序算法，比如选择排序，还要你证明它的循环不变量。这正是算法竞赛圈里常说的“CLRS选择排序循环不变量证明”。我当时还真把这段证明过程过了一遍，因为它能解释为什么选择排序每一轮交换后，前i个元素已经是全局有序的。

选择排序的循环不变量是：每次外层循环开始时，前i个元素已经是整个数组中最小的i个元素，且它们已经升序排列。理由有三条：

• 初始化：i=0时，前0个元素为空集，命题自然成立。
• 保持：第i轮内层循环找到从i到末尾的最小值，与第i个位置交换。因为前i个元素已经是全局最小的i个，剩余部分的所有值都大于等于它们，所以第i轮找出的位置i处的新值，必然使前i+1个元素保持有序且为全局最小前i+1个。
• 终止：i = n-1时，前n-1个元素全局有序，最后一个元素自然而然也处于正确位置。

这个证明不是纸上谈兵。它直接对应了选择排序的行为特征：每轮只交换一次，最多n-1次交换；比较次数固定为n(n-1)/2，不管输入是否有序。所以选择排序适合“交换成本高但比较成本低”的场景，而冒泡排序和插入排序的行为特征又不一样。你想真正理解排序算法，把循环不变量写出来比背代码有用得多。

还有一个容易被忽略的问题：标准库std::sort是不稳定排序，也就是说两个值相等的元素在排序后相对位置不保证保持不变。如果你排序的是std::pair<int, int>，希望按第一个元素排序、第一个元素相同时保持第二个元素的原始顺序，就要用std::stable_sort，或者自定义比较函数时把第二个元素也纳入比较。不过对于纯数字排序，稳定性没有任何影响，不需要纠结。

3.4 字母数字组合排序：谁在什么时候排到你面前

刚才提到字典序和数值序的区别，这个在“字母数字组合排序”场景下体现得最明显。假设你有一组形如"a2"、"a10"、"a1"的字符串，按字典序排序得到的是"a1"、"a10"、"a2"，但按“人类直觉”的自然序，你期望的是"a1"、"a2"、"a10"。这俩结果不一样。

原因就是字符串逐字符比较时，'1'和'2'的比较发生在'0'之前："a10"和"a2"先比'a'和'a'，再比'1'和'2'，'1'小于'2'，所以"a10"排在"a2"前面。但数字10显然比2大，这就是信息丢失导致的错误排序。

要解决这个问题，需要自己写一个比较函数：把字符串里的数字部分提取出来按数值比较，字母部分按字典序比较。这在C++里可以这样写：

bool natural_compare(const std::string &a, const std::string &b) { size_t i = 0, j = 0; while (i < a.size() && j < b.size()) { if (std::isdigit(a[i]) && std::isdigit(b[j])) { size_t i_end = i; while (i_end < a.size() && std::isdigit(a[i_end])) i_end++; size_t j_end = j; while (j_end < b.size() && std::isdigit(b[j_end])) j_end++; // 去掉前导零后比较数值，或先按长度比较再按字典序比较 std::string num_a = a.substr(i, i_end - i); std::string num_b = b.substr(j, j_end - j); if (num_a.size() != num_b.size()) return num_a.size() < num_b.size(); if (num_a != num_b) return num_a < num_b; i = i_end; j = j_end; } else if (a[i] != b[j]) { return a[i] < b[j]; } else { i++; j++; } } return a.size() < b.size(); }

这个比较函数的价值在于：它真正实现了“数字按数值比、字母按字符比”的自然排序逻辑。写这类代码时，最常见的错误是只处理了“两个字符都是数字”的情况，没处理“一个是数字一个不是”的交叉情况。上面代码里，如果a[i]是数字而b[j]不是，会走最后的else分支，按普通字符比较。实际排序时会发现这个决策在某些极端输入下不一定符合直觉（比如"a2b"和"a10"谁在前？），但至少行为是确定且可解释的。对于算法题，行为可解释比追求绝对完美更重要。

4. 三道题串起来看：一套可复用的边界条件检查清单

4.1 边界条件自查：做题家的最后一道防线

三道题都写完、样例都通过之后，我建议再做一轮边界条件测试。我给自己列了一个检查清单，每题至少测三种极端情况：

质数题：

• n=1：预期输出“不是质数”
• n=2：预期输出“是质数”，这是唯一一个偶数质数
• n=4：预期输出“不是质数”
• n是很大的质数（比如999983）：验证平方根优化后仍能快速返回

字符串处理题：

• 空字符串：逆序还是空串，过滤后也是空串，大小写转换后还是空串
• 全空格字符串：过滤后变成空串
• 纯标点字符串：过滤后输出空串
• 字符串以'\0'结尾的隐式处理

分割排序题：

• 空串：什么也不输出，不能崩溃
• 单个数字"42"：输出42
• 连续分隔符"5,,3"：输出3 5，不能出现0
• 末尾分隔符"5,3,"：输出3 5
• 前导零"007, 2"：按数值处理则输出2 7
• 重复数字"3, 3, 1"：输出1 3 3，数量不能少

这个清单我建议你也保留一份。算法题最容易死的地方不是逻辑，而是边界条件输入输出不匹配。

4.2 输入输出格式：一半的罚时来自这里

做题时还有一个无形的坑——输入输出格式。很多练习平台对输出格式有严格规定，比如“每个数字之间用一个空格分隔，末尾不能有多余空格”。

末尾多余空格到底会不会被判错？不同平台策略不同，有的严格判错，有的会宽容处理。但保险策略永远是：不输出多余空格。

for (size_t i = 0; i < nums.size(); i++) { if (i > 0) std::cout << ' '; std::cout << nums[i]; } std::cout << std::endl;

这个写法利用了i > 0判断，第一个元素前不输出空格，后面每个元素前补一个空格。这样永远不会有首尾多余空格的问题。类似的逻辑在处理“按行输出结果”“输出特定格式的字符串”时都适用。

如果题目要求“每行输出一个质数”，那就简单多了，直接每行一个输出，不存在分隔符问题。所以读题时先搞清楚输出格式比写代码更重要。我在做day36的时候就因为这个细节浪费了一次提交机会：质数判断没问题，但没注意要求“按空格分隔输出所有质数”，我按每行一个输出了，直接被判错。从那以后，我读题时第一件事就是圈出“输出”那一行。

4.3 算法复杂度选择：先看数据范围再动手

这三道题放在同一天训练，其实也是在教你一个思维习惯：拿到题先看数据范围，再决定用什么算法。

质数题如此，排序题也一样。数据量在千级以内，冒泡排序都能轻松过；数据量到十万级，就必须用O(n log n)的排序了。C++标准库的std::sort是内省排序，综合性能很好，不需要自己造轮子。但如果题目的考察点就是手写排序算法，那你就得按题目要求来，这时候理解每个排序算法的循环不变量和适用场景就显得非常重要了。

我当时做这道题时，特意用Python和C++各写了一遍。Python写起来快很多，但C++对内存和类型的控制更精细，尤其是在字符编码边界问题上，能更明显地看出语言层面的差异。如果时间允许，我建议你也用两种语言各刷一遍同类题目，很多“为什么”会在对比中自己浮出水面。

5. 我做完这三道题之后的三个体会

第一，排序和字符串处理的坑，往往比算法本身的坑多。质数判定用到的是数学思维，但字符串过滤和分割排序用到的是对语言API细节的掌握。很多人在刷题时把精力放在“算法有多高级”上，忽略了API的边界行为，结果一提交就挂。

第二，稳的写法比炫的写法值钱。我最早写的质数判断版本里用的是for(int i = 2; i * i <= n; i++)，这个写法在n超过int范围时可能溢出。后来我在一个开源项目里看到他们用的是for(int i = 2; i <= n / i; i++)，用除法代替乘法彻底避免溢出。这个写法我当时没想到，但它确实是更稳的选择。细节决定成败，这种经验只有多踩坑多对比才能积累下来。

第三，勤用打印调试，别硬看代码。遇到字符串分割后输出不对的情况，第一反应应该是打印每一段分割结果，看看分隔符和空串都是怎么进入数组的，而不是盯着代码逻辑空想。这比反复读代码快得多，尤其是C++里没有现成split的情况下，手写解析逻辑很容易出问题，打印调试能帮你快速定位是分割错了还是转换错了还是排序错了。我那天做第三题时，就是靠连续几行cout打印，才发现自己的标志位判断少处理了一种分隔符情况。

day36这套题目让我重新审视了一遍自己的代码习惯：边界条件检查没做好、API细节掌握不牢、输出格式容易漏看——这三个问题以前都犯过，但一次训练里全部暴露出来，反而是件好事。如果你也在刷类似的组合题，希望这篇记录能帮你少踩几个我踩过的坑。