1/29 String 多步翻转法

Reverse Words in a String

需要去clarify几件事，1）can we use trim(), reverse() or split() methods in the code 2) does that mean I only can parse the string manually?

Elegant but not memory efficient method:

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;

        String[] arr = s.trim().split("\\s+");
        StringBuilder sb = new StringBuilder();
        for (int i = arr.length - 1; i > 0; --i) {
            sb.append(arr[i]).append(" ");
        }

        return sb.append(arr[0]).toString();
    }
}

parse the string manually.

第一步，先翻转所有的words，spaces保持不变，然后第二步，从后往前走，遇到word就搜集，遇到space就跳过。

public class Solution {
    public String reverseWords(String s) {
        if (s == null || s.length() == 0) return s;

        int i = 0;
        char[] array = s.toCharArray();
        while (i < s.length()) {
            // skip all the leading spaces
            while (i < s.length() && s.charAt(i) == ' ') i++;

            int start = i;
            while (i < s.length() && s.charAt(i) != ' ') i++;

            reverse(array, start, i - 1);
        }
        // use stringBuilder to get the array word by word and skip all the spaces between them
        StringBuilder sb = new StringBuilder();
        i = s.length() - 1;

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

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

    private void reverse(char[] arr, int start, int end) {
        while (start < end) {
            char temp = arr[start];
            arr[start] = arr[end];
            arr[end] =temp;
            start++;
            end--;
        }
    }
}

Reverse Words in a String II, 比上一题简单，第二步不用一个一个character看，直接reverse就可以了。

Rotate Array

需要算清楚两个subarray的长度。

class Solution {
    public void rotate(int[] nums, int k) {
        k = k % nums.length; // do not forget the situation that k is larger than the nums.length

        int n = nums.length;
        int len = n - k;  // the length of the string we need to reverse

        reverse(nums, 0, len - 1);
        // pay attention: if we want to rotate right one step, we only need to reverse the
        // last character of the array, and reverse the remaining subarray.
        reverse(nums, len, n - 1);    
        reverse(nums, 0, n - 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 --;
        }
    }
}

Reverse String

two ways to do that, one is to use StringBuilder reverse() method to reverse String.

class Solution {
    public String reverseString(String s) {
        return new StringBuilder(s).reverse().toString();
    }
}

another way is to reverse every character in the string.

class Solution {
    public String reverseString(String s) {
        int left = 0, right = s.length() - 1;
        char[] arr = s.toCharArray();
        while (left < right) {
            char c = arr[left];
            arr[left++] = arr[right];
            arr[right--] = c;
        }
        return new String(arr);
    }
}

Reverse String 2

need to use two pointers to maintain a sliding window.

class Solution {
    public String reverseStr(String s, int k) {
        char[] strArr = s.toCharArray();
        int n = s.length();
        for (int i = 0; i < n; i += 2 * k) {
            int left = i, right = Math.min(i + k - 1, n - 1);    // use two pointers to keep a sliding window.
            while (left < right) {
                char temp = strArr[left];
                strArr[left++] = strArr[right];
                strArr[right--] = temp;
            }
        }
        return new String(strArr);
    }
}