题目描述

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

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

示例 1：

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 今天的每日一题是字符串反转题目，题干容易理解，反转的函数就是常用的 swap 函数增加指针的移动。

• 按照题意，可以首先写出朴素代码，经过测试，朴素代码可以通过测试。

• 朴素代码通过之后，翻看题解，一看到官方题解，瞬间感觉到自己还有很大的提升空间。反转每个下标从 2k的倍数开始的，长度为 k 的子串。若该子串长度不足 k，则反转整个子串。

• 这里的理解很厉害，比题干优化了很多，根据这个理解，可以写出优化的代码。

通过代码

• 朴素代码

public String reverseStr(String s, int k) {
        int i = 0;
        int idx = 0;
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        for (int j = 0; j < n; j++) {
            i++;
            if (i == 2 * k) {
                swap(idx, idx + k - 1, charArray);
                idx = j + 1;
                i = 0;
            }
        }
        if (i > 0 && i < k) {
            swap(idx, idx + i - 1, charArray);
        } else if (i > 0 && i < 2 * k) {
            int end = Math.min(idx + k - 1, n - 1);
            swap(idx, end, charArray);
        }
        
        return new String(charArray);
    }

    public void swap(int left ,int right, char[] arr) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

• 优化代码

    public String reverseStr(String s, int k) {
        char[] charArray = s.toCharArray();
        int n = charArray.length;
        for (int i = 0; i < n; i += 2 * k) {
            int end = Math.min(i + k, n) - 1;
            swap(i, end, charArray);
        }
        
        return new String(charArray);
    }

    public void swap(int left ,int right, char[] arr) {
        while (left < right) {
            char temp = arr[left];
            arr[left] = arr[right];
            arr[right] = temp;
            left++;
            right--;
        }
    }

总结

• 上述代码的时间复杂度是 O(n), 空间复杂度是 O(n)

• 坚持算法每日一题，加油！在算法学习过程中，每次提交通过之后，还要学习优秀的代码的解决方案，进而转换成为自己的解法，提升能力！