LC 541. 反转字符串 II

题目描述

这是 LeetCode 上的 541. 反转字符串 II ，难度为 简单。

给定一个字符串 s 和一个整数 k，从字符串开头算起，每 2k 个字符反转前 k 个字符。

• 如果剩余字符少于 k 个，则将剩余字符全部反转。
• 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。

示例 1：

输入：s = "abcdefg", k = 2

输出："bacdfeg"

示例 2：

输入：s = "abcd", k = 2

输出："bacd"

提示：

• 1 <= s.length <= $10^4$
• s 仅由小写英文组成
• 1 <= k <= $10^4$

---

模拟

使用 l 和 r 两个指针分别圈出每次需要翻转的“理论”范围，每次翻转完更新 l 和 r，同时注意范围 $[l, r]$ 内不足 $k$ 个的情况（将 r 与真实边界 n - 1取个 $min$）。

代码：

class Solution {
    public String reverseStr(String s, int k) {
        char[] cs = s.toCharArray();
        int n = s.length();
        for (int l = 0; l < n; l = l + 2 * k) {
            int r = l + k - 1;
            reverse(cs, l, Math.min(r, n - 1));
        }
        return String.valueOf(cs);
    }
    void reverse(char[] cs, int l, int r) {
        while (l < r) {
            char c = cs[l];
            cs[l] = cs[r];
            cs[r] = c;
            l++; r--;
        }
    }
}

• 时间复杂度：$O(n)$
• 空间复杂度：Java 中 String 属于不可变，复杂度为 $O(n)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.541 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。