541-反转字符串 ii

题目地址(541. 反转字符串 II - 力扣（LeetCode）)

https://leetcode.cn/problems/reverse-string-ii/description/

题目描述

给定一个字符串 s 和一个整数 k ，从字符串开头算起，每计数至 2k 个字符，就反转这 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

前置知识

• 字符串
• 双指针

思路

使用 left 和 right 两个指针分别指向待反转的范围。

每次翻转完，要更新 left 和 right 的范围。

• l = l + 2 * k
• r = l + k - 1

指向下一个 2k 范围，然后再进行反转。

关键点

• 双指针移动的更新
• 最后一次翻转，r 有可能越界，因为要取 Math.min(r,n-1)

代码

• 语言支持：Java

Java Code:

class Solution {
    public String reverseStr(String s, int k) {
        char[] cs = s.toCharArray();
        int n = s.length();
        // l 和 r 分别指向待反转的范围
        // 更新 l 和 r 要注意 不足 k 的情况。
        // r 可能会 > n-1，此时应该是最后一次，而 l 还是会在索引范围内，
        // 极端的情况是 l = n-1，此时不需要翻转。
        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--;
        }
    }
}

复杂度分析

令 n 为字符串长度。

• 时间复杂度：$O(n)$。遍历的长度为字符串长度n。
• 空间复杂度：$O(n)$,因为Java语言不需要申请长度为n的数组来存储字符。