reference resources: https://www.cnblogs.com/gzshan/p/12570332.html

1, Rotate array

Corresponding to 43 questions of Niuke

1. Title

There is a shift instruction in assembly language called cyclic left shift (ROL). Now there is a simple task to simulate the operation result of this instruction with a string. For a given character sequence S, please rotate the sequence output after shifting it left by K bits (ensure that K is less than or equal to the length of S). For example, the character sequence S = "abcXYZdef" requires the output of the result after the cycle is shifted left by 3 bits, that is, "XYZdefabc". Isn't it simple? OK, take care of it!

Data range: the length of the input string meets the requirements,
Advanced: space complexity, time complexity

2. Ideas

Note that if n is greater than str length, it can be realized by taking remainder
For example:
Input: "aab", 10
Return value: "aba"

3. Code

//Built in method
public class Solution{
	private chars reverse(char str, int n){
		if (str == null || str.length()<= 1 || n <= 0 ) return str;
		if ( n > str.length()) n= n%str.length();
		return str.subString(n) + str.subString(0,n);
}
}

//Flip three times
public class Solution {
    public String LeftRotateString(String str,int n) {
        // base case
        if (str == null || str.length()<= 1 || n<=0) return str;
        if (n> str.length()) n= n%str.length();
        //New array
        char [] chars = str.toCharArray();
        //Flip left and right, and then flip as a whole
        reverse (chars, 0, n-1);
        reverse (chars, n , str.length()-1);
        reverse (chars, 0, str.length()-1);
        return new String(chars);
    }
    private void reverse (char[] chars, int start, int end ){
        while(start < end){
            char temp = chars [start];
            chars[start] = chars[end];
            chars[end] = temp;
            start ++;
            end--;
        }
    }
}

2, Binary search

1. Title

Find a specific value target in an ordered array

2. Ideas

Binary search

• If target = = num s [mid], return directly
• If target < num s [mid], then target is located in the left section [left, mid]. Let right = mid-1, search in the left section
• If target > num [mid], then target is in the right section (mid,right). Make left = mid+1 and search in the right section

3. Code

public class Solution{
	   public boolean search(int[] nums, int target) {
       		if(nums==null || nums.length==0) return false;
      		int low=0,high=nums.length-1;
        	while(low<=high){
         		 int mid=low+(high-low)/2;
           		 if(nums[mid]==target)  return true;
                else if(target<nums[mid]){ 
                high=mid-1;
                }else{
                low=mid+1;
            }
        }
        return false;
    }
}

3, Search rotation sort array

1. Title

The integer array nums is arranged in ascending order, and the values in the array are different from each other.

Before passing to the function, nums rotates on a previously unknown subscript k (0 < = k < nums. Length), so that the array becomes [nums[k], nums[k+1],..., nums[n-1], nums[0], nums[1],..., nums[k-1]] (the subscript counts from 0). For example, after rotating at subscript 3, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2].

Give you the rotated array num and an integer target. If the target value target exists in num, return its subscript, otherwise return - 1.

Example

input: nums = [4,5,6,7,0,1,2], target = 0
 output: 4

input: nums = [4,5,6,7,0,1,2], target = 3
 output: -1

2. Ideas

For binary search, if you separate from any position, half of them must be orderly. Therefore, we can still separate from the midpoint position, and then compare the leftmost elements num [low] and num [mid], so as to judge whether the left or right side is continuous and orderly, and then we can choose which side to continue the search.
1. If target = = num s [mid], return directly
2. If num [left] < = num [mid], it indicates that the left section [left,mid] is "continuously increasing". At this time:
   if num [left] < = target < = num [mid], it means that the target is on the left. Let right = mid-1 and find it in the left interval
   otherwise, make left = mid+1 and search in the right section
3. Otherwise, it indicates that the interval [mid,right] on the right is "continuously increasing".
  at this time:
If num [mid] < = target < = num [right], it means that target is located in the right section. Make left = mid+1 and search in the right section
   otherwise, make right = mid-1 and search in the left section

3. Code

class Solution {
    public int search(int[] nums, int target) {
        if(nums==null || nums.length==0)
            return -1;
        int low=0,high=nums.length-1;
        while(low<=high){
            int mid=low+(high-low)/2;
            if(nums[mid]==target)
                return mid;
            else if(nums[low]<=nums[mid]){  //Left continuous
                if(target<nums[mid] && target>=nums[low])
                    high=mid-1;
                else
                    low=mid+1;
            }else{      //Right continuous
                if(target>nums[mid] && target<=nums[high])
                    low=mid+1;
                else
                    high=mid-1;
            }
        }
        return -1;
    
}