最近在跟着一个算法训练营刷题做到第7天了今天集中解决的是三道字符串题344反转字符串、541反转字符串II还有一个变种题“替换数字”。说实话这三道题难度都不算高但放在一起刷完回头看非常有收获。它们把字符串操作里最常见的几个坑——原地修改、边界处理、长度变化、从后往前覆盖——全给串起来了。这篇文章我就以过来人的身份把这三道题的思路、代码、踩坑记录完整写一遍希望能给正在刷题的朋友一点参考尤其是那些刚开始接触字符串题、总在边界条件上翻车的小伙伴。1. 整体思路与题量安排1.1 三道题的定位与联系先说这三道题分别是什么。反转字符串是LeetCode的第一道数组/字符串题要求把一个字符数组原地反转不能用额外的数组空间。它考验的是最基础的双指针思想也是很多后续题目的“底子”。反转字符串II是344的升级版。题目标题很唬人实际规则是给定一个字符串s和一个整数k对字符串每隔2k个字符的前k个字符进行反转如果剩余字符少于k个则全部反转如果剩余字符小于2k但大于等于k个则反转前k个剩下的保持原状。这就是一道带条件的区间反转题核心考点在“如何把规则翻译成循环不变量”。第三题不一样有的题库里叫“替换数字”实际上是“将字符串中的所有数字字符替换为number”。比如输入a1b2c3输出a numberb numberc number。这个题和传统“替换空格”非常像核心考察点是已知要扩容的字符串如何高效地从后往前填充避免频繁插入导致的O(n²)开销。这三道题放在一起恰好是“基础反转 → 条件反转 → 长度变化替换”的递进关系。刷的时候明显能感觉到前一道题的动作会成为后一道题的基础动作比如541就是“控制区间分段调用双指针反转”。1.2 为什么字符串类题目适合练手很多人刷题喜欢一上来就啃动态规划、图论这些硬骨头结果就是三天打鱼两天晒网。我反而觉得字符串基础题是最适合早期稳定节奏的原因很简单第一字符串题通常不需要引入复杂的抽象数据结构你手里就一个数组或者一个string操作直观调试容易。第二字符串题特别考“细节”。数组题越界你可能一眼能看出来字符串题因为涉及字符下标、长度变化、拼接顺序边界条件一旦写错表现得往往不是报错而是输出结果莫名多一个空格或者少一个字符这种问题更难排查。第三字符串题和实际业务往往很近比如参数校验、模板渲染、日志处理天天都在跟字符串打交道。把这些算法题练明白写业务代码的时候会下意识地考虑复杂度对转义、拼接、复制的理解也会更深。所以如果你的训练营也把字符串题排在前期那就耐心跟着节奏走。相信我这三道题吃透后面遇到“反转链表”“反转区间”这类二重循环结构你会有一种“似曾相识”的感觉。2. 344. 反转字符串2.1 题目要求与双指针解法344题的表象是“反转字符串”其实考察的是原地修改数组的能力。题面说“输入一个字符数组”必须原地修改意味着你不能new一个新的字符数组再把内容倒着放进去。空间复杂度要求O(1)。双指针解法大家都会写左指针指向开头右指针指向末尾交换两个位置的字符然后左指针右移右指针左移直到两个指针相遇或者交错。交换的时候可以用临时变量也可以直接调swap函数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 - 1C版本也非常简洁class Solution { public: void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } };这里有一个很多新手都会纠结的点循环条件写while(left right)还是while(left right)实际无所谓对于两个不同元素交换left right时交换同一个元素等于没交换所以两种写法结果一致。但习惯上写left right因为当数组长度为奇数时中间那个字符不需要动当长度为偶数时left right保证所有对称位置都交换完。2.2 面试中的易错点与语言差异这道题虽简单面试官往往会在上面加戏。比如他问你“能不能直接调用语言内置的reverse函数”你要是说能他可能就不让你写了直接说“好下一题”。因为这道题的本意就是考察你有没有意识到不能取巧。我们刷训练营时也是同样的态度就算语言有内置API也先自己实现一遍等完全理解原理以后再看API是怎么封装的。另外要注意LeetCode上这道题给的是List[str]也就是一个字符列表不是字符串。为什么特意设计成列表正是因为Python的字符串是不可变对象你没法原地修改。如果题目给的是字符串你就要先把字符串转成列表操作完再拼回来这就不符合O(1)空间的要求了。这一点在很多面试里会被单独拎出来问如果输入是Python字符串你怎么反转答案是s s[::-1] # 利用切片创建新字符串O(n)空间但这不是这道题要求的。如果面试官要求原地且输入是字符串那说明他可能希望你用bytearray或者字符串拼接的方式不过这种讨论已经超出基础题范畴了。记住一点看到“原地修改”四个字首先确定数据类型是否可变再决定能不能做。实际上我第一次写这道题的时候还犯过一个低级错误——交换字符时直接写left 1忘了更新right - 1结果死循环把训练营的打卡页面都刷白了。从此我养成习惯写双指针循环的第一时间就把两个指针的更新语句写全不要觉得“后面再补”没关系。3. 541. 反转字符串II3.1 题意理解每2k个字符反转前k个541题第一次见很容易被绕晕。题目描述很绕“每隔2k个字符反转这2k个字符中的前k个字符如果剩余字符少于k个反转所有剩余字符如果剩余字符大于等于k但小于2k个反转前k个其余不动。”我用个更直白的方式解释你把字符串按照2k为一组来切片。对于每一组只反转这组中的前k个字符后半段原样保留。如果最后一组不足2k但要分类讨论最后一组的字符总数小于k把这整组都反转。最后一组的字符总数大于等于k但小于2k只反转前k个后面的不动。举例说明。字符串abcdefgk2。2k4。前4个是abcd反转前2个得到bacd。剩余从索引4开始是efg字符总数3大于等于k(2)但小于2k(4)因此反转前2个ef得到feg。最终结果是bacdfeg。这个例子里LeetCode题解也有我刷的时候手动推了三四遍才算真正搞懂。另一种理解方式是把字符串看作多个长度2k的小节每个小节内只处理前半段。循环的步长设为2k而不是k这个设定特别关键。很多人第一反应是步长设为k然后反转当前k个、跳过下一个k个、再反转下一个k个这样逻辑也能做但步长设置为2k会让代码更贴近题意不容易错。3.2 边界条件与模拟循环的实现按照2k步长来遍历循环内需要处理的就是“当前位置i到ik-1”这段区间。但这里有一个边界问题如果字符串最后剩余部分不足k个那我们反转到字符串末尾就停如果剩余部分至少k个那就只反转前k个。怎么判断呢可以用min(i k, n)表示要反转的区间的右边界不含。比如当前起点i0k2n7那么反转区间就是[0, min(2,7))也就是[0,2)反转两个字符。再来起点i4反转区间是[4, min(6,7))也就是[4,6)反转两个字符。如果n很小比如n3k2起点i0min(2,3)2反转[0,2)剩余1个字符不动这就符合“剩余字符小于k时反转全部剩余”吗不对剩余是c只有一个字符小于k应该反转剩余全部也就是反转c自己。如果我们用min(ik,n)作为右边界反转区间是[0,2)剩余索引2“c”没有反转。看起来不符合“反转所有剩余字符”的要求让我们仔细看看。题目说“如果剩余字符少于 k 个反转所有剩余字符”。这里“剩余字符”指的是从当前位置i开始到最后的所有字符。当i0k2n3时剩余字符是3个并不少于k(2)。所以应该反转前k个剩余1个不动。只有当i位置到最后的总长度少于k时才全部反转。所以min(ik, n)区间反转是成立的吗假如n4k2i2剩余2个字符不少于k所以应该反转前k个也就是全部剩余反转[2,4)。min(4,4)4区间[2,4)反转2个。没错。再看n1k2i0剩余1个字符少于k应该反转全部也就是反转[0,1)。min(2,1)1区间[0,1)。正确。所以使用min(ik, n)作为右边界是对的。前面n3k2min(2,3)2反转[0,2)剩余[2,3]一个字符因为剩余总数3k所以不应该反转剩余的全部。所以正确。还是用min没错。注意我们需要反转的区间是左闭右开[i, ik)与[i,n)的交集也就是[i, min(ik,n))。所以核心代码是class Solution: def reverseStr(self, s: str, k: int) - str: chars list(s) n len(chars) for i in range(0, n, 2 * k): left i right min(i k - 1, n - 1) # 反转区间的右端点包含 while left right: chars[left], chars[right] chars[right], chars[left] left 1 right - 1 return .join(chars)用右端点包含的写法right min(i k - 1, n - 1)这样区间就是[left, right]好理解。或者用右开区间right min(i k, n) for j in range(i, (i right) // 2): # 但这样可能不直观我推荐用右闭区间因为边界更直观。不过要注意如果i k - 1比i还小怎么办不可能因为k大于等于1i处至少有一个字符。所以区间至少包含一个元素不会出现leftright。其实这道题也可以把反转逻辑抽成一个单独函数因为本质上就是多次调用344题的双指针反转。面试时这样写还能体现模块化思维def reverse_range(chars, l, r): while l r: chars[l], chars[r] chars[r], chars[l] l 1 r - 1然后在主循环调用。我刷这道题踩的坑是一开始把循环步长写成了k然后用一个布尔变量flag控制“这个k反不反转”结果代码写出来又多又乱还容易在最后一组出错。后来想明白直接用步长2k完全不需要flag。这件事对我的启发是有时候问题复杂是因为你选择的步长和题目描述的粒度不一致。题目天然以2k为一个单元那就顺着它的粒度来。还有一个很容易犯的错Python里字符串不可变所以必须先把s转成list否则直接对s操作就会报TypeError: str object does not support item assignment。这句话我在训练营答疑群里至少看到过5次。新手最好记一下Python字符串和C的string不一样C的string可以修改Python的str不能。所以看到LeetCode上输入是字符串、输出也是字符串的题目千万别忘了先转列表最后再拼接。4. 54. 替换数字4.1 字符串的不可变性陷阱第三题“替换数字”其实是代码随想录里的经典扩展题题意是请你写一个函数输入一个字符串把其中所有的数字字符0-9替换成字符串number。比如输入a1b2c3输出a numberb numberc number。注意这里说的“数字”是单个字符不是连续的多位数字。如果输入是a12b输出是a numbernumberb因为1和2是两个数字字符每个都要替换。这个题最简单的写法是def replace_numbers(s: str) - str: result [] for ch in s: if 0 ch 9: result.append(number) else: result.append(ch) return .join(result)时间复杂度O(n)空间复杂度O(n)。这在大多数实际场景已经足够好了。但为什么很多训练营和教材还要讲“从后往前替换”的操作因为这道题的前身是“替换空格”在C语言或C环境中字符串是一个字符数组面试官可能要求你在原数组上进行扩容替换不借助额外数组。这时候如果你从前往后替换每遇到一个数字就要把后续所有字符往后移动时间复杂度会退化成O(n²)。掌握从后往前替换的思路本质是理解“已知扩容大小如何原地更新”的套路。即使你平时用Python不关心原数组学会这种思路也能帮你更深刻地理解为什么字符串操作要尽量避免频繁插入。4.2 从后往前替换的经典做法就在想一下如果我们手上是一个容量足够大的字符数组比如原来长度为n数字一共有cnt个每个数字变成6个字符的number那么新数组总长度为n cnt * 5因为每个数字从1个字符变成6个字符长度增加5。从后往前替换的步骤如下先扫描一遍字符串统计数字字符的个数cnt。设置新长度new_len n cnt * 5。设置两个指针old_index指向原字符串末尾n - 1new_index指向新字符串末尾new_len - 1。从后往前遍历原字符串如果当前字符不是数字直接把它复制到new_index位置两个指针都往前移1。如果当前字符是数字则依次从后往前填入number这6个字符。具体来说new_index依次填入r、e、b、m、u、n倒着填然后old_index往前移1new_index往前移6。C实现大致长这样void replaceNumber(string s) { int count 0; for (char c : s) { if (c 0 c 9) count; } int old_index s.size() - 1; s.resize(s.size() count * 5); int new_index s.size() - 1; while (old_index 0) { if (s[old_index] 0 || s[old_index] 9) { s[new_index--] s[old_index--]; } else { s[new_index--] r; s[new_index--] e; s[new_index--] b; s[new_index--] m; s[new_index--] u; s[new_index--] n; old_index--; } } }注意倒着填的时候顺序别搞错。你要让整个替换完成后字符串顺序正确从后往前填最后一个字符r应该最先出现在新字符串的末尾所以先填r再往前填e依此类推最后填n。我一开始写成顺序填结果字符串变成了rebmun看起来就像“number”倒着写。这个错误非常经典值得记在小本本上。那么Python里能做原地的类似操作吗严格来说Python字符串不可变做不到C那样在同一个字符串上resize。但我们可以用列表模拟类似过程def replace_number(s: str) - str: cnt sum(ch.isdigit() for ch in s) chars list(s) old_idx len(chars) - 1 chars.extend([] * (cnt * 5)) new_idx len(chars) - 1 while old_idx 0: if 0 chars[old_idx] 9: for ch in reversed(number): chars[new_idx] ch new_idx - 1 old_idx - 1 else: chars[new_idx] chars[old_idx] new_idx - 1 old_idx - 1 return .join(chars)上面的reversed(number)正好就是r,e,b,m,u,n逻辑清晰。不过说实话在Python中实际刷题时直接用开头那种列表拼接最快很少需要自虐式地从后往前写。但面试时如果面试官问你“原字符串是一个可变的数组你怎么做到O(1)空间”你就得拿出从后往前的方案。所以两种方案最好都掌握至少能讲清楚“从后往前为什么能避免反复移动”的复杂度分析。另一个值得留意的点是统计数字个数时有人会写成if ch 0 and ch 9也有人写成ch.isdigit()。这两种在本题都可以但isdigit()对Unicode数字字符也返回True比如这种全角数字如果题目明确只要求ASCII的数字0-9建议用字符比较避免误判。训练营里的题通常不会搞这个细微差别但面试时你可以主动提会显得你严谨。5. 实际刷题中的高频问题与经验总结5.1 三个题目放在一起的刻意训练点说真的如果单独刷这三道题每道都很快就能AC但合在一起你会发现一个非常明显的递进344题是“无脑反转”只需要双指针541题是“条件反转”需要在双指针外面套一层区间控制替换数字是“反转的延伸”其实没有反转但它的核心是“从后往前的双指针”。你看三道题用到的都是同一个底层技能——双指针但应用场景一变逻辑判断就完全不同。这种训练模式正是训练营安排的意义所在用同一种技巧解决不同难度的题让你在重复中形成肌肉记忆。以后看到“字符串”“数组”“原地修改”这组关键词脑子里第一反应就应该是双指针而不是新建容器。我还发现一个规律这三道题对“循环边界”的敏感度极高。344题是while循环里leftright541题是for循环range(0,n,2k)加min边界替换数字是while old_index0。任何一个边界写错轻则少处理一个字符重则越界崩溃。建议大家刷的时候养成习惯先在纸上写出边界条件再动笔写代码。训练营里有位同学分享的土办法是拿一个具体的短字符串比如a1b跑一遍逻辑标出每个变量每一步的值这个办法对新手排查边界问题特别有效。5.2 复杂度分析与经验对比这三道题复杂度都不高但别因为简单就忽略分析面试时需要你脱口而出。344题时间复杂度O(n)空间复杂度O(1)。因为只需要左右两个指针扫一遍数组。541题时间复杂度O(n)空间复杂度O(1)若考虑转列表Python的额外空间是O(n)但算法本身在数组上操作可以看作O(1)如果题目传入的是字符串那需要转列表属于语言层面的必要开销。每2k步长处理一次每个字符最多被访问一次。替换数字如果使用简单的列表拼接时间O(n)空间O(n)。如果使用C原字符串扩容从后往前覆盖时间O(n)空间O(1)因为没有任何额外数组只是改变了原字符串的长度。注意C的resize本身可能需要重新分配内存但那是容器管理的开销通常不把resize计入额外空间或者你可以说“不考虑底层扩容开销额外空间O(1)”。这里有一个面试常追问的坑从后往前替换的空间复杂度真的是O(1)吗严格来说如果原字符数组容量不够你需要先扩容扩容要么原地扩展如果后面内存充足要么申请新空间拷贝这本身就占用了额外空间。所以有时候面试官更在意“你愿不愿意为了O(1)空间复杂度去改造一个在现实生活中几乎不会发生的场景”。实际工程里我们直接用库函数或者新建容器就好不会傻到在原字符串上腾挪。5.3 刷完这三题之后可以怎么延伸如果这三道题已经顺利拿下我建议你别急着继续往后走先趁热打铁做几道同类型的练习巩固一下接雨水不那个太难。可以先做“反转链表”你会发现链表的双指针反转和数组有相似之处但指针指向更反直觉。再做一道“反转字符串中的单词”比如把the sky is blue变成blue is sky the这道题用到了“局部反转整体反转”的组合技巧特别考验你能否把前面学的东西拆解组合。关于替换类可以做LeetCode 27移除元素或者283移动零它们也都是双指针在数组上的应用能帮你把“覆盖”“交换”这两个动作串起来。训练营的节奏一般是一天三道题但我不建议贪多。把这三道题真正消化掉比一天刷十道然后全忘要有用得多。消化标准很简单不看任何提示能独立写出代码并且能说出每行代码为什么那么写边界条件为什么那么判断。如果能做到恭喜你字符串基础这一关算是过了。最后分享一个小技巧在本地练习的时候写一个辅助函数打印数组或列表在每个步骤后的状态比如反转前、反转后替换前、替换后。我用这个办法排查541题的边界问题非常方便。很多LeetCode在线编辑器也可以手动加打印但提交前记得删掉以免影响性能。希望这篇记录能帮你少踩几个坑。字符串题最重要的是稳不要急一步一步推边界你也能像我一样顺利把这章过完。
最近在跟着一个算法训练营刷题做到第7天了今天集中解决的是三道字符串题344反转字符串、541反转字符串II还有一个变种题“替换数字”。说实话这三道题难度都不算高但放在一起刷完回头看非常有收获。它们把字符串操作里最常见的几个坑——原地修改、边界处理、长度变化、从后往前覆盖——全给串起来了。这篇文章我就以过来人的身份把这三道题的思路、代码、踩坑记录完整写一遍希望能给正在刷题的朋友一点参考尤其是那些刚开始接触字符串题、总在边界条件上翻车的小伙伴。1. 整体思路与题量安排1.1 三道题的定位与联系先说这三道题分别是什么。反转字符串是LeetCode的第一道数组/字符串题要求把一个字符数组原地反转不能用额外的数组空间。它考验的是最基础的双指针思想也是很多后续题目的“底子”。反转字符串II是344的升级版。题目标题很唬人实际规则是给定一个字符串s和一个整数k对字符串每隔2k个字符的前k个字符进行反转如果剩余字符少于k个则全部反转如果剩余字符小于2k但大于等于k个则反转前k个剩下的保持原状。这就是一道带条件的区间反转题核心考点在“如何把规则翻译成循环不变量”。第三题不一样有的题库里叫“替换数字”实际上是“将字符串中的所有数字字符替换为number”。比如输入a1b2c3输出a numberb numberc number。这个题和传统“替换空格”非常像核心考察点是已知要扩容的字符串如何高效地从后往前填充避免频繁插入导致的O(n²)开销。这三道题放在一起恰好是“基础反转 → 条件反转 → 长度变化替换”的递进关系。刷的时候明显能感觉到前一道题的动作会成为后一道题的基础动作比如541就是“控制区间分段调用双指针反转”。1.2 为什么字符串类题目适合练手很多人刷题喜欢一上来就啃动态规划、图论这些硬骨头结果就是三天打鱼两天晒网。我反而觉得字符串基础题是最适合早期稳定节奏的原因很简单第一字符串题通常不需要引入复杂的抽象数据结构你手里就一个数组或者一个string操作直观调试容易。第二字符串题特别考“细节”。数组题越界你可能一眼能看出来字符串题因为涉及字符下标、长度变化、拼接顺序边界条件一旦写错表现得往往不是报错而是输出结果莫名多一个空格或者少一个字符这种问题更难排查。第三字符串题和实际业务往往很近比如参数校验、模板渲染、日志处理天天都在跟字符串打交道。把这些算法题练明白写业务代码的时候会下意识地考虑复杂度对转义、拼接、复制的理解也会更深。所以如果你的训练营也把字符串题排在前期那就耐心跟着节奏走。相信我这三道题吃透后面遇到“反转链表”“反转区间”这类二重循环结构你会有一种“似曾相识”的感觉。2. 344. 反转字符串2.1 题目要求与双指针解法344题的表象是“反转字符串”其实考察的是原地修改数组的能力。题面说“输入一个字符数组”必须原地修改意味着你不能new一个新的字符数组再把内容倒着放进去。空间复杂度要求O(1)。双指针解法大家都会写左指针指向开头右指针指向末尾交换两个位置的字符然后左指针右移右指针左移直到两个指针相遇或者交错。交换的时候可以用临时变量也可以直接调swap函数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 - 1C版本也非常简洁class Solution { public: void reverseString(vectorchar s) { int left 0, right s.size() - 1; while (left right) { swap(s[left], s[right]); left; right--; } } };这里有一个很多新手都会纠结的点循环条件写while(left right)还是while(left right)实际无所谓对于两个不同元素交换left right时交换同一个元素等于没交换所以两种写法结果一致。但习惯上写left right因为当数组长度为奇数时中间那个字符不需要动当长度为偶数时left right保证所有对称位置都交换完。2.2 面试中的易错点与语言差异这道题虽简单面试官往往会在上面加戏。比如他问你“能不能直接调用语言内置的reverse函数”你要是说能他可能就不让你写了直接说“好下一题”。因为这道题的本意就是考察你有没有意识到不能取巧。我们刷训练营时也是同样的态度就算语言有内置API也先自己实现一遍等完全理解原理以后再看API是怎么封装的。另外要注意LeetCode上这道题给的是List[str]也就是一个字符列表不是字符串。为什么特意设计成列表正是因为Python的字符串是不可变对象你没法原地修改。如果题目给的是字符串你就要先把字符串转成列表操作完再拼回来这就不符合O(1)空间的要求了。这一点在很多面试里会被单独拎出来问如果输入是Python字符串你怎么反转答案是s s[::-1] # 利用切片创建新字符串O(n)空间但这不是这道题要求的。如果面试官要求原地且输入是字符串那说明他可能希望你用bytearray或者字符串拼接的方式不过这种讨论已经超出基础题范畴了。记住一点看到“原地修改”四个字首先确定数据类型是否可变再决定能不能做。实际上我第一次写这道题的时候还犯过一个低级错误——交换字符时直接写left 1忘了更新right - 1结果死循环把训练营的打卡页面都刷白了。从此我养成习惯写双指针循环的第一时间就把两个指针的更新语句写全不要觉得“后面再补”没关系。3. 541. 反转字符串II3.1 题意理解每2k个字符反转前k个541题第一次见很容易被绕晕。题目描述很绕“每隔2k个字符反转这2k个字符中的前k个字符如果剩余字符少于k个反转所有剩余字符如果剩余字符大于等于k但小于2k个反转前k个其余不动。”我用个更直白的方式解释你把字符串按照2k为一组来切片。对于每一组只反转这组中的前k个字符后半段原样保留。如果最后一组不足2k但要分类讨论最后一组的字符总数小于k把这整组都反转。最后一组的字符总数大于等于k但小于2k只反转前k个后面的不动。举例说明。字符串abcdefgk2。2k4。前4个是abcd反转前2个得到bacd。剩余从索引4开始是efg字符总数3大于等于k(2)但小于2k(4)因此反转前2个ef得到feg。最终结果是bacdfeg。这个例子里LeetCode题解也有我刷的时候手动推了三四遍才算真正搞懂。另一种理解方式是把字符串看作多个长度2k的小节每个小节内只处理前半段。循环的步长设为2k而不是k这个设定特别关键。很多人第一反应是步长设为k然后反转当前k个、跳过下一个k个、再反转下一个k个这样逻辑也能做但步长设置为2k会让代码更贴近题意不容易错。3.2 边界条件与模拟循环的实现按照2k步长来遍历循环内需要处理的就是“当前位置i到ik-1”这段区间。但这里有一个边界问题如果字符串最后剩余部分不足k个那我们反转到字符串末尾就停如果剩余部分至少k个那就只反转前k个。怎么判断呢可以用min(i k, n)表示要反转的区间的右边界不含。比如当前起点i0k2n7那么反转区间就是[0, min(2,7))也就是[0,2)反转两个字符。再来起点i4反转区间是[4, min(6,7))也就是[4,6)反转两个字符。如果n很小比如n3k2起点i0min(2,3)2反转[0,2)剩余1个字符不动这就符合“剩余字符小于k时反转全部剩余”吗不对剩余是c只有一个字符小于k应该反转剩余全部也就是反转c自己。如果我们用min(ik,n)作为右边界反转区间是[0,2)剩余索引2“c”没有反转。看起来不符合“反转所有剩余字符”的要求让我们仔细看看。题目说“如果剩余字符少于 k 个反转所有剩余字符”。这里“剩余字符”指的是从当前位置i开始到最后的所有字符。当i0k2n3时剩余字符是3个并不少于k(2)。所以应该反转前k个剩余1个不动。只有当i位置到最后的总长度少于k时才全部反转。所以min(ik, n)区间反转是成立的吗假如n4k2i2剩余2个字符不少于k所以应该反转前k个也就是全部剩余反转[2,4)。min(4,4)4区间[2,4)反转2个。没错。再看n1k2i0剩余1个字符少于k应该反转全部也就是反转[0,1)。min(2,1)1区间[0,1)。正确。所以使用min(ik, n)作为右边界是对的。前面n3k2min(2,3)2反转[0,2)剩余[2,3]一个字符因为剩余总数3k所以不应该反转剩余的全部。所以正确。还是用min没错。注意我们需要反转的区间是左闭右开[i, ik)与[i,n)的交集也就是[i, min(ik,n))。所以核心代码是class Solution: def reverseStr(self, s: str, k: int) - str: chars list(s) n len(chars) for i in range(0, n, 2 * k): left i right min(i k - 1, n - 1) # 反转区间的右端点包含 while left right: chars[left], chars[right] chars[right], chars[left] left 1 right - 1 return .join(chars)用右端点包含的写法right min(i k - 1, n - 1)这样区间就是[left, right]好理解。或者用右开区间right min(i k, n) for j in range(i, (i right) // 2): # 但这样可能不直观我推荐用右闭区间因为边界更直观。不过要注意如果i k - 1比i还小怎么办不可能因为k大于等于1i处至少有一个字符。所以区间至少包含一个元素不会出现leftright。其实这道题也可以把反转逻辑抽成一个单独函数因为本质上就是多次调用344题的双指针反转。面试时这样写还能体现模块化思维def reverse_range(chars, l, r): while l r: chars[l], chars[r] chars[r], chars[l] l 1 r - 1然后在主循环调用。我刷这道题踩的坑是一开始把循环步长写成了k然后用一个布尔变量flag控制“这个k反不反转”结果代码写出来又多又乱还容易在最后一组出错。后来想明白直接用步长2k完全不需要flag。这件事对我的启发是有时候问题复杂是因为你选择的步长和题目描述的粒度不一致。题目天然以2k为一个单元那就顺着它的粒度来。还有一个很容易犯的错Python里字符串不可变所以必须先把s转成list否则直接对s操作就会报TypeError: str object does not support item assignment。这句话我在训练营答疑群里至少看到过5次。新手最好记一下Python字符串和C的string不一样C的string可以修改Python的str不能。所以看到LeetCode上输入是字符串、输出也是字符串的题目千万别忘了先转列表最后再拼接。4. 54. 替换数字4.1 字符串的不可变性陷阱第三题“替换数字”其实是代码随想录里的经典扩展题题意是请你写一个函数输入一个字符串把其中所有的数字字符0-9替换成字符串number。比如输入a1b2c3输出a numberb numberc number。注意这里说的“数字”是单个字符不是连续的多位数字。如果输入是a12b输出是a numbernumberb因为1和2是两个数字字符每个都要替换。这个题最简单的写法是def replace_numbers(s: str) - str: result [] for ch in s: if 0 ch 9: result.append(number) else: result.append(ch) return .join(result)时间复杂度O(n)空间复杂度O(n)。这在大多数实际场景已经足够好了。但为什么很多训练营和教材还要讲“从后往前替换”的操作因为这道题的前身是“替换空格”在C语言或C环境中字符串是一个字符数组面试官可能要求你在原数组上进行扩容替换不借助额外数组。这时候如果你从前往后替换每遇到一个数字就要把后续所有字符往后移动时间复杂度会退化成O(n²)。掌握从后往前替换的思路本质是理解“已知扩容大小如何原地更新”的套路。即使你平时用Python不关心原数组学会这种思路也能帮你更深刻地理解为什么字符串操作要尽量避免频繁插入。4.2 从后往前替换的经典做法就在想一下如果我们手上是一个容量足够大的字符数组比如原来长度为n数字一共有cnt个每个数字变成6个字符的number那么新数组总长度为n cnt * 5因为每个数字从1个字符变成6个字符长度增加5。从后往前替换的步骤如下先扫描一遍字符串统计数字字符的个数cnt。设置新长度new_len n cnt * 5。设置两个指针old_index指向原字符串末尾n - 1new_index指向新字符串末尾new_len - 1。从后往前遍历原字符串如果当前字符不是数字直接把它复制到new_index位置两个指针都往前移1。如果当前字符是数字则依次从后往前填入number这6个字符。具体来说new_index依次填入r、e、b、m、u、n倒着填然后old_index往前移1new_index往前移6。C实现大致长这样void replaceNumber(string s) { int count 0; for (char c : s) { if (c 0 c 9) count; } int old_index s.size() - 1; s.resize(s.size() count * 5); int new_index s.size() - 1; while (old_index 0) { if (s[old_index] 0 || s[old_index] 9) { s[new_index--] s[old_index--]; } else { s[new_index--] r; s[new_index--] e; s[new_index--] b; s[new_index--] m; s[new_index--] u; s[new_index--] n; old_index--; } } }注意倒着填的时候顺序别搞错。你要让整个替换完成后字符串顺序正确从后往前填最后一个字符r应该最先出现在新字符串的末尾所以先填r再往前填e依此类推最后填n。我一开始写成顺序填结果字符串变成了rebmun看起来就像“number”倒着写。这个错误非常经典值得记在小本本上。那么Python里能做原地的类似操作吗严格来说Python字符串不可变做不到C那样在同一个字符串上resize。但我们可以用列表模拟类似过程def replace_number(s: str) - str: cnt sum(ch.isdigit() for ch in s) chars list(s) old_idx len(chars) - 1 chars.extend([] * (cnt * 5)) new_idx len(chars) - 1 while old_idx 0: if 0 chars[old_idx] 9: for ch in reversed(number): chars[new_idx] ch new_idx - 1 old_idx - 1 else: chars[new_idx] chars[old_idx] new_idx - 1 old_idx - 1 return .join(chars)上面的reversed(number)正好就是r,e,b,m,u,n逻辑清晰。不过说实话在Python中实际刷题时直接用开头那种列表拼接最快很少需要自虐式地从后往前写。但面试时如果面试官问你“原字符串是一个可变的数组你怎么做到O(1)空间”你就得拿出从后往前的方案。所以两种方案最好都掌握至少能讲清楚“从后往前为什么能避免反复移动”的复杂度分析。另一个值得留意的点是统计数字个数时有人会写成if ch 0 and ch 9也有人写成ch.isdigit()。这两种在本题都可以但isdigit()对Unicode数字字符也返回True比如这种全角数字如果题目明确只要求ASCII的数字0-9建议用字符比较避免误判。训练营里的题通常不会搞这个细微差别但面试时你可以主动提会显得你严谨。5. 实际刷题中的高频问题与经验总结5.1 三个题目放在一起的刻意训练点说真的如果单独刷这三道题每道都很快就能AC但合在一起你会发现一个非常明显的递进344题是“无脑反转”只需要双指针541题是“条件反转”需要在双指针外面套一层区间控制替换数字是“反转的延伸”其实没有反转但它的核心是“从后往前的双指针”。你看三道题用到的都是同一个底层技能——双指针但应用场景一变逻辑判断就完全不同。这种训练模式正是训练营安排的意义所在用同一种技巧解决不同难度的题让你在重复中形成肌肉记忆。以后看到“字符串”“数组”“原地修改”这组关键词脑子里第一反应就应该是双指针而不是新建容器。我还发现一个规律这三道题对“循环边界”的敏感度极高。344题是while循环里leftright541题是for循环range(0,n,2k)加min边界替换数字是while old_index0。任何一个边界写错轻则少处理一个字符重则越界崩溃。建议大家刷的时候养成习惯先在纸上写出边界条件再动笔写代码。训练营里有位同学分享的土办法是拿一个具体的短字符串比如a1b跑一遍逻辑标出每个变量每一步的值这个办法对新手排查边界问题特别有效。5.2 复杂度分析与经验对比这三道题复杂度都不高但别因为简单就忽略分析面试时需要你脱口而出。344题时间复杂度O(n)空间复杂度O(1)。因为只需要左右两个指针扫一遍数组。541题时间复杂度O(n)空间复杂度O(1)若考虑转列表Python的额外空间是O(n)但算法本身在数组上操作可以看作O(1)如果题目传入的是字符串那需要转列表属于语言层面的必要开销。每2k步长处理一次每个字符最多被访问一次。替换数字如果使用简单的列表拼接时间O(n)空间O(n)。如果使用C原字符串扩容从后往前覆盖时间O(n)空间O(1)因为没有任何额外数组只是改变了原字符串的长度。注意C的resize本身可能需要重新分配内存但那是容器管理的开销通常不把resize计入额外空间或者你可以说“不考虑底层扩容开销额外空间O(1)”。这里有一个面试常追问的坑从后往前替换的空间复杂度真的是O(1)吗严格来说如果原字符数组容量不够你需要先扩容扩容要么原地扩展如果后面内存充足要么申请新空间拷贝这本身就占用了额外空间。所以有时候面试官更在意“你愿不愿意为了O(1)空间复杂度去改造一个在现实生活中几乎不会发生的场景”。实际工程里我们直接用库函数或者新建容器就好不会傻到在原字符串上腾挪。5.3 刷完这三题之后可以怎么延伸如果这三道题已经顺利拿下我建议你别急着继续往后走先趁热打铁做几道同类型的练习巩固一下接雨水不那个太难。可以先做“反转链表”你会发现链表的双指针反转和数组有相似之处但指针指向更反直觉。再做一道“反转字符串中的单词”比如把the sky is blue变成blue is sky the这道题用到了“局部反转整体反转”的组合技巧特别考验你能否把前面学的东西拆解组合。关于替换类可以做LeetCode 27移除元素或者283移动零它们也都是双指针在数组上的应用能帮你把“覆盖”“交换”这两个动作串起来。训练营的节奏一般是一天三道题但我不建议贪多。把这三道题真正消化掉比一天刷十道然后全忘要有用得多。消化标准很简单不看任何提示能独立写出代码并且能说出每行代码为什么那么写边界条件为什么那么判断。如果能做到恭喜你字符串基础这一关算是过了。最后分享一个小技巧在本地练习的时候写一个辅助函数打印数组或列表在每个步骤后的状态比如反转前、反转后替换前、替换后。我用这个办法排查541题的边界问题非常方便。很多LeetCode在线编辑器也可以手动加打印但提交前记得删掉以免影响性能。希望这篇记录能帮你少踩几个坑。字符串题最重要的是稳不要急一步一步推边界你也能像我一样顺利把这章过完。
