LintCode 39 - Recover Rotated Sorted Array + LintCode 8 Rotated String

http://www.chenguanghe.com/recover-rotated-sorted-array/

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

Clarification

What is rotated array?

• For example, the orginal array is [1,2,3,4], The rotated array of it can be [1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

Example

[4, 5, 1, 2, 3] -> [1, 2, 3, 4, 5]

We can use binary search log(n) to find the rotated point(pivot).

public void recoverRotatedSortedArray(ArrayList<Integer> nums) {

        for(int i = 0; i < nums.size()-1; i++){

            if(nums.get(i) > nums.get(i+1)){

                reverse(nums,0,i);

                reverse(nums,i+1,nums.size()-1);

                reverse(nums,0,nums.size()-1);

                break;

            }

        }

    }

    

    

    public void reverse(ArrayList<Integer> nums, int i, int j) {

        while(i < j) {

            Integer tmp = nums.get(i);

            nums.set(i,nums.get(j));

            nums.set(j,tmp);

            i++;

            j--;

        }

    }

http://www.jiuzhang.com/solutions/recover-rotated-sorted-array/

http://blog.hyoung.me/cn/2017/02/array-rotation/

从连续性角度考虑，我们发现旋转过后的数组中，起始元素应该与末尾元素相连，而新的结合点旁边的两个元素则应该位于原始数组的两端，那我们有没有办法通过交换的方式来重构这种关系呢？答案就是分步翻转了。

以题设中的例子来看，要想还原可以经过三步翻转，如下图所示

当然，我们可以利用之前解决 Find the Minimum in RSA 的方法在 $O\left(\text{log}N\right)$ 的时间内来找到断点，出于简化逻辑的考虑，就不做此优化了。即使优化过后，整体算法时间复杂度也还是 $O\left(N\right)$，并不会受影响。
http://www.chenguanghe.com/recover-rotated-sorted-array/

LintCode 8 Rotated String
http://www.cnblogs.com/EdwardLiu/p/4427493.html

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

Example
Given "abcdefg"

for offset=0, return "abcdefg"

for offset=1, return "gabcdef"

for offset=2, return "fgabcde"

for offset=3, return "efgabcd"

 7     public void rotateString(char[] str, int offset) {
 8         // write your code here
 9         if (str==null || str.length==0) return;
10         offset %= str.length;
11         if (offset == 0) return;
12         reverse(str, 0, str.length-1);
13         reverse(str, 0, offset-1);
14         reverse(str, offset, str.length-1);
15     }
16     
17     public void reverse(char[] str, int l, int r) {
18         
19         while (l < r) {
20             char temp = str[l];
21             str[l] = str[r];
22             str[r] = temp;
23             l++;
24             r--;
25         }
26     }

http://blog.hyoung.me/cn/2017/02/array-rotation/

void rotateString(string &str,int offset){

    int n = str.length();

    if (n < 2)

        return;

    

    offset %= n;

    

    reverse(str.begin(), str.end());

    reverse(str.begin(), str.begin() + offset);

    reverse(str.begin() + offset, str.end());

}

 7     public char[] rotateString(char[] A, int offset) {
 8         // wirte your code here
 9         if (A==null || A.length == 0) return new char[0];
10         String str = new String(A);
11         offset %= str.length();
12         if (offset == 0) return str.toCharArray();
13         String first = str.substring(0, str.length()-offset);
14         String second = str.substring(str.length()-offset);
15         String res = second + first;
16         return res.toCharArray();
17     }