LeetCode 541. 反转字符串 II

约 4 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 阿里 百度
标签
字符串 双指针

题目描述

✅ 541. 反转字符串 II

image-20260928224209015

题意分析

从字符串开头按每 2k 个字符划为一组，每组只反转前 k 个字符，后 k 个保持不动。最后一组若不足 k 个，则全部反转；若至少有 k 个但不足 2k 个，仍只反转前 k 个。

分组依据是原来的下标位置，反转只调整组内字符顺序，不改变字符串长度。输入仅含小写英文字母，k 为正整数，返回处理后的字符串。

解法：按 2k 分组原地反转

核心思路

[!blue]

每个周期中真正需要操作的只有前半段，所以让组首 start 每次增加 2k，就能直接跳过无需修改的后半段，无需额外维护反转与保留的状态。

当前组最多反转 k 个字符，因此闭区间右端为 min(start + k - 1, n - 1)。剩余不足 k 个时，右端被截到字符串末尾，等价于全部反转；剩余至少 k 个时，右端仍是前 k 个的末位，其余字符不动，两种尾部情况由同一个公式覆盖。

在选定区间里用左右指针交换成对位置并同时向中间移动。每次交换放对两端字符，区间中间剩一个字符时无需处理；各次操作区间互不重叠，所以每个位置最多被一次反转触及。

Java、Go 都先将字符串转换成可修改缓冲，操作完成再转回字符串。每组反转的边界只取决于下标和长度，不受前面字符已经交换的影响。

解题步骤

  1. 将输入转换为字符数组或字节切片。
  2. 从 start = 0 开始，以 2 * k 为步长遍历组首。
  3. 计算闭区间右端 min(start + k - 1, n - 1)，用双指针反转该区间。
  4. 组首超出字符串后结束，将缓冲区转换为结果字符串。

代码实现

class Solution {
    public String reverseStr(String s, int k) {
        char[] chars = s.toCharArray();

        for (int start = 0; start < chars.length; start += 2 * k) {
            // 每个周期最多反转前 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 {
    chars := []byte(s)

    for start := 0; start < len(chars); start += 2 * k {
        // 每个周期最多反转前 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)$，各反转区间互不重叠，转换也为线性。
  • 空间复杂度：$O(n)$，可修改字符缓冲。

关键点总结

[!green]

  • 步长是完整周期二 k，反转长度最多 k。
  • 右端是闭区间，长度需要减一。

易错点总结

[!yellow]

  • 组首步长是 2k，步长写成 k 会反转原本应保留的后半段。
  • 右端需要减一并截断到 n - 1，否则会多反转一个字符或访问越界。
  • 剩余长度介于 k 与 2k 之间时仍只反转前 k 个，不能把整段尾部全部反转。
  • Java 应使用 new String(chars) 构造结果，数组的 toString() 不会返回字符内容。

相似题目

题目 难度 关联与区别
344. 反转字符串 简单 原地反转区间是基本子过程，本题只处理每2k块中的前k个字符。
557. 反转字符串中的单词 III 简单 同样局部反转字符，本题按固定长度分块，原题按单词边界分块。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/12124492
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！