【每日一题】74. 搜索二维矩阵 + 【剑指offer】10- I. 斐波那契数列

每日一题

搜索二维矩阵，前几天做过，这次独立写出来了。

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        
        int i = 0,j = size(matrix[0]) - 1;
        int flag = matrix[i][j];
        //printf("%d",size(matrix));
        while(i < size(matrix) && j >= 0){
            flag = matrix[i][j];
            if(flag < target){
                i++;
            }
            else if(flag > target){
                j--;
            }
            else{
                return true;
            }
        }
        return false;
    }
};

剑指10-1

递归

斐波那契数列典型用递归来处理。但是这样会超出时间限制。

class Solution {
public:
    int fib(int n) {
        if(n == 0){
            return 0;
        }
        else if(n == 1){
            return 1;
        }
        else{
            return fib(n - 1) + fib(n - 2);
        }        
    }
};

动态规划

存下来前面的所有的数。

class Solution {
public:
    int fib(int n) {
        vector<int> dp;
        for(int i = 0;i <= n;i++){
            if(i == 0){
                dp.push_back(0);
            }
            else if(i == 1){
                dp.push_back(1);
            }
            else{
                dp.push_back((dp[i-1]+dp[i-2])%(1000000007));
            }
        }
        return dp[n];
    }
};

因为结果只跟前两个数字有关，所以要想办法存储前两个数字。

class Solution {
public:
    int fib(int n) {
        if(n == 0){
            return 0;
        }
        else if(n == 1){
            return 1;
        }
        int first = 0;
        int second = 1;
        int res;
        for(int i = 2;i <= n;i++){
            res = first + second;
            first = second;
            second = res % 1000000007;
        }
        return second;
    }
};