多步翻转法

Reverse Words in a String II

两步翻转法，参考 这里 的 topological sort. 其实这个 follow up 比问题一简单，因为已经告诉你了没有 trailing zeros 而且中间空格只有一个。

while 循环里套 while 的时候，记得把外层的判断条件也放到内层，否则容易越界。

public class Solution {
    public void reverseWords(char[] s) {
        int wordStart = 0;
        int index = 0;

        while(index < s.length){
            while(index < s.length && s[index] != ' ') index++;

            reverse(s, wordStart, index - 1);

            index ++;
            wordStart = index;
        }

        reverse(s, 0, s.length - 1);
    }

    private void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start ++;
            end --;
        }
    }
}

Reverse Words in a String I

稍微麻烦点，要处理各种 trailing space 和中间

public class Solution {
    public String reverseWords(String s) {
        if(s.length() == 0) return "";
        int wordStart = 0;
        int index = 0;

        char[] array = s.toCharArray();

        while(index < s.length()){
            while(index < s.length() && array[index] == ' ') index ++;
            wordStart = index;
            while(index < s.length() && array[index] != ' ') index ++;
            reverse(array, wordStart, index - 1);
        }

        StringBuilder sb = new StringBuilder();
        index = s.length() - 1;

        while(index >= 0){
            while(index >= 0 && array[index] == ' ') index --;
            while(index >= 0 && array[index] != ' '){
                sb.append(array[index--]);
            }
            sb.append(' ');
        }

        return sb.toString().trim();
    }

    private void reverse(char[] s, int start, int end){
        while(start < end){
            char temp = s[start];
            s[start] = s[end];
            s[end] = temp;

            start ++;
            end --;
        }
    }
}

Rotate Array

多步翻转法的另一个应用。

public class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length;

        reverse(nums, 0, nums.length - k - 1);
        reverse(nums, nums.length - k, nums.length - 1);
        reverse(nums, 0 , nums.length - 1);
    }

    private void reverse(int[] nums, int start, int end){
        while(start < end){
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;

            start ++;
            end --;
        }
    }
}

A1 a2 ..an b1 b2 ...bn -> a1b1a2b2...anbn

AaBb - ABab

a1 a2 (a3 a4 b1 b2) b3 b4 - a1 a2 b2 b1 || a4 a3 b3 b4

因为 a1 a2 长度等于 b1 b2