恢复旋转排序数组&&旋转字符串

1、给定一个旋转排序数组，在原地恢复其排序。

您在真实的面试中是否遇到过这个题？

Yes

样例

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

挑战

使用O(1)的额外空间和O(n)时间复杂度

说明

什么是旋转数组？

比如，原始数组为[1,2,3,4], 则其旋转数组可以是[1,2,3,4], [2,3,4,1], [3,4,1,2], [4,1,2,3]

解题思路：这个就是找到第一个出现降序的位置，然后排序，如何利用O(1)的空间？举个例子，比如[4,5,1,2,3]，我们可以先将[4,5]颠倒为[5,4]，然后再将[1,2,3]颠倒[3,2,1]，之后再整个颠倒就整好是按照升序排列的;

 1 public class Solution {
 2     /**
 3      * @param nums: The rotated sorted array
 4      * @return: void
 5      */
 6     public void reverse(ArrayList<Integer> nums,int start,int end){
 7         for(int i=start,j=end;i<j;i++,j--){
 8             int temp = nums.get(i);
 9             nums.set(i,nums.get(j));
10             nums.set(j,temp);
11         }
12     }
13     public void recoverRotatedSortedArray(ArrayList<Integer> nums) {
14         // write your code
15         for(int i=0;i<nums.size()-1;i++){
16             if(nums.get(i)>nums.get(i+1)){
17                 reverse(nums,i+1,nums.size()-1);
18                 reverse(nums,0,i);
19                 reverse(nums,0,nums.size()-1);
23     }
24 }

2、给定一个字符串和一个偏移量，根据偏移量旋转字符串(从左向右旋转)

样例

对于字符串 "abcdefg".

offset=0 => "abcdefg"
offset=1 => "gabcdef"
offset=2 => "fgabcde"
offset=3 => "efgabcd"

挑战

在数组上原地旋转，使用O(1)的额外空间

 1 public class Solution {
 2     /**
 3      * @param str: an array of char
 4      * @param offset: an integer
 5      * @return: nothing
 6      */
 7     public void rotateString(char[] str, int offset) {
 8         // write your code here
 9         int end = str.length-1;
10         if(str!=null&&str.length!=0){
11             offset = offset%(end+1);
12             rorate(str,0,end - offset);
13             rorate(str,end - offset+1,end);
14             rorate(str,0 ,end);
15         }
16     }
17     public void rorate(char[] str ,int start,int end){
18         char tmp;
19         while(start<=end){
20             tmp = str[end];
21             str[end]=str[start];
22             str[start]=tmp;
23             start++;
24             end--;
25         }
26     }
27 }