字符串算法刷题三大基本功：双指针、步长循环与ACM模式扩容填充

说实话字符串类的算法题在刷题圈里属于最容易被低估的一类。一来题目描述短二来示例简单大多数人瞄一眼就觉得自己会了。可真到训练营第八天把 LeetCode344 反转字符串、LeetCode541 反转字符串 II、卡码网 KamaCoder54 替换数字这三道题放在一起复盘时才发现字符串题想写得干净、稳定、不露边界破绽远比想象中讲究。这三道题表面看都是处理字符序列实际上覆盖了字符串题最核心的三种基本功双指针原地操作、步长循环处理区间、以及扩容后从后往前的反向填充。如果你正在刷题补基础或者准备面试想把手上的字符串题练扎实又或者刚接触 ACM 模式被输入输出搞得头晕这篇文章应该能帮上忙。我会把每道题的解题思路、为什么这样写、以及实测踩过的坑都摊开讲清楚。1. 第八天为什么把这三道题放在一起字符串基本功的三种考验很多人在刷题初期会有个错觉字符串题就是 API 调用题反正语言库里都有现成函数。这个想法在业务开发里没毛病但在算法训练里恰恰是陷阱。训练营把这三道题安排在同一天其实是在用三道题分别敲打三个不同层面的能力。LeetCode344 考的是原地修改。所谓反转字符串核心限制不在反转而在不能用额外空间。这是对双指针手感的直接训练也是后面一系列字符串难题的基础。LeetCode541 考的是规则翻译成循环。题目给了一条看起来有点绕的规则如果你真的按规则一步步 if-else 去模拟很容易写出一堆边界条件。更聪明的做法是找到规则里的周期用一步循环步长解决掉。卡码网54 考的是ACM 模式下的完整处理能力。这道题给了你在 LeetCode 答题框里体会不到的东西自己读输入、自己处理字符串扩容、自己输出结果。而且在解法上从前往后替换和从后往前替换性能差距是 O(n²) 和 O(n) 的差距。三题串起来正好是一条从会写到会想再到会在完整环境里跑通的递进链路。我当时的安排是344 花 20 分钟541 花 30 分钟54 花 40 分钟剩下的时间全部用于把三道题的边界情况列成表格对照。后面会讲这 40 分钟里至少有 15 分钟是耗在调试输入输出上。题号模式核心考点建议投入时间LeetCode344 反转字符串核心代码模式双指针、原地修改20 分钟LeetCode541 反转字符串 II核心代码模式步长循环、区间边界30 分钟卡码网54 替换数字ACM 模式整行 IO、扩容、反向填充40 分钟2. LeetCode344 反转字符串先管住调用 reverse 的手2.1 这道题到底在考什么题目本身特别简单给你一个字符数组要求原地把顺序反转不开辟额外空间。我第一次看到的时候心想这不是 std::reverse 一行的事吗确实std::reverse(s.begin(), s.end())能过但这就失去了训练的意义。训练营提醒得很到位LeetCode344 的本意是让你徒手实现反转逻辑因为后面很多字符串题目里反转是一个中间步骤你不能每次都依赖库函数而且面试时面试官经常会让你手动写一遍反转看看你对索引和边界的敏感度。这道题的关键约束是原地和O(1) 额外空间。所谓原地意味着你只能通过交换字符来改变顺序不能新开一个等长数组再拷贝回去。如果你写过vectorchar ans s;再 reverse 回去本质上还是额外开了一份空间不符合要求。2.2 双指针写法的边界细节思路一句话就能说完左指针指向开头右指针指向结尾交换这两个位置的字符然后左指针右移、右指针左移直到两指针相遇。class Solution { public: void reverseString(vectorchar s) { int left 0; int right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } };这里有个很多人会纠结的点循环条件到底写left right还是left right我建议统一写left right。因为当字符数组长度是偶数时两个指针会错开长度是奇数时中间那个字符本来就不需要动left right的时候再交换一次等于自己换自己纯属多余。两种写法在结果上没有区别但left right更符合直觉也更好解释。如果你喜欢 for 循环风格也可以写成for (int i 0, j s.size() - 1; i j; i, j--) { swap(s[i], s[j]); }Python 版本同理只是注意 Python 的字符串是不可变对象题目输入给的是 list 才能原地修改class Solution: def reverseString(self, s: List[str]) - None: left, right 0, len(s) - 1 while left right: s[left], s[right] s[right], s[left] left 1 right - 12.3 为什么我不建议直接用库函数交差这不是说库函数不好。std::reverse本身封装得很好笔试时该用就用。但作为训练如果你连一次手写反转都没有做过后面做反转单词、反转链表、反转括号内字符串这些变体题时很容易在索引计算上翻车。我的判断标准是这样的如果拿到题目第一反应是这个函数的底层原理是什么那就先手写一遍再说如果第一反应是这题本身就是在考某个库函数的用法那直接调库也合理。344 明显属于前者它是想让你理解双指针而不是考察你是否知道 reverse 函数。另外补充一个小知识点std::reverse接收的是迭代器区间而且是左闭右开区间也就是[begin, end)。这个惯例在 C 里大量出现后面 541 题也会用到所以建议先对左闭右开这个概念熟悉起来。3. LeetCode541 反转字符串 II用循环步长消化复杂规则3.1 先把规则翻译成人话541 题的规则是这样的给定一个字符串 s 和一个整数 k从字符串开头算起每计数至 2k 个字符就反转这 2k 个字符中的前 k 个字符。如果剩余字符少于 k 个则将剩余字符全部反转。如果剩余字符大于等于 k 个但小于 2k 个则反转前 k 个字符其余字符保持不变。乍一看很绕其实可以精简成两句话每 2k 个字符为一组组内前 k 个反转后 k 个不动。最后一组如果凑不满 k 个那就全反转如果凑得满 k 个但凑不满 2k 个依然只反转前 k 个。这里的核心技巧是不要用计数器去数我已经处理了几个字符而是直接在 for 循环里让下标每次跳 2k。这样循环天然把字符串切成了若干个长度为 2k 的段每段独立处理前 k 个字符即可。3.2 步长循环的写法class Solution { public: string reverseStr(string s, int k) { int n s.size(); for (int i 0; i n; i 2 * k) { int left i; // 反转区间是 [i, ik-1]但不能超过字符串末尾 int right min(i k, n) - 1; while (left right) { swap(s[left], s[right]); left; right--; } } return s; } };这段代码最妙的地方在right min(i k, n) - 1。我第一遍看题解的时候没太理解为什么直接减 1后来自己推导了一遍才算彻底明白。左边界是i因为每组起点就是当前循环到的位置。右边界本应该是i k - 1也就是组内前 k 个字符的最后一个。但如果最后一组剩余字符不足 k 个i k - 1就会超出字符串实际长度所以要先用min(i k, n)把右边界截到字符串末尾再减 1 变成合法的数组下标。你可以用一个例子验证s abcdefg, k 2n 7。第一轮 i0right min(2, 7) - 1 1交换下标 0 和 1结果是 bacdefg。第二轮 i4right min(6, 7) - 1 5交换下标 4 和 5结果是 bacdferg。等等bacdferg 只有 7 个字符吗数一下b a c d f e r g确实是 7 个。最后一组从下标 4 开始剩余 efg 共 3 个字符大于等于 k2所以反转前 2 个 ef变成 fe第三字符 g 不动得到 bacdfeg。我上面随手写的顺序打错了你写代码跑一遍就会得到正确结果 bacdfeg。这就是为什么我强烈建议这种题要自己手推一轮眼睛看会了不等于手算对了尤其是边界条件下标特别容易错。3.3 实操中的两类典型错误第一类错误是把简单规则写成分段讨论。比如有同学写if (剩余字符个数 k) { // 反转前 k 个 } else { // 全部反转 }逻辑上没问题但这种写法需要一个额外的变量记录剩余字符数而且每次循环都要重新计算代码变得又长又容易漏情况。比如剩余字符大于等于 k 但小于 2k这种情况用上面的判断也能覆盖但如果你再细分出大于 k 小于 2k和大于 2k的分支就会把很简单的事情搞复杂。第二类错误是min(i k, n)忘减 1。我第一次写的时候用的是while (left right)并且right min(i k, n)结果每次都多交换了一个字符。原因是 right 作为数组下标应该是最后一个有效索引而min(i k, n)其实是下一个段的起点它在语义上对应的是最后一个反转字符的再下一个位置所以必须减 1。如果你实在怕搞混也可以直接用 STL 版本reverse(s.begin() i, s.begin() min(i k, n));这里正好利用了std::reverse左闭右开的特性不需要手动减 1。我建议你先手写双指针逻辑确认理解了边界原理之后笔试时再大胆用这个简化版。4. 卡码网54 替换数字从核心代码模式到 ACM 模式的第一课4.1 ACM 模式暴露的问题输入输出都不会写给你看个真实场景。前七天在 LeetCode 上刷题函数签名都是现成的你只需要把逻辑填进函数体输入早就被平台处理好了。但训练营第八天模拟笔试突然换成卡码网这种 ACM 模式要求你自己写main()、自己读标准输入、自己打印结果很多人的第一反应是懵的。卡码网54 的题目描述是这样的给定一个字符串 s将其中的数字字符替换为 number 字符串。比如输入a1b2c3输出anumberbnumbercnumber。别笑这道题真有不少人挂在读输入上。用cin s还是getline(cin, s)取决于输入是否包含空格。这道题给的字符串不含空格所以cin完全够用。但如果你不确认题目描述保险起见用getline也没毛病#include iostream #include string using namespace std; int main() { string s; cin s; // 主逻辑... cout s endl; return 0; }ACM 模式真正考验的不只是你知道怎么替换而是你能不能在一个没有测试用例逐步提示的环境里把完整程序写对。LeetCode 里你函数返回值对了就行这里你必须自己负责整个程序的生命周期稍有疏忽就是编译错或者格式错。4.2 为什么必须从后往前填充把数字替换成 number直觉上的做法是遍历字符串遇到数字就调用 insert 方法插进去。但这在 C 里是个性能陷阱。std::string::insert会在插入位置把后续字符整体后移最坏情况下每个数字字符插入都导致后面所有字符搬一次家。假设字符串里有一半是数字复杂度会退化到 O(n²)。训练营里反复强调的慎用 insert/erase这就是原因之一。正确的思路分三步先遍历一遍字符串统计数字字符的个数 count。原字符串扩容每个数字替换成 6 个字符的 number所以新长度是oldSize count * 5原来是 1 个字符替换后变 6 个净增 5 个。从后往前填充一个指针 i 指向旧字符串末尾一个指针 j 指向扩容后字符串末尾。遇到数字就反着写入 number遇到普通字符就原样搬过去。代码如下#include iostream #include string using namespace std; int main() { string s; cin s; int oldSize s.size(); int count 0; for (char c : s) { if (c 0 c 9) { count; } } s.resize(oldSize count * 5); int i oldSize - 1; int j s.size() - 1; while (i 0) { if (s[i] 0 s[i] 9) { s[j--] r; s[j--] e; s[j--] b; s[j--] m; s[j--] u; s[j--] n; i--; } else { s[j--] s[i--]; } } cout s endl; return 0; }为什么从后往前填充能避免覆盖因为扩容之后新字符串的末尾一定大于旧字符串的末尾。从后往前处理时j 指针的位置始终在 i 指针的右边也就是说我们写进去的新内容不会碰到还没处理的旧字符。反过来如果从前往后填充每次写入都可能把未处理的旧字符覆盖掉那才真的叫灾难。你可以把它想象成往已经装了一半书的箱子里再塞新书只有先把后半部分腾空从末尾往前一本一本挪才不会把前面的书挤坏。4.3 字符串扩容与填充的易错点这道题有几个坑我挨个说。第一个坑resize之后直接在原字符串上继续遍历。resize会改变s.size()如果你在扩容前没有保存oldSize后面用for (int i 0; i s.size(); i)遍历时会把扩容出来的空字符也当作有效内容处理逻辑直接错乱。所以务必先int oldSize s.size();再统计和扩容。第二个坑填充 number 时的顺序。从后往前写number 要反着写先写 r再写 e再写 b再写 m再写 u最后写 n。很多人写着写着就把s[j--] n; s[j--] u;写成正序结果字符串变成 rebmun调试半天才发现顺序反了。我后来习惯先在注释里写好n u m b e r再对照反序抄写。第三个坑数字字符判断。建议用c 0 c 9不要用isdigit(c)的直接版本。isdigit的参数要求是int且必须是 EOF 或 0-255 之间的值如果字符被当成有符号负数传进去行为就不确定。字符范围比较是最朴素也最安全的方式。如果非要用 Python 写这个题由于字符串不可变最自然的方式是转成 lists input().strip() res [] for c in s: if c.isdigit(): res.append(number) else: res.append(c) print(.join(res))注意这里额外用了一个 list空间是 O(n)。Python 的字符串不可变无法在原字符串上原地扩容这是语言特性决定的面试时说明白即可。5. 三道题合起来复盘字符串题通用法则与踩坑记录5.1 判断能不能用库函数的三条标准这一天的三题做完最值得沉淀的就是什么时候可以调库函数这个判断力。我自己总结了三条标准每次遇到字符串题先快速过一遍这个题的核心考点是库函数本身吗如果是比如考察你知道某个 STL 函数的使用那直接用没问题。手写会不会让我更理解底层如果会哪怕笔试能调库训练时也要手写一遍。344 和 541 都属于这种。面试场景下对方期待的是什么如果面试官明确说你实现一下反转那调reverse就是答非所问。我在 541 题里其实给了一个折中方案手写双指针理解边界最终笔试用std::reverse保证速度和准确率。学习阶段和应试阶段可以有不同的策略关键是你心里清楚每个函数背后做了什么。5.2 实测踩过的两个典型坑第一个坑是resize 之后用 s.size() 做遍历边界。我在写替换数字这道题时一开始统计完 count 就直接s.resize(...)然后想当然地写了一个 for 循环去处理结果把扩容后的空位也遍历进去了。最后靠打印每一步字符串才发现问题。解决方案就是我前面说的先保存oldSize循环和指针都以 oldSize 计算。第二个坑是541 题反转区间右边界算错。我第一次写的是right min(i k, n)然后用while (left right)交换本来只想反转 k 个字符结果因为 left 和 right 都指向有效下标多交换了一个。这个错误很隐蔽因为字符串短的时候结果看起来差不多对直到我用s abcdef, k 2手工推演才暴露。这两个坑我后来都记录在自己的错题本里两周后又遇到类似题明显反应快了很多。强烈建议你也把错的版本和正确版本并排贴在一起下次复习时一眼就能看到差异。5.3 复杂度视角的合并复盘把三道题放在一张表里看题目时间复杂度空间复杂度核心技巧LeetCode344O(n)O(1)双指针左右交换LeetCode541O(n)O(1)步长循环 区间边界截断卡码网54O(n)O(1)扩容 从后往前双指针不难发现三题的共同点都是 O(n) 时间和 O(1) 额外空间。字符串题的复杂度估算有个简单套路如果没有嵌套循环就是线性扫描如果出现 insert/erase 这种需要搬移的操作用法就要警惕退化。你想把空间压到 O(1)本质上都是在原字符串上做交换或迁移动作而不是新建字符串。另外关于“替换数字”这种题我平时练的时候会顺手多想一想如果替换的不是固定长度的 number而是长度不固定的某个变量还能不能从后往前答案是需要先知道新总长度而新总长度往往需要额外遍历一次统计这就是这类题的基本功值得多做两遍形成肌肉记忆。第八天结束之后我把三道题又默默重写了一遍。能有这样的复盘习惯比多刷五道新题更有价值。特别是 54 题我后来在另一个模拟环境里又遇到了几乎一样的替换类题目直接套用从后往前的模板几分钟就写完了连边界都没卡过。这种手感就是靠当天一次次的推演和错题积累出来的。