Recover Rotated Sorted Array

Given a rotated sorted array, recover it to sorted array in-place.

解题方法

找出斷點，然後用reverse way to recover. (三段翻轉法)

private void reverse(List<Integer> nums, int start, int end) {
        for (int i = start, j = end; i < j; i++, j--) { //只是要找斷點
            int temp = nums.get(i);
            nums.set(i, nums.get(j));
            nums.set(j, temp);
        }
    }

    public void recoverRotatedSortedArray(List<Integer> nums) {
        for (int index = 0; index < nums.size() - 1; index++) {
            if (nums.get(index) > nums.get(index + 1)) {
                reverse(nums, 0, index);
                reverse(nums, index + 1, nums.size() - 1);
                reverse(nums, 0, nums.size() - 1);
                return;
            }
        }
    }

Rotate String

Given a string and an offset, rotate string by offset. (rotate from left to right)

解题方法

找出斷點，然後用reverse way to recover. (三段翻轉法)

public void rotateString(char[] str, int offset) {
        //corner case
        if(str == null || str.length == 0){
            return;
        }

        //check cycle
        int n = str.length;
        offset = offset % n;

        reverse(str, n - offset, n - 1);
        reverse(str, 0, n - offset - 1);
        reverse(str, 0 , n - 1);
    }

    private void reverse(char[] str, int start, int end){
        if(start == end){ return;}
        for(int i = start, j = end; i < j; i++, j--){
            char temp = str[i];
            str[i] = str[j];
            str[j] = temp;
        }
    }