[nine day training] content III of the problem solution of leetcode question brushing Report

write in front   

Hello everyone , I am a Ze En, I hope after you read it , It can help you , Insufficient, please correct ！ Learn and communicate together
2021 Blog star of the year, Internet of things and embedded development TOP5,  Zhou Bang 43, General list 3343
This paper is written by   Ze En  original CSDN First episode If you need to reprint, please inform
Personal home page ： Beating soy sauce desu_ Ze En_CSDN Blog
Welcome to → give the thumbs-up + Collection ️ + Leaving a message. ​
Series column ： Nine day training (LeetCode) Algorithm _ Beating soy sauce desu-CSDN Blog
Creation time ：2021 : 12 . 13  Japan
️ We are not on the stage of our choice , Acting is not the script we chose  

• This chapter's blog topic links   

1. 33. Search rotation sort array - Power button （LeetCode）
2. 81. Search rotation sort array II - Power button （LeetCode）
3. 153. Look for the minimum value in the rotation sort array - Power button （LeetCode）
4. 70. climb stairs - Power button （LeetCode）
5. 509. Fibonacci number - Power button （LeetCode）
6. 1137. The first N One tibonacci number - Power button （LeetCode）

Catalog

write in front   

This chapter's blog topic links   

Search rotation sort array  

Search rotation sort array  

Look for the minimum value in the rotation sort array  

climb stairs  

Fibonacci sequence

The first N Fibonacci sequence

---

---

Search rotation sort array  

subject ： 

​

Example ：

​

​

🧨 Tips ： 

• 1 <= nums.length <= 5000
• -10^4 <= nums[i] <= 10^4
• nums Every value in is unmatched
• Ensure data in the title  nums  Rotated on a previously unknown subscript
• -10^4 <= target <= 10^4

---

Solution to the problem

• Direct use of violence , use for Loop traversal , See if  num[n] == target, Otherwise return to -1.

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

---

Search rotation sort array  

subject ： 

​ Example ：

​🧨 Tips ： 

• 1 <= nums.length <= 5000
• -104 <= nums[i] <= 104
• Ensure data in the title  nums  Rotated on a previously unknown subscript
• -10^4 <= target <= 10^4

---

Solution to the problem  

• This topic is the same as the above topic , But the return value of the traversal of this topic is different from that of the loop that has retreated . 

bool search(int* nums, int numsSize, int target){
    int n = 0;
    for(n=0;n<numsSize;n++)
    {
        if(nums[n] == target)
        {
            return true;
        }
    }
    return false;
}

---

Look for the minimum value in the rotation sort array  

subject ：

​

Example ：

​🧨 Tips ： 

• n == nums.length
• 1 <= n <= 5000
• -5000 <= nums[i] <= 5000
• nums  All integers in   Different from each other
• nums  It turns out to be an ascending array , And carried on  1  to  n  Second rotation

---

Solution to the problem  

This topic mainly focuses on binary search , But I use for Loop traversal , Then judge . So as to compare with each other , Then find the minimum value in the array . 

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

---

climb stairs  

subject ：

​

Example ：

​

---

Solution to the problem  

use for loop , Then exchange the variable values in it . Last Return value to return , When for When the cycle does not meet the conditions , Be careful ： Here's the variable c Initialization must be 1. 

int climbStairs(int n) {
    int a = 0, b = 0, c = 0;
    int i;
    for (i = 1; i <= n; i++)
    {
        a = b;      //a = 0,b = 0,a = 1
        b = c;      //b = 1,
        c = a + b;  //c = 1,c = 2
    }
    return c;
}

---

Fibonacci sequence

subject ：

​

Example ：

​

🧨 Tips ：  

• 0 <= n <= 30

---

Solution to the problem  

At the beginning of this topic, I thought of using recursion , It's over . In recursive terms , Less code , But the efficiency is relatively low . 

Defined recursively as follows ：F(0)=0,F(1)=1, F(n)=F(n - 1)+F(n - 2)

int fib(int N){
    if (N == 0 || N == 1) 
    {
        return N;
    }
    return fib(N - 1) + fib(N - 2);
}

---

The first N Fibonacci sequence

subject ：

​ Example ： 

​

🧨 Tips ： 

• 0 <= n <= 37
• The answer is guaranteed to be 32 An integer , namely  answer <= 2^31 - 1.

---

Solution to the problem   

First n = 0 perhaps n == 1 as well as 2, Each is a return 0 and 1 Of . Then do this problem according to this idea ： And in n >= 0  Under the condition of Tn+3 = Tn + Tn+1 + Tn+2.

int tribonacci(int n){
    if(n==0)
    {
        return 0;
    }
    if(n==1||n==2)
    {
        return 1;
    }
    int a=0,b=1,c=1;
    int d = 0;
    int i = 0;
    for(i=3;i<=n;i++)
    {
        d=a+b+c;
        a=b;
        b=c;
        c=d;
     }
     return d;
}

 ​