First question

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, Num rotates on a previously unknown subscript k (0 < = k < num.length), making the array [num [k], Num [K + 1],..., Num [n-1], Num [0], Num [1],..., Num [k-1]] (subscripts count from 0). For example, [0,1,2,4,5,6,7] may become [4,5,6,7,0,1,2] after rotation at subscript 3.

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

Problem solving:

Violent problem solving:

int search(int* nums, int numsSize, int target){
    if(numsSize==0){
        return -1;
    }
    if (numsSize == 1){
        return nums[0] == target?0:-1;
    }
	int i;
    for (i = 0;i<numsSize;i++){
        if (target == nums[i]){
            return i;
        }
    }
    return -1;
}

Binary search:

Idea:

1. Since it is an ordered array, the first thought is binary search

2. The meaning of the question says that it is an ordered array after a rotation change. Then analyze whether the binary search method can be used.

3. Divide the array into two parts according to the binary search method. Half of the rotated array can be divided all the time because it should be orderly.

int search(int* nums, int numsSize, int target){
	if(numsSize==0){
        return -1;
    }
    if (numsSize == 1){
        return nums[0] == target?0:-1;
    }

    int left,right,mid;
    left = 0; 
    right = numsSize-1;
    while(left<=right){
        mid = (left+right)/2;
        if (nums[mid] == target){
            return mid;
        }
        if (nums[0]<=nums[mid]){
            if (target>=nums[0]&& target<nums[mid]){
                right = mid-1;
            }else{
                left = mid+1;
            }
        }else{
            if (target>nums[mid]&& target<=nums[numsSize-1]){
                left = mid+1;
            }else{
                right = mid-1;
            }
        }
    }
    return -1;
    
}

The second question is almost the same as the first question, so I don't write it

Question 3

An array of length n is known, which is arranged in ascending order in advance. After 1 to n rotations, the input array is obtained. For example, the original array num = [0,1,2,4,5,6,7] may be obtained after changing:
If you rotate 4 times, you can get [4,5,6,7,0,1,2]
If you rotate 7 times, you can get [0,1,2,4,5,6,7]
Note that the array [a[0], a[1], a[2],..., a[n-1]] is rotated once, and the result is array [a[n-1], a[0], a[1], a[2],..., a[n-2]].

Give you an array nums with different element values. It was originally an array arranged in ascending order and rotated many times according to the above situation. Please find and return the smallest element in the array

Problem solution

1. The violent solution is similar to the violent solution of the first question, but if there are more than one, the minimum value will not be written

2. Optimization of violence solution.

Idea: find an inflection point

According to the meaning of the question, if the minimum value is not where the subscript is zero, it must be where the latter value is smaller than the previous value. And there is only one inflection point. Once found, the result will be returned directly. The latter comparison is less.

int findMin(int* nums, int numsSize){
    int i ;
    for(i=1;i<numsSize;i++){
        if(nums[i]<nums[i-1]){
            return nums[i];
        }
    }
    return nums[0];
}

Question 4

Suppose you are climbing stairs. You need n steps to reach the roof.

You can climb one or two steps at a time. How many different ways can you climb to the roof?

**Note: * * given n is a positive integer.

Problem solution

1. This should be the subject of dynamic programming. I'm still confused. I won't know. Interested in the following dynamic equation.

f(n) = f(n-1) + f(n-2);

Explanation: we analyze it backwards and go to the nth order. We can go from the Nth-1 order to the first step, or from the nth-2 order to the first step and the second step The way to step n is to add the way to step n-1 to step n-2

f(1) = 1;

Explanation: to the first order, there is only one way

f(2) = 2;

Explanation: to the second order, there are two ways: 1. Step by step and two steps. 2. Step by step, step by step.

Combined with the above dynamic equation, the problem solution is obtained

int climbStairs(int n){
    int f1 = 1;
    if (n==1){
        return f1;
    }
    int f2 = 2;
    int i ;    
    for(i =3;i<=n;i++){
        int f3 = f1+f2;
        f1 = f2;
        f2 = f3;
    }
    return f2;
}

Summary: the knowledge points of today's training are arrays. You can store the values of intermediate steps (f3, and subscript i) in an array with appropriate length. Just take the value corresponding to n.

Question 5

Fibonacci numbers are usually represented by F(n), and the sequence formed is called Fibonacci sequence. The sequence starts with 0 and 1, and each subsequent number is the sum of the first two numbers. That is:

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2), where n > 1
Here you are n, please calculate F(n).

Problem solving:

We can also solve the problem according to the idea of dynamic programming, and the problem has given the dynamic equation.

int fib(int n){
    int f0 = 0;
    int f1 = 1;
    int i ;    
    for(i =2;i<=n;i++){
        int f2 = f0+f1;
        f0 = f1;
        f1 = f2;
    }
    return f1;
}

Summary: you can also save the intermediate results to the array and get the results from the array.