541.反转字符串Ⅱ

难度：容易

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

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

示例 1：

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

示例 2：

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

提示：

• 1 <= s.length <= 104
• s 仅由小写英文组成
• 1 <= k <= 104

解题思路

这道题目显然是模拟，实现题目中规定的反转规则就可以了。

在遍历字符串的过程中，让 i += (2 * k)，i 每次移动 2 * k，然后判断是否有需要反转的区间。

因为要找的也就是每 2 * k 区间的起点，这样写代码会高效很多。

我的代码

public String reverseStr(String s, int k) {
    // 字符串转数组，方便操作
    char[] ch = s.toCharArray();
    for (int i = 0; i < ch.length; i += 2 * k) {
        // 剩余字符少于 k 个，则将剩余字符全部反转
        if (ch.length - i < k) {
            reverseString(ch, i, ch.length - i);
        } else if (ch.length - i >= k) {// 剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符
            reverseString(ch, i, k);
        }
    }
    // 返回数组组成的字符串
    return new String(ch);
}

//反转字符串的函数
public void reverseString(char[] s, int begin, int size) {
    for (int i = 0; i < size / 2; i++) {
        char temp = s[begin + i];
        s[begin + i] = s[begin + size - 1 - i];
        s[begin + size - 1 - i] = temp;
    }
}

时间复杂度: O(n)

空间复杂度: O(1) 或 O(n)，取决于使用的语言中字符串是否可以修改。

更优雅一点的写法

public String reverseStr(String s, int k) {
    // 字符串转数组，方便操作
    char[] ch = s.toCharArray();
    for (int i = 0; i < ch.length; i += 2 * k) {
        // 如果剩余字符少于 k 个，则将剩余字符全部反转，否则反转前 k 个字符
        int end = Math.min(i + k - 1, ch.length - 1);
        reverseString(ch, i, end);
    }
    // 返回数组组成的字符串
    return new String(ch);
}

// 反转字符串的函数
public void reverseString(char[] s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start++] = s[end];
        s[end--] = temp;
    }
}

总结

交换两个元素的三种方法都需要掌握。