LeetCode 541. 反转字符串 II
目录
题目描述
题意分析
题目给出字符串 s 和整数 k，要求每数满 2k 个字符就把这一段的前 k 个反转，后 k 个保持不动，然后返回改造后的字符串。
真正需要仔细读的是尾部规则：剩余字符少于 k 个时，把剩下的全部反转；剩余字符在 k 到 2k 之间时，只反转前 k 个，其余保持原样。把这两条和主规则放在一起看会发现，它们其实是同一句话——每一段都反转「从段首起、最多 k 个」的部分。
约束是 s 长度不超过 10^4、只含小写字母、$1 \le k \le 10^4$。注意 k 允许大于整个字符串长度，这时相当于整串反转，是必须单独验一遍的边界。
另外两处边界：字符串长度恰好是 2k 的整数倍时最后一段不会有残留；长度为 1 且 k 为 1 时结果与输入相同。
输出是新字符串，但 Java 和 Go 的字符串都不可变，实现上只能先转成字符数组再改，这一点会直接影响后面对额外空间的判断。
解法：按 2k 分组原地反转
核心思路
一个自然但笨拙的写法是：用一个计数器逐字符扫描，数到第 k 个就切出一个子串反转、拼到结果里，数到第 2k 个就把这一段原样拼上，然后计数器归零。这样写要维护段内偏移、段号奇偶、以及尾部三种残留情况，分支多得很容易漏。
瓶颈不在时间而在于分支数量。既然规则以 2k 为周期，就不必逐字符地「数」，直接让段首下标以 2k 为步长跳着走即可，段号奇偶的判断随之消失。
再往前一步观察：题面里那三条规则（满 2k、剩余不足 k、剩余介于 k 和 2k 之间）其实可以合并成一条——对每个段首 start，反转闭区间 $[start,\ \min(start + k - 1,\ n - 1)]$。剩余不足 k 时 min 取到 n - 1，自动退化成「把剩下的全反转」；剩余不少于 k 时 min 取到 start + k - 1，正好是「只反转前 k 个」。三种情况合成一个表达式，尾部特判就全部消失了。
于是整个解法的不变量是：每轮循环开始时，下标小于 start 的部分已经完全处理好且不会再被碰；start 到 n - 1 是尚未处理的后缀，而它的处理方式与原问题完全同构。
段内反转本身用左右指针相向交换即可，字符数组支持随机访问，不需要另外构造子串。
解题步骤
- 先把字符串转成字符数组。因为 Java 与 Go 的字符串都不可变，只有转成数组才谈得上「原地交换」，否则每段都要重新拼一次字符串，时间会退化到 $O(n^2)$。
- 让 start 从 0 出发，每轮加 2 * k，循环条件是 start < n。步长取 2k 而不是 k，是因为每个周期里只有前半段需要动，后半段直接跳过；这样也省掉了「当前是第几段」的奇偶判断。
- 每轮先算 right = min(start + k - 1, n - 1)。取 min 是把题面三条尾部规则合并成一条的关键：不够 k 个时右端自动收缩到字符串末尾，够 k 个时右端就停在段首往后第 k 个位置。
- 调用反转函数处理闭区间 [start, right]：左右指针相向移动，
left < right时交换并各自向内走一步。用<而不是<=，是因为两指针相遇时无需和自己交换。- 注意反转函数不需要额外判断 right 是否小于 start——当 start 恰好等于 n - 1 时 right 也等于 n - 1，循环一次都不执行，天然安全。
- 全部段处理完后把字符数组转回字符串返回。
以
s = "abcdefg"、k = 2走一遍：数组为 [a, b, c, d, e, f, g]，n = 7。第一轮 start = 0，right = min(0 + 1, 6) = 1，反转 [0, 1]，交换 a 与 b，数组变成 [b, a, c, d, e, f, g]。start 加 4 变成 4，仍小于 7，第二轮 right = min(4 + 1, 6) = 5，反转 [4, 5]，交换 e 与 f，数组变成 [b, a, c, d, f, e, g]。start 再加 4 变成 8，不小于 7，循环结束。返回 "bacdfeg"，与样例一致。可以顺带核对尾部：最后一段是下标 4 到 6 共三个字符，长度介于 k = 2 和 2k = 4 之间，规则要求只反转前两个，而 min 恰好把 right 停在 5，下标 6 的 g 原封不动。
代码实现
class Solution {
// 最后一段可能不足 k 个，也可能在 k 到 2k 个之间，右边界必须取 min(start + k - 1, n -。
public String reverseStr(String s, int k) {
char[] chars = s.toCharArray();
for (int start = 0; start < chars.length; start += 2 * k) {
int right = Math.min(start + k - 1, chars.length - 1);
reverse(chars, start, right);
}
return new String(chars);
}
private void reverse(char[] chars, int left, int right) {
while (left < right) {
char swapValue = chars[left];
chars[left] = chars[right];
chars[right] = swapValue;
left++;
right--;
}
}
}
func reverseStr(s string, k int) string {
// 最后一段可能不足 k 个，也可能在 k 到 2k 个之间，右边界必须取 min(start + k - 1, n -。
chars := []byte(s)
for start := 0; start < len(chars); start += 2 * k {
right := start + k - 1
if right >= len(chars) {
right = len(chars) - 1
}
reverse(chars, start, right)
}
return string(chars)
}
func reverse(chars []byte, left int, right int) {
for left < right {
chars[left], chars[right] = chars[right], chars[left]
left++
right--
}
}
复杂度分析
- 时间复杂度：$O(n)$，段与段之间互不重叠，所有反转加起来最多交换 $n/2$ 次，转数组和转回字符串也各是一趟。
- 空间复杂度：$O(n)$，来自不可变字符串必须复制出的字符数组；若语言允许直接原地改字符串，则只需常数级额外变量。
关键点总结
- 遇到「每隔若干个做一次操作」的题，先把步长设成一个完整周期，让下标自己跳过不需要处理的部分，比逐字符计数再判奇偶要短得多。
- 题面里并列的几条尾部规则往往能合并成一个 min 或 max 表达式，合并前先手动验一遍每种情况都能落到同一个式子上，合并后特判就可以整体删掉。
- 闭区间的反转函数写成
while (left < right)就自带「区间为空或只有一个元素时什么都不做」的语义，调用方不必再加保护性判断。- 字符串不可变的语言里，凡是需要多次局部修改的题，第一步都应该是转成字符数组，否则反复拼接会把线性算法拖成平方级。
- 面试视角：这题代码很短，真正被看的是有没有主动枚举 k > n、n 恰为 2k 倍数、n 落在段中间这三类边界，并当场用一个小例子验证 min 表达式。写完后主动说一句「反转函数可以抽出来复用到 344 和 151」也是加分项。
易错点总结
- 错误写法：步长写成
start += k→ s = "abcdefg"、k = 2 时每一段都被反转，得到 "badcfeg"，而正确答案是 "bacdfeg"，后 k 个本应保持原样。- 错误写法：右边界写成
start + k - 1不取 min → s = "abcd"、k = 3 时 right 算成 2 没问题，但 s = "ab"、k = 3 时 right 算成 2 已经越界，直接抛数组下标异常。- 错误写法：把 min 的第二个参数写成
chars.length而不是chars.length - 1→ 闭区间的右端点跑到数组长度处，同样越界；开闭区间一旦混用，边界就会整体偏移一位。- 错误写法：为尾部单独写
if (剩余 < k) 全反转 else 反转前 k 个的分支 → 逻辑本身能对，但要同时维护两套下标计算，s = "abcdefg"、k = 2 这种「剩余介于 k 和 2k 之间」的情况最容易被漏进错误分支。- 错误写法：反转循环写成
while (left <= right)→ 区间长度为奇数时中点会和自己交换一次，结果虽然不变但白做；更糟的是若同时写成left++, right--之外的别的更新方式就会越过彼此，形成死循环或错位。- 错误写法：每段用
s.substring(...)切出来反转再拼回新串 → 每次拼接都要复制整串，s 长度 10^4 时会退化成平方级，且原地这个考点直接丢掉。- 错误写法：忘记把结果从字符数组转回字符串，直接返回
chars.toString()→ Java 里得到的是数组的对象地址而不是内容，必须用new String(chars)。- 错误写法：认为 k 一定小于字符串长度而不验 k > n 的情况 → s = "abc"、k = 5 时只有一轮循环，right = min(4, 2) = 2，整串反转成 "cba"，这正是题目要的；但若没取 min 就会越界，这个用例是检验边界的最短路径。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 151. 反转字符串中的单词 | 中等 | 先整体反转再逐词反转，还要压缩多余空格 |
| 186. 反转字符串中的单词 II | 中等 | 与 151 同思路但要求原地、额外空间 $O(1)$ |
| 344. 反转字符串 | 简单 | 最基础的相向双指针交换，可当本题的子过程 |
| 345. 反转字符串中的元音字母 | 简单 | 指针要先跳过不参与交换的字符再配对 |
| 557. 反转字符串中的单词 III | 简单 | 只反转每个单词内部，单词顺序保持不变 |
| 剑指 Offer 58 - I. 翻转单词顺序 | 简单 | 与 151 同题，注意首尾和中间的连续空格 |
| 补充题 11. 翻转URL字符串里的单词 | 中等 | 分隔符换成点号，反转逻辑不变但切分要改 |