## Wednesday, January 27, 2016

### 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/

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     }