LeetCode.541.Reverse String II 反转字符串 II

题目描述

541 Reverse String II
https://leetcode-cn.com/problems/reverse-string-ii/
https://leetcode.com/problems/reverse-string-ii/description/

Given a string and an integer k, you need to reverse the first k characters for every 2k characters counting from the start of the string. If there are less than k characters left, reverse all of them. If there are less than 2k but greater than or equal to k characters, then reverse the first k characters and left the other as original.
Example:

Input: s = "abcdefg", k = 2
Output: "bacdfeg"

Restrictions:

1. The string consists of lower English letters only.
2. Length of the given string and k will in the range [1, 10000]

---

解题过程

典型的字符串操作题，注意考虑全面就行，尤其注意不足k个或者不足2k个字符时的情况。
我的代码用的全都是Java String类操作，导致速度很慢，不过为了更熟悉Java类，还是应该多使用现成的类方法。

private static class SolutionV2018 {
    public String reverseStr(String s, int k) {
        StringBuilder result = new StringBuilder("");
        int i = 0;
        int lastIndex = 0;//上一个下标位
        int lastEvenEndIndex = -1;//上一个偶数段结束位
        while (i < s.length()) {
            if ((i + 1) % k == 0) {//遍历到一个完整的奇数段
                result.append(new StringBuilder(s.substring(i - k + 1, i + 1)).reverse());//加上奇数段反转
                result.append(s.substring(i + 1, i + k + 1 > s.length() ? s.length() : i + k + 1));//加上偶数段
                lastIndex = i;//上一个下标位
                lastEvenEndIndex = i + k;//上一个偶数段结束位
                i += k + 1;//跳过偶数段
            } else {
                lastIndex = i;
                i++;
            }
        }
        if (lastIndex == i - 1) {//在奇数段结束，即剩余字符不足k个
            result.append(new StringBuilder(s.substring(lastEvenEndIndex + 1)).reverse());//加上剩余奇数段的反转
        }
        return result.toString();
    }
}

提交后发现速度快的代码都是先转为char数组再操作，当然具体的方法各不相同。其中最简洁清晰的是下面这个：

public class Solution {
    public String reverseStr(String s, int k) {
        char[] ca = s.toCharArray();
        for (int left = 0; left < ca.length; left += 2 * k) {
            for (int i = left, j = Math.min(left + k - 1, ca.length - 1); i < j; i++, j--) {
                char tmp = ca[i];
                ca[i] = ca[j];
                ca[j] = tmp;
            }
        }
        return new String(ca);
    }
}

---

GitHub代码

algorithms/leetcode/leetcode/_541_ReverseString2.java
https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_541_ReverseString2.java

---