LeetCode_43_ReverseStringII

1. question: 反转字符串II（简单）

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

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-string-ii

示例 1：

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

示例 2：

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

提示：

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

2. answers

这道题在反转字符串的基础上显示了反转的范围，因此只需要在遍历的时候，限制一下反转的下标即可。

第一种方法采用栈来反转，代码如下所示：

public class Solution_0040 {

    public static String reverseStr(String s, int k) {

        Stack<Character> stack = new Stack<>();

        char[] chars = s.toCharArray();

        StringBuilder sb = new StringBuilder();
        int index = 0;

        for(char c: chars) {
            index += 1;

            // 前k个字符入栈
            if(index <= k) {
                stack.push(c);

            } else if(index <= 2*k) {
                // 此时为k-2k之间
                // 将栈中的字符出栈，拼接字符串，并拼接k-2k之间的字符。

                while(!stack.isEmpty()) {
                    // 只在k+1个字符时出栈，其余均为空
                    sb.append(stack.pop());
                }

                sb.append(c);

                // 归零，相当于下一次的字符在新的0-k之间
                if(index == 2*k) index = 0;

            }
        }

        // 最后，对于 最后一段<k的字符串，栈中保存了字符
        while(!stack.isEmpty()) {
            sb.append(stack.pop());
        }

        return sb.toString();
    }

    public static void main(String[] args) {
        System.out.println();

//        String s = "abcdefg";
        String s = "abcd";

        System.out.println(reverseStr(s, 2));
    }
}

上面方法的时间和空间复杂度均为O(n)。实际上没必要用栈，可以直接在原始数组上进行修改。反转字符串采用首尾双指针的方法来做。这时候需要额外的起始指针。代码如下所示;

public class Solution_0040_02 {

    public static String reverseStr(String s, int k) {

        char[] chars = s.toCharArray();

        int start = 0, j = 1;

        // 注意k和下标之间的对应关系
        for (int i = 0; i < chars.length; i++) {

            if(j == k) {
                // 反转 start和i之间的元素
                reverse(chars, start, i);
                // 此处直接更新下一次反转的起始位置
                start = i + k + 1;
            }

            // 更新J，
            if(j == 2*k) {
//                start = i + 1;
                j = 0;
            }

            j++;
        }

        // 注意最后，如果start依然在数组索引范围内，那么就说明此时的情况是 存在0-k个字符没有反转
        // 否则就是超出k个元素了，不需要反转
        if(start <= chars.length - 1) {
            reverse(chars, start, chars.length - 1);
        }

        return String.valueOf(chars);
    }

    // 反转
    public static void reverse(char[] chars, int start, int end) {

        char temp;
        while(start < end) {

            temp = chars[start];
            chars[start] = chars[end];
            chars[end] = temp;

            start += 1;
            end -= 1;
        }
    }

    public static void main(String[] args) {
        System.out.println();

        String s = "abcdefg";
//        String s = "abcd";

        System.out.println(reverseStr(s, 2));
    }
}

3. 备注

参考力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台 (leetcode-cn.com)，代码随想录 (programmercarl.com)。