ReverseStringII [source code]

public class ReverseStringII {
    public String reverseStr(String s, int k) {
        if (s.length() == 0 || k == 0) return s;
        char[] chars = s.toCharArray();
        int n = chars.length;
        int m = n % (2 * k) != 0 ? n / (2 * k) + 1 : n / (2 * k);
        for (int i = 0; i < m; i++) {
            int hd, tl;
            if (i == m - 1 && (n - 2 * k * (m - 1)) < k) {
                hd = i * 2 * k + 0;
                tl = n - 1;
            } else {
                hd = 0 + i * 2 * k;
                tl = k - 1 + i * 2 * k;
            }
            while (hd < tl) {
                char tmp = chars[tl];
                chars[tl--] = chars[hd];
                chars[hd++] = tmp;
            }
        }
        // return new String(chars);
        return String.valueOf(chars);
    }

    public static void main(String[] args) {
        ReverseStringII tester = new ReverseStringII();
        String i1s = "abcdefgh";
        int i1k = 2;
        System.out.println(tester.reverseStr(i1s, i1k));
    }
}

这个问题总体来说还是很简单的, 不过还是符合 Google 的题目一贯的作风, 对细节的处理比较注重. 这题的主要思路就是分段, 然后每一段内 reverse. 直观的做法肯定是段内的 rev 用一个专门的utility 函数来做, 不过这个是不必要的, 而且因为要不停的传值, 最后对速度也有影响. 反正 rev 本身也是很简单, 直接在段内 inline 做掉就行了.

分段问题, 目前刷题还是第一次碰到, 尤其是分段后的 iterate 怎么处理. 这个在425的 zimpl 的数独问题的时候稍微接触了一下. 需要思考的问题是, 最外层的 iterator 是用分段的 index呢, 还是直接用 element 的 index(然后内部再来用处理完成分段). 比较常规的做法就是这里的做法, 最外层的 iterator 用段落的 index.

这里总结一个循环 header 里面termination condition的写法: i < n这里的 n, 其实更多的时候你要记住, 这里是一个length的概念才放在这里(前面是<不能取等号, 如果取等号就完全不一样了). 这个总结看起来很 trivial, 不过如果是做一个实际的题目的时候, 很可能脑子里就把不同的概念搞混了. point is, 这个开区间终点应该是length, 而不是最值.

最后的速度是8(44), 不算特别快, 有点奇怪, 这个算法的速度应该是 linear 了.

找到一个优化, 就是最后的char array to string, 用 valueOf 更快, 速度直接做到了: 6(82). 这个好像是 submission 最优解了;

这个是 submission 最优解的另外一个写法:

public class Solution {  
  public String reverseStr(String s, int k) {  
        char[] test = s.toCharArray();  
        int sz = 0;  
        while(sz < test.length){  
            reverse(test , sz , k);  
            sz +=2 * k;  
        }  
        return String.valueOf(test);  
    }  

    private static void reverse(char[] t, int n , int k){  
        if(n + k > t.length) k =  t.length  - n;  
        int i  = 0;  
        while(i < k/2){  
            char temp = t[n+i];  
            t[n+i] = t[n+k-i-1];  
            t[n+k-i-1] = temp;  
            i++;  
        }  
    }  
}

一模一样的速度; 好像这个传值对于速度的影响并没有我想象的那么大. 而且他这样分开写了之后其实是比我的代码要更好理解的.

分段的另外一种做法:

 for (int left = 0; left < ca.length; left += 2 * k) {

直接用循环的 step 来表达分段, 这个就是我上面说的第二种思路; 其实这个写法好像更好理解一些?!
对应的解:

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);  
    }  
}

这个是另外一个用 builder 的思路做的:

    public String reverseStr(String s, int k) {  
        StringBuilder res = new StringBuilder();  
        for (int i = 0; i < s.length(); i++) {  
            if (i % (2 * k) < k) res.insert(i - i % (2 * k), s.charAt(i));  
            else res.append(s.charAt(i));  
        }  
        return res.toString();  
    }

代码很简洁, 估计真正工业上还是用这种思路的多一些, 就是速度不怎么样: 19(11);

Problem 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:
The string consists of lower English letters only.
Length of the given string and k will in the range [1, 10000]
Difficulty:Easy
Category:Algorithms
Acceptance:43.90%
Contributor: Stomach_ache
Companies
google
Related Topics
string
Similar Questions
Reverse String Reverse Words in a String III