★ FEATURED ARTICLE 这一天的挑战有点意思——三道题放在一块儿其实正好覆盖了编程里三个最基础也最容易出问题的环节数学逻辑、字符串处理、还有集合操作。质数、翻译字符串、分割数字并排序听起来都是入门题但真上手写的时候你会发现坑全在细节里。我做完这组题之后的感受是题目越简单越能看出一个人平时写代码的习惯。这篇文章就把我当天的完整思路、踩过的坑、以及最终拿出来的解法都记录下来希望能给正在刷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×bn。所以判断n是否为质数只需要检查2到√n之间的整数就够了。为什么这个结论成立因为因子是成对出现的。以n36为例它的因子对是(1,36)、(2,18)、(3,12)、(4,9)、(6,6)。可以看到从6开始因子就开始重复了。所以检查到√n6就够了再往后检查的都是重复工作。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的较小倍数在之前已经被更小的质因子筛过了。比如i5时5×210早被2筛过5×315早被3筛过5×420早被2筛过所以直接从25开始标记就行。这个优化能让筛法在N很大时明显更快实测在N100万时从i×i开始的版本比从2×i开始的版本快大约15%到20%。筛法的整体复杂度是O(n log log n)n100万时大概只需要几十毫秒。我刚才说Combinatorics这类问题里最常用的质数工具就是它不是没道理的。1.4 实际编码中最容易翻车的两个点质数题翻车的地方反而不在算法本身而在边界条件和语言细节。第一个坑是数据类型。判断质数时如果i×i超出int范围就会溢出。比如n是10亿量级时√n大约是31623i×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::reversestd::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_castunsigned char(c))) { result c; } } return result; }这里有一个非常隐蔽的坑isalnum接收的是int类型但标准要求这个int必须能表示为unsigned char或者EOF。如果你直接传入char在有些平台和编译器组合下char是signed类型ASCII码大于127的字符比如中文字符的某个字节、或者扩展字符集里的字符会变成负数传给isalnum就属于未定义行为表现就是过滤结果里出现奇怪的字符或者行为异常。安全做法是显式强转成static_castunsigned 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_castunsigned char(c))) return std::toupper(static_castunsigned char(c)); if (std::isupper(static_castunsigned char(c))) return std::tolower(static_castunsigned 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差异很大用错了真会翻车语言推荐写法注意事项Pythons.split()或s.split(,)默认split会吃掉所有空白字符包括空格、制表符、换行Javas.split(,)参数是正则表达式.要写成\\.Cstd::stringstream或手写遍历标准库没有直接split需要自己封装C#s.Split(,)参数是char数组或string数组不是正则Java的split最容易踩坑它的参数是正则表达式。如果你按.分割直接写123.456.split(.)返回的是空数组因为.在正则里表示任意字符。正确写法是split(\\.)。同样按|分割要写split(\\|)反正只要是正则元字符都得转义。这个问题在面试和笔试题里出现频率极高。C没有内置split函数最简单的做法是用stringstream处理以空白字符分隔的输入#include sstream std::vectorint parse_numbers(const std::string s) { std::vectorint nums; std::stringstream ss(s); int num; while (ss num) { nums.push_back(num); } return nums; }注意stringstream的操作符是按空白字符自动分割的而且会自动跳过前导空白。如果输入是5, 3, 8, 1这种带逗号的格式就无能为力了你需要先把逗号当作分隔符。最稳妥的方法是手写遍历std::vectorint parse_numbers_with_commas(const std::string s) { std::vectorint 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::greaterint()); // 降序但如果你在学算法很容易遇到一个衍生题让你手写排序算法比如选择排序还要你证明它的循环不变量。这正是算法竞赛圈里常说的“CLRS选择排序循环不变量证明”。我当时还真把这段证明过程过了一遍因为它能解释为什么选择排序每一轮交换后前i个元素已经是全局有序的。选择排序的循环不变量是每次外层循环开始时前i个元素已经是整个数组中最小的i个元素且它们已经升序排列。理由有三条初始化i0时前0个元素为空集命题自然成立。保持第i轮内层循环找到从i到末尾的最小值与第i个位置交换。因为前i个元素已经是全局最小的i个剩余部分的所有值都大于等于它们所以第i轮找出的位置i处的新值必然使前i1个元素保持有序且为全局最小前i1个。终止i n-1时前n-1个元素全局有序最后一个元素自然而然也处于正确位置。这个证明不是纸上谈兵。它直接对应了选择排序的行为特征每轮只交换一次最多n-1次交换比较次数固定为n(n-1)/2不管输入是否有序。所以选择排序适合“交换成本高但比较成本低”的场景而冒泡排序和插入排序的行为特征又不一样。你想真正理解排序算法把循环不变量写出来比背代码有用得多。还有一个容易被忽略的问题标准库std::sort是不稳定排序也就是说两个值相等的元素在排序后相对位置不保证保持不变。如果你排序的是std::pairint, int希望按第一个元素排序、第一个元素相同时保持第二个元素的原始顺序就要用std::stable_sort或者自定义比较函数时把第二个元素也纳入比较。不过对于纯数字排序稳定性没有任何影响不需要纠结。3.4 字母数字组合排序谁在什么时候排到你面前刚才提到字典序和数值序的区别这个在“字母数字组合排序”场景下体现得最明显。假设你有一组形如a2、a10、a1的字符串按字典序排序得到的是a1、a10、a2但按“人类直觉”的自然序你期望的是a1、a2、a10。这俩结果不一样。原因就是字符串逐字符比较时1和2的比较发生在0之前a10和a2先比a和a再比1和21小于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 边界条件自查做题家的最后一道防线三道题都写完、样例都通过之后我建议再做一轮边界条件测试。我给自己列了一个检查清单每题至少测三种极端情况质数题n1预期输出“不是质数”n2预期输出“是质数”这是唯一一个偶数质数n4预期输出“不是质数”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 算法复杂度选择先看数据范围再动手这三道题放在同一天训练其实也是在教你一个思维习惯拿到题先看数据范围再决定用什么算法。数据范围推荐方案理由N ≤ 1000平方根优化试除法单次O(√N)总量可接受N ≤ 10^6埃拉托斯特尼筛法O(N log log N)毫秒级N ≤ 10^7筛法内存优化注意内存占用bool数组约10MBN 10^7分段筛法/Miller-Rabin普通筛法内存可能不够质数题如此排序题也一样。数据量在千级以内冒泡排序都能轻松过数据量到十万级就必须用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细节掌握不牢、输出格式容易漏看——这三个问题以前都犯过但一次训练里全部暴露出来反而是件好事。如果你也在刷类似的组合题希望这篇记录能帮你少踩几个我踩过的坑。
阅读完成 · 觉得有帮助？
