如果你问我算法训练营第八天有什么特别的我的回答是这一天的三道题单独拿出来都不算难但合在一起却把字符串处理里最重要的三种思维全串起来了。代码随想录把344.反转字符串、541.反转字符串II和替换数字安排在同一天不是随便排的。前者是最基础的双指针应用中间是双指针加上区间划分的进阶后者则是字符串扩容与倒序填充的经典模板。很多朋友刷到这一天会觉得“就这”——字符串反转谁不会但真正动手写能一次通过的人并没有想象中那么多。这天的核心价值不在于题目本身而在于帮你建立三种可复用的思维模型相向双指针、边界条件分析、从后向前覆盖。这三种模型在后面刷题时会反复遇到比如反转字符串里的单词、移动零、链表反转甚至做后端开发时处理大字符串替换都能用上。这篇文章我不只讲题解还会把每道题的易错点、为什么这样写、以及面试官真正想考察什么全部拆开说清楚。如果你是跟着训练营节奏走的新手建议把这天的三道题当作“字符串基本功考核”来对待如果你是有经验的开发者也可以重点看看替换数字那道题的倒序填充思路它在写高性能字符串处理代码时非常实用。1. 思路拆解为什么这三道题安排在同一天1.1 从题目难度看学习路径先看这三道题的定位。344.反转字符串是一道LeetCode简单题要求原地修改字符数组不能开辟额外空间。541.反转字符串II是简单到中等之间的题在反转的基础上增加了“每2k个字符反转前k个”的规则。替换数字则是一道典型的笔试风格题目要求把字符串里的每个数字字符替换成“number”。这个难度梯度是有意设计的。如果你第一天就上手替换数字那种需要预先统计、扩容、倒序填充的题很容易被绕晕。但先做344你掌握了双指针交换的基本功再做541你学会了区间划分和边界判断最后做替换数字你已经有能力理解“为什么要从后往前填充”。这就是代码随想录训练营安排题目的逻辑——每一道题都在给下一道题铺路。很多人在541这道题上翻车不是因为反转逻辑复杂而是因为边界条件处理不熟练。这也是这一天训练的真正目的让你习惯在写循环之前先把所有边界情况列出来而不是写完之后靠调试去猜。1.2 每道题背后的核心思维我把这三道题对应到三种底层思维后面刷题你会不断遇到它们双指针思维用一个左指针和一个右指针从两端向中间逼近或者用两个指针一前一后同步移动。344用到的是相向双指针替换数字用到的是同向双指针。区间划分思维把一个大问题按规则划分成若干小段对每段做独立处理。541的核心不是“怎么反转”而是“怎么正确地切分区间”。扩容与倒序填充思维当字符串长度会发生变化时先扩容到最终大小再从末尾向前填充避免反复插入元素导致移动大量数据。这三种思维都不是只服务这一天的题目。你后面做“反转字符串中的单词”时会发现它是“整体反转局部反转”的组合拳正是344和541思路的叠加做数组相关的题目时双指针更是出场率最高的技巧之一。所以这一天看起来是三道字符串题实际上是在给你后面所有需要处理“区间”和“指针”的题目打底。2. 344.反转字符串双指针思想的第一次正式登场2.1 题目还原与最直观的暴力思路题目要求很简单输入一个字符数组比如[h,e,l,l,o]要求原地反转成[o,l,l,e,h]并且不能使用额外的数组空间。刚接触这道题的人第一反应往往是新开一个数组从后往前遍历填入。这个方案在工程实现上完全没问题但题目明确限制了空间复杂度为O(1)所以必须原地修改。所谓原地就是只允许在输入数组上操作最多使用几个临时变量。另一个朴素思路是通过reverse(s.begin(), s.end())一行搞定。很多新手觉得这是最聪明的做法但在训练营里这样做等于白做。因为这道题考察的就是你知不知道reverse底层是怎么实现的。如果让你把它当作面试手撕题面试官下一句就会问“那你不用库函数手写一个反转给我看看。”所以手写双指针是绕不开的。2.2 双指针解法与三种交换方式的取舍双指针的思路非常直观左边一个指针指向数组开头右边一个指针指向数组末尾交换两个位置的字符然后左指针右移、右指针左移直到两个指针相遇或者错过去。class Solution { public: void reverseString(vectorchar s) { int left 0; int right s.size() - 1; while (left right) { // 交换 left 和 right 指向的字符 char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } } };这里最核心的一段就是交换。我见过不少人在交换上出问题所以展开说一下。最稳妥的写法是用临时变量也就是上面代码里的tmp。这种方式在任何语言里都是通用的不会出错。有人为了炫技用加减法交换两个整数变量a a b; b a - b; a a - b;。这在字符数组上虽然可行但一旦数据量很大存在整数溢出的风险。还有人用异或交换a ^ b; b ^ a; a ^ b;。这种方式看起来很简洁但可读性差面试时容易解释不清而且对新手来说自己写着写着就容易绕晕。我的建议是面试和刷题用临时变量就够了。不要为了“看起来高级”去用异或或者加减法代码是给人读的可读性和正确性永远排在第一位。这道题的时间复杂度是O(n)空间复杂度是O(1)因为只用了常数个临时变量。2.3 库函数到底能不能用关键看考察点关于库函数的使用代码随想录里有一个非常经典的原则如果题目考察的是某个API的底层原理你就不能直接用这个API如果题目本身和库函数无关那用库函数反而能提升效率。用reverse反转字符串就属于第一种情况。面试官出这道题时想知道你懂不懂双指针和原地修改而不是想知道你知不知道有reverse这个函数。所以一旦你在代码里调用了reverse这道题就失去了考察意义。但反过来如果你做的是业务相关的开发比如处理一段文本需要反转某个范围内的字符直接用std::reverse完全没问题。工程师的时间和性能都很宝贵没必要自己造轮子。核心判据只有一个这道题考不考这个函数的底层实现。考就手写不考就放心用。在Java和Python里也有类似的对应操作。Java的Collections.reverse、Python的切片s[::-1]或者reversed()在做项目时都很方便但刷这道题时同样要手写双指针。我见过太多人在面试时习惯性调用库函数然后被面试官追问实现原理最后答不上来非常可惜。3. 541.反转字符串II边界处理才是隐藏考点3.1 题意中的“每2k个”到底怎么理解541的题目描述有点绕给定一个字符串s和一个整数k从字符串开头算起每计数至2k个字符就反转这2k个字符中的前k个字符。我用大白话翻译一下把字符串按2k个一组来划分。对于每一组只反转前k个字符后面k个保持原样。如果最后一组不足k个字符那么把这不足k个的全部反转。如果最后一组大于等于k个但不足2k个那么只反转前k个剩下的不动。看一个官方示例s abcdefg, k 2。此时2k等于4所以第一组是abcd反转前2个字符ab变成ba得到bacd此时已经处理到下标4。剩余字符串是efg长度是3大于等于k且小于2k所以反转前2个字符ef变成fe最终得到bacdfeg。这个题最迷惑人的一点是它并不是“每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) { // 剩余字符大于等于k个反转前k个 if (i k n) { reverse(s.begin() i, s.begin() i k); } else { // 剩余字符不足k个全部反转 reverse(s.begin() i, s.end()); } } return s; } };这个写法里循环变量i每次增加2*k天然地把字符串切成了若干个段。每一轮进入循环时i都是当前段开始的下标。然后检查i k是否还在字符串长度范围内如果在说明当前段至少有k个剩余字符反转[i, ik)如果不在说明不足k个直接把[i, end)全部反转。这里有个容易踩的细节判断条件是i k n而不是i k n。因为当i k n时正好剩k个字符按照题目规则也应该反转前k个所以边界情况要包含等号。我见过不少人是这里写错导致字符串长度刚好是k的整数倍时结果不对。3.3 边界条件的完整推导与实际模拟为了让你真正理解边界我手动模拟两个极端场景。场景一s abcd, k 2。n等于4第一轮i 0i k 2 4所以反转[0, 2)也就是ab变成ba得到bacd。第二轮i 4循环条件i n不成立退出。最终结果是bacd。这里注意虽然字符串正好可以组成一组2k但只反转前k个后面两个字符不参与反转。场景二s abcd, k 5。n等于4第一轮i 0i k 5 4进入else分支把整个字符串反转得到dcba。这对应“剩余字符不足k个全部反转”的规则。如果手写一个通用版本不用C的reverse而是自己实现区间反转核心思想是一样的左指针从区间起点开始右指针从区间终点前一个位置开始相向交换直到相遇。把区间反转封装成一个独立函数reverseRange(s, start, end)会让代码更清晰面试时也更容易和面试官讨论。这个题的另一个常见解法是先把整个字符串切分成数组再用循环处理每组数据。但我觉得那种写法比较绕因为切分本身要处理边界不如直接在原字符串上通过下标操作来得简洁。代码随想录里Carl老师也强调过能用下标原地操作就不要先切分切分操作往往带来额外的空间开销和逻辑复杂度。4. 替换数字从后向前填充的经典模板4.1 最朴素的解法为什么不行替换数字这道题题目要求是给定一个字符串把里面所有的数字字符0到9替换成“number”。比如输入a1b2c3输出anumberbnumbercnumber。先说为什么朴素解法不行。很多人第一次看到这道题第一反应是用一个空字符串遍历原字符串遇到数字就拼接number遇到字母就直接拼接。这种写法没有错结果也是对的。但这道题如果放在面试里通常会有一个附加要求在原有字符串上操作且不开辟新的字符串空间。如果你使用类似string newStr或者StringBuilder来拼接空间复杂度就是O(n)这在一般工程开发中完全没问题。但面试官考察的其实是你能不能做到O(1)额外空间也就是原字符串上原地修改。这时候就有个难题每替换一个数字字符串就会变长直接在原字符串中间插入字母会导致后续所有字符整体后移时间复杂度会退化成O(n²)。如果你用过C语言操作字符数组就会深有体会字符串在内存里是一段连续的空间中间插入内容是很麻烦的。而C的string虽然提供了insert接口但它在内部也是通过移动元素来实现的。所以这道题的正确思路是先扩容再从后往前填充压根不在中间插。4.2 统计、扩容、从后往前填充三步走正确解法分三步。第一步先遍历一遍原字符串统计数字字符的个数。因为我们要预判最终字符串的长度。每个数字字符会被替换成6个字符number而它原来占1个字符所以每个数字会让字符串额外增加5个字符。第二步把字符串扩容到最终长度。C里可以调用resize方法。第三步也是最核心的一步从后往前填充。用一个指针j指向原字符串的末尾一个指针i指向扩容后字符串的末尾然后从后往前遍历。如果当前字符是数字就把number逆序填入i指向的位置及之前的5个位置如果是字母就直接复制到i指向的位置。可能有人会问为什么必须从后往前不能从前往后因为从前往后填充时一旦遇到数字并插入number后面的所有字符都要整体后移产生了大量重复移动。而从后往前填充时每个字符只需要被复制一次时间复杂度是O(n)。这个思路跟“数组原地删除元素时从后往前移动”是一个道理。4.3 完整代码与复杂度对比下面给出一个完整的C实现。这段代码以标准输入输出示例为模板方便你直接本地运行验证。#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; } } // 第二步扩容每个数字多出5个位置 s.resize(oldSize 5 * count); // 第三步从后往前填充 int i s.size() - 1; int j oldSize - 1; while (j 0) { if (s[j] 0 s[j] 9) { s[i] r; s[i - 1] e; s[i - 2] b; s[i - 3] m; s[i - 4] u; s[i - 5] n; i - 6; } else { s[i] s[j]; i--; } j--; } cout s endl; return 0; }我手动验证一下输入a1b2c3统计出3个数字扩容后长度从6变成21。然后倒序遍历从末尾开始遇到3填入number遇到c直接复制遇到2填number遇到b直接复制遇到1填number遇到a直接复制。最终结果是anumberbnumbercnumber完全正确。如果换成正序遍历加insert的写法每次插入的时间复杂度是O(n)n个数字就是O(n²)。而倒序填充只有O(n)。这种优化在日常开发里意义很大尤其是处理大文本或者日志字符串时性能差距会非常明显。代码随想录里还提到过这道题的原型是“替换空格”把空格替换成%20。思路完全一样只是每个空格额外增加2个字符。我建议你把今天替换数字的做法记成模板下次遇到类似“替换”类题目直接套三步走统计变化量、扩容、倒序填充。5. 高频易错点与排查实录5.1 344反转字符串的易错点344这道题看起来简单实际有三个容易被批评的地方。第一个是循环条件写成left right。当字符串长度为偶数时写成小于等于会导致左右指针在中间位置交错之后再交换一次把已经交换好的字符又换回来最终结果等于没有反转。所以正确的写法永远是left right。第二个是忘记更新指针导致死循环。有些新手交换完两个字符后没有写left和right--于是程序在同一个位置反复交换永远跳不出循环。这段代码虽然短但笔试时越简单的题越容易被粗心毁掉。第三个是为了炫技使用异或交换。我之前说过异或交换在数组整数场景下有几率出现隐藏问题字符数组本身也有可读性问题。面试时你写一长串异或面试官第一反应不是觉得你厉害而是觉得你在秀操作、容易埋坑。老老实实用临时变量才是正解。5.2 541反转字符串II的易错点541的易错点主要集中在区间边界判断。最经典的一个错误是循环条件写成了for (int i 0; i s.size(); i)然后每轮用i % (2 * k)去判断当前是否到达反转点。这种写法虽然也能做出来但代码会复杂很多而且很容易在i恰好是k的倍数或者2k的倍数时出错。另一个常见的错误是判断剩余字符是否大于等于k时漏掉了等号。比如写成if (i k n)那么当i k n时等于说剩余正好k个字符按照规则应该反转但你的代码走到了else分支把整个剩余部分反转了。如果剩余部分恰好就是k个那结果一样但如果剩余部分小于k结果就是错的。这种边界错误在测试用例里非常难发现因为大部分常规输入不会卡在这个点上。5.3 替换数字的易错点替换数字这道题的易错点稍微多一些。第一扩容大小容易算错。每个数字变成6个字符原先是1个所以多5个位置不是多6个。我见过有人resize(oldSize 6 * count)结果多了一个空位导致最后输出时多出一个空格或者乱码。第二填充时忘了i - 6。倒序填入number后必须把i往回移动6个位置才能保证下一次写入覆盖到正确的位置。如果忘记减后面写入的内容会覆盖掉刚写的number。第三判断数字字符时要写成s[j] 0 s[j] 9不能直接写s[j] 0 s[j] 9。因为字符数组里存的是字符要和字符的字面值比较。这是新手最常见的错误。第四如果输入字符串里有其他非数字也非字母的情况比如符号、空格要提前想清楚是否需要处理。这道题通常只考字母和数字但面试时可别自己给自己加戏。5.4 这几个考点的面试追问清单最后整理一份面试官经常追问的问题你可以拿来自测344题你为什么要用双指针空间复杂度是多少如果不允许用额外数组你能做到吗541题如果k大于字符串长度你的代码会怎么执行如果k等于0呢会不会死循环替换数字为什么不能用正序插入insert的时间复杂度是多少如果要求不能用resize你还有别的扩容方案吗这些问题并不难但能当场答清楚的候选人说明他是真的理解了代码背后的逻辑而不是背答案。我强烈建议你在刷完当天的题之后闭上眼睛把每道题的思路和代码流程口述一遍。能说清楚才是真的会了。6. 训练营第八天的沉淀与后续延伸6.1 三道题的内在逻辑串联这三道题表面上是三个独立题目实际上是一条完整的训练链条。344让你学会用双指针原地修改字符数组的顺序。541在此基础上加入了“分段处理”规则让你学会在循环里灵活控制步长并且正确判断每一段的边界。替换数字则更进一步让你在面对字符串长度动态变化时用统计加扩容加倒序填充的思路把复杂度从O(n²)降到O(n)。如果你把这三道题融会贯通你就会发现一个普遍的规律只要涉及到字符串的区间操作先画坐标、列边界、再写循环基本不会出错。这个习惯比背任何模板都重要。6.2 接下来你可以继续挑战的题目如果第八天的题你已经完全掌握了我建议你马上去做以下几道题检验一下今天学到的东西剑指Offer 05替换空格。和替换数字几乎一样把空格替换成%20正好练习同一个模板。151.反转字符串中的单词。这道题是今天的终极应用先整体反转整个字符串再逐个单词反转组合了344和541的思路。27.移除元素。数组版的双指针移动问题和替换数字的倒序填充思路有异曲同工之妙。我个人在实际操作中的体会是刷题最忌讳的是“看过题解觉得自己会了”。代码随想录训练营之所以强调“卡码网”上去重复提交就是让你逼自己脱离题解把代码写出来。以第八天的三道题为例你哪怕只看懂了解析亲手写一遍也很可能会在541的等号、替换数字的扩容大小上卡住。卡住是好事卡住说明你找到了自己的知识盲区。最后再分享一个小技巧每天刷完题之后花十分钟用纸笔画一下这三道题的数据变化过程。画的时候不要偷懒把每一步交换、每一个指针位置都标出来。把图画顺了代码自然就写得顺。这个习惯我保持了很长时间对复杂边界问题的理解帮助非常大。
字符串处理三题串讲：双指针、边界判断与倒序填充的算法思维
如果你问我算法训练营第八天有什么特别的我的回答是这一天的三道题单独拿出来都不算难但合在一起却把字符串处理里最重要的三种思维全串起来了。代码随想录把344.反转字符串、541.反转字符串II和替换数字安排在同一天不是随便排的。前者是最基础的双指针应用中间是双指针加上区间划分的进阶后者则是字符串扩容与倒序填充的经典模板。很多朋友刷到这一天会觉得“就这”——字符串反转谁不会但真正动手写能一次通过的人并没有想象中那么多。这天的核心价值不在于题目本身而在于帮你建立三种可复用的思维模型相向双指针、边界条件分析、从后向前覆盖。这三种模型在后面刷题时会反复遇到比如反转字符串里的单词、移动零、链表反转甚至做后端开发时处理大字符串替换都能用上。这篇文章我不只讲题解还会把每道题的易错点、为什么这样写、以及面试官真正想考察什么全部拆开说清楚。如果你是跟着训练营节奏走的新手建议把这天的三道题当作“字符串基本功考核”来对待如果你是有经验的开发者也可以重点看看替换数字那道题的倒序填充思路它在写高性能字符串处理代码时非常实用。1. 思路拆解为什么这三道题安排在同一天1.1 从题目难度看学习路径先看这三道题的定位。344.反转字符串是一道LeetCode简单题要求原地修改字符数组不能开辟额外空间。541.反转字符串II是简单到中等之间的题在反转的基础上增加了“每2k个字符反转前k个”的规则。替换数字则是一道典型的笔试风格题目要求把字符串里的每个数字字符替换成“number”。这个难度梯度是有意设计的。如果你第一天就上手替换数字那种需要预先统计、扩容、倒序填充的题很容易被绕晕。但先做344你掌握了双指针交换的基本功再做541你学会了区间划分和边界判断最后做替换数字你已经有能力理解“为什么要从后往前填充”。这就是代码随想录训练营安排题目的逻辑——每一道题都在给下一道题铺路。很多人在541这道题上翻车不是因为反转逻辑复杂而是因为边界条件处理不熟练。这也是这一天训练的真正目的让你习惯在写循环之前先把所有边界情况列出来而不是写完之后靠调试去猜。1.2 每道题背后的核心思维我把这三道题对应到三种底层思维后面刷题你会不断遇到它们双指针思维用一个左指针和一个右指针从两端向中间逼近或者用两个指针一前一后同步移动。344用到的是相向双指针替换数字用到的是同向双指针。区间划分思维把一个大问题按规则划分成若干小段对每段做独立处理。541的核心不是“怎么反转”而是“怎么正确地切分区间”。扩容与倒序填充思维当字符串长度会发生变化时先扩容到最终大小再从末尾向前填充避免反复插入元素导致移动大量数据。这三种思维都不是只服务这一天的题目。你后面做“反转字符串中的单词”时会发现它是“整体反转局部反转”的组合拳正是344和541思路的叠加做数组相关的题目时双指针更是出场率最高的技巧之一。所以这一天看起来是三道字符串题实际上是在给你后面所有需要处理“区间”和“指针”的题目打底。2. 344.反转字符串双指针思想的第一次正式登场2.1 题目还原与最直观的暴力思路题目要求很简单输入一个字符数组比如[h,e,l,l,o]要求原地反转成[o,l,l,e,h]并且不能使用额外的数组空间。刚接触这道题的人第一反应往往是新开一个数组从后往前遍历填入。这个方案在工程实现上完全没问题但题目明确限制了空间复杂度为O(1)所以必须原地修改。所谓原地就是只允许在输入数组上操作最多使用几个临时变量。另一个朴素思路是通过reverse(s.begin(), s.end())一行搞定。很多新手觉得这是最聪明的做法但在训练营里这样做等于白做。因为这道题考察的就是你知不知道reverse底层是怎么实现的。如果让你把它当作面试手撕题面试官下一句就会问“那你不用库函数手写一个反转给我看看。”所以手写双指针是绕不开的。2.2 双指针解法与三种交换方式的取舍双指针的思路非常直观左边一个指针指向数组开头右边一个指针指向数组末尾交换两个位置的字符然后左指针右移、右指针左移直到两个指针相遇或者错过去。class Solution { public: void reverseString(vectorchar s) { int left 0; int right s.size() - 1; while (left right) { // 交换 left 和 right 指向的字符 char tmp s[left]; s[left] s[right]; s[right] tmp; left; right--; } } };这里最核心的一段就是交换。我见过不少人在交换上出问题所以展开说一下。最稳妥的写法是用临时变量也就是上面代码里的tmp。这种方式在任何语言里都是通用的不会出错。有人为了炫技用加减法交换两个整数变量a a b; b a - b; a a - b;。这在字符数组上虽然可行但一旦数据量很大存在整数溢出的风险。还有人用异或交换a ^ b; b ^ a; a ^ b;。这种方式看起来很简洁但可读性差面试时容易解释不清而且对新手来说自己写着写着就容易绕晕。我的建议是面试和刷题用临时变量就够了。不要为了“看起来高级”去用异或或者加减法代码是给人读的可读性和正确性永远排在第一位。这道题的时间复杂度是O(n)空间复杂度是O(1)因为只用了常数个临时变量。2.3 库函数到底能不能用关键看考察点关于库函数的使用代码随想录里有一个非常经典的原则如果题目考察的是某个API的底层原理你就不能直接用这个API如果题目本身和库函数无关那用库函数反而能提升效率。用reverse反转字符串就属于第一种情况。面试官出这道题时想知道你懂不懂双指针和原地修改而不是想知道你知不知道有reverse这个函数。所以一旦你在代码里调用了reverse这道题就失去了考察意义。但反过来如果你做的是业务相关的开发比如处理一段文本需要反转某个范围内的字符直接用std::reverse完全没问题。工程师的时间和性能都很宝贵没必要自己造轮子。核心判据只有一个这道题考不考这个函数的底层实现。考就手写不考就放心用。在Java和Python里也有类似的对应操作。Java的Collections.reverse、Python的切片s[::-1]或者reversed()在做项目时都很方便但刷这道题时同样要手写双指针。我见过太多人在面试时习惯性调用库函数然后被面试官追问实现原理最后答不上来非常可惜。3. 541.反转字符串II边界处理才是隐藏考点3.1 题意中的“每2k个”到底怎么理解541的题目描述有点绕给定一个字符串s和一个整数k从字符串开头算起每计数至2k个字符就反转这2k个字符中的前k个字符。我用大白话翻译一下把字符串按2k个一组来划分。对于每一组只反转前k个字符后面k个保持原样。如果最后一组不足k个字符那么把这不足k个的全部反转。如果最后一组大于等于k个但不足2k个那么只反转前k个剩下的不动。看一个官方示例s abcdefg, k 2。此时2k等于4所以第一组是abcd反转前2个字符ab变成ba得到bacd此时已经处理到下标4。剩余字符串是efg长度是3大于等于k且小于2k所以反转前2个字符ef变成fe最终得到bacdfeg。这个题最迷惑人的一点是它并不是“每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) { // 剩余字符大于等于k个反转前k个 if (i k n) { reverse(s.begin() i, s.begin() i k); } else { // 剩余字符不足k个全部反转 reverse(s.begin() i, s.end()); } } return s; } };这个写法里循环变量i每次增加2*k天然地把字符串切成了若干个段。每一轮进入循环时i都是当前段开始的下标。然后检查i k是否还在字符串长度范围内如果在说明当前段至少有k个剩余字符反转[i, ik)如果不在说明不足k个直接把[i, end)全部反转。这里有个容易踩的细节判断条件是i k n而不是i k n。因为当i k n时正好剩k个字符按照题目规则也应该反转前k个所以边界情况要包含等号。我见过不少人是这里写错导致字符串长度刚好是k的整数倍时结果不对。3.3 边界条件的完整推导与实际模拟为了让你真正理解边界我手动模拟两个极端场景。场景一s abcd, k 2。n等于4第一轮i 0i k 2 4所以反转[0, 2)也就是ab变成ba得到bacd。第二轮i 4循环条件i n不成立退出。最终结果是bacd。这里注意虽然字符串正好可以组成一组2k但只反转前k个后面两个字符不参与反转。场景二s abcd, k 5。n等于4第一轮i 0i k 5 4进入else分支把整个字符串反转得到dcba。这对应“剩余字符不足k个全部反转”的规则。如果手写一个通用版本不用C的reverse而是自己实现区间反转核心思想是一样的左指针从区间起点开始右指针从区间终点前一个位置开始相向交换直到相遇。把区间反转封装成一个独立函数reverseRange(s, start, end)会让代码更清晰面试时也更容易和面试官讨论。这个题的另一个常见解法是先把整个字符串切分成数组再用循环处理每组数据。但我觉得那种写法比较绕因为切分本身要处理边界不如直接在原字符串上通过下标操作来得简洁。代码随想录里Carl老师也强调过能用下标原地操作就不要先切分切分操作往往带来额外的空间开销和逻辑复杂度。4. 替换数字从后向前填充的经典模板4.1 最朴素的解法为什么不行替换数字这道题题目要求是给定一个字符串把里面所有的数字字符0到9替换成“number”。比如输入a1b2c3输出anumberbnumbercnumber。先说为什么朴素解法不行。很多人第一次看到这道题第一反应是用一个空字符串遍历原字符串遇到数字就拼接number遇到字母就直接拼接。这种写法没有错结果也是对的。但这道题如果放在面试里通常会有一个附加要求在原有字符串上操作且不开辟新的字符串空间。如果你使用类似string newStr或者StringBuilder来拼接空间复杂度就是O(n)这在一般工程开发中完全没问题。但面试官考察的其实是你能不能做到O(1)额外空间也就是原字符串上原地修改。这时候就有个难题每替换一个数字字符串就会变长直接在原字符串中间插入字母会导致后续所有字符整体后移时间复杂度会退化成O(n²)。如果你用过C语言操作字符数组就会深有体会字符串在内存里是一段连续的空间中间插入内容是很麻烦的。而C的string虽然提供了insert接口但它在内部也是通过移动元素来实现的。所以这道题的正确思路是先扩容再从后往前填充压根不在中间插。4.2 统计、扩容、从后往前填充三步走正确解法分三步。第一步先遍历一遍原字符串统计数字字符的个数。因为我们要预判最终字符串的长度。每个数字字符会被替换成6个字符number而它原来占1个字符所以每个数字会让字符串额外增加5个字符。第二步把字符串扩容到最终长度。C里可以调用resize方法。第三步也是最核心的一步从后往前填充。用一个指针j指向原字符串的末尾一个指针i指向扩容后字符串的末尾然后从后往前遍历。如果当前字符是数字就把number逆序填入i指向的位置及之前的5个位置如果是字母就直接复制到i指向的位置。可能有人会问为什么必须从后往前不能从前往后因为从前往后填充时一旦遇到数字并插入number后面的所有字符都要整体后移产生了大量重复移动。而从后往前填充时每个字符只需要被复制一次时间复杂度是O(n)。这个思路跟“数组原地删除元素时从后往前移动”是一个道理。4.3 完整代码与复杂度对比下面给出一个完整的C实现。这段代码以标准输入输出示例为模板方便你直接本地运行验证。#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; } } // 第二步扩容每个数字多出5个位置 s.resize(oldSize 5 * count); // 第三步从后往前填充 int i s.size() - 1; int j oldSize - 1; while (j 0) { if (s[j] 0 s[j] 9) { s[i] r; s[i - 1] e; s[i - 2] b; s[i - 3] m; s[i - 4] u; s[i - 5] n; i - 6; } else { s[i] s[j]; i--; } j--; } cout s endl; return 0; }我手动验证一下输入a1b2c3统计出3个数字扩容后长度从6变成21。然后倒序遍历从末尾开始遇到3填入number遇到c直接复制遇到2填number遇到b直接复制遇到1填number遇到a直接复制。最终结果是anumberbnumbercnumber完全正确。如果换成正序遍历加insert的写法每次插入的时间复杂度是O(n)n个数字就是O(n²)。而倒序填充只有O(n)。这种优化在日常开发里意义很大尤其是处理大文本或者日志字符串时性能差距会非常明显。代码随想录里还提到过这道题的原型是“替换空格”把空格替换成%20。思路完全一样只是每个空格额外增加2个字符。我建议你把今天替换数字的做法记成模板下次遇到类似“替换”类题目直接套三步走统计变化量、扩容、倒序填充。5. 高频易错点与排查实录5.1 344反转字符串的易错点344这道题看起来简单实际有三个容易被批评的地方。第一个是循环条件写成left right。当字符串长度为偶数时写成小于等于会导致左右指针在中间位置交错之后再交换一次把已经交换好的字符又换回来最终结果等于没有反转。所以正确的写法永远是left right。第二个是忘记更新指针导致死循环。有些新手交换完两个字符后没有写left和right--于是程序在同一个位置反复交换永远跳不出循环。这段代码虽然短但笔试时越简单的题越容易被粗心毁掉。第三个是为了炫技使用异或交换。我之前说过异或交换在数组整数场景下有几率出现隐藏问题字符数组本身也有可读性问题。面试时你写一长串异或面试官第一反应不是觉得你厉害而是觉得你在秀操作、容易埋坑。老老实实用临时变量才是正解。5.2 541反转字符串II的易错点541的易错点主要集中在区间边界判断。最经典的一个错误是循环条件写成了for (int i 0; i s.size(); i)然后每轮用i % (2 * k)去判断当前是否到达反转点。这种写法虽然也能做出来但代码会复杂很多而且很容易在i恰好是k的倍数或者2k的倍数时出错。另一个常见的错误是判断剩余字符是否大于等于k时漏掉了等号。比如写成if (i k n)那么当i k n时等于说剩余正好k个字符按照规则应该反转但你的代码走到了else分支把整个剩余部分反转了。如果剩余部分恰好就是k个那结果一样但如果剩余部分小于k结果就是错的。这种边界错误在测试用例里非常难发现因为大部分常规输入不会卡在这个点上。5.3 替换数字的易错点替换数字这道题的易错点稍微多一些。第一扩容大小容易算错。每个数字变成6个字符原先是1个所以多5个位置不是多6个。我见过有人resize(oldSize 6 * count)结果多了一个空位导致最后输出时多出一个空格或者乱码。第二填充时忘了i - 6。倒序填入number后必须把i往回移动6个位置才能保证下一次写入覆盖到正确的位置。如果忘记减后面写入的内容会覆盖掉刚写的number。第三判断数字字符时要写成s[j] 0 s[j] 9不能直接写s[j] 0 s[j] 9。因为字符数组里存的是字符要和字符的字面值比较。这是新手最常见的错误。第四如果输入字符串里有其他非数字也非字母的情况比如符号、空格要提前想清楚是否需要处理。这道题通常只考字母和数字但面试时可别自己给自己加戏。5.4 这几个考点的面试追问清单最后整理一份面试官经常追问的问题你可以拿来自测344题你为什么要用双指针空间复杂度是多少如果不允许用额外数组你能做到吗541题如果k大于字符串长度你的代码会怎么执行如果k等于0呢会不会死循环替换数字为什么不能用正序插入insert的时间复杂度是多少如果要求不能用resize你还有别的扩容方案吗这些问题并不难但能当场答清楚的候选人说明他是真的理解了代码背后的逻辑而不是背答案。我强烈建议你在刷完当天的题之后闭上眼睛把每道题的思路和代码流程口述一遍。能说清楚才是真的会了。6. 训练营第八天的沉淀与后续延伸6.1 三道题的内在逻辑串联这三道题表面上是三个独立题目实际上是一条完整的训练链条。344让你学会用双指针原地修改字符数组的顺序。541在此基础上加入了“分段处理”规则让你学会在循环里灵活控制步长并且正确判断每一段的边界。替换数字则更进一步让你在面对字符串长度动态变化时用统计加扩容加倒序填充的思路把复杂度从O(n²)降到O(n)。如果你把这三道题融会贯通你就会发现一个普遍的规律只要涉及到字符串的区间操作先画坐标、列边界、再写循环基本不会出错。这个习惯比背任何模板都重要。6.2 接下来你可以继续挑战的题目如果第八天的题你已经完全掌握了我建议你马上去做以下几道题检验一下今天学到的东西剑指Offer 05替换空格。和替换数字几乎一样把空格替换成%20正好练习同一个模板。151.反转字符串中的单词。这道题是今天的终极应用先整体反转整个字符串再逐个单词反转组合了344和541的思路。27.移除元素。数组版的双指针移动问题和替换数字的倒序填充思路有异曲同工之妙。我个人在实际操作中的体会是刷题最忌讳的是“看过题解觉得自己会了”。代码随想录训练营之所以强调“卡码网”上去重复提交就是让你逼自己脱离题解把代码写出来。以第八天的三道题为例你哪怕只看懂了解析亲手写一遍也很可能会在541的等号、替换数字的扩容大小上卡住。卡住是好事卡住说明你找到了自己的知识盲区。最后再分享一个小技巧每天刷完题之后花十分钟用纸笔画一下这三道题的数据变化过程。画的时候不要偷懒把每一步交换、每一个指针位置都标出来。把图画顺了代码自然就写得顺。这个习惯我保持了很长时间对复杂边界问题的理解帮助非常大。
