【LeetCode】Day49-斐波那契数

509. 斐波那契数【简单】

class Solution {
    public int fib(int n) {
        if(n<2)
            return n;
        int first=0,second=1,third=0;
        for(int i=2;i<=n;i++){
            third=first+second;
            first=second;
            second=third;
        }
        return third;
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( 1 ) O(1) O(1)

关于java中的位运算，这篇文章说的比较清楚【Java位运算】n&1和n＞＞1含义

矩阵快速幂模板：

public int[][] pow(int[][] a, int n) {
    int[][] ret = {{1, 0}, {0, 1}};//单位矩阵
    while (n > 0) {
        if ((n & 1) == 1) {
            ret = multiply(ret, a);
        }
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}

此题代码：

class Solution {
    public int fib(int n) {
        if(n<2)
            return n;
        int[][] a={{1,1},{1,0}};
        int[][] res=pow(a,n-1);
        return res[0][0];
    }
    //矩阵快速幂
    public int[][] pow(int[][] a,int n){
        int[][] ret={{1,0},{0,1}};//单位矩阵
        while(n>0){
            //奇数
            if((n&1)==1)
                ret=multiply(ret,a);
            a=multiply(a,a);
            n>>=1;
        }
        return ret;
    }
    //矩阵乘法
    public int[][] multiply(int[][] a,int[][] b){
        int[][] c=new int[2][2];
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j];
            }
        }
        return c;
    }
}

时间复杂度： O ( l o g n ) O(logn) O(logn)

空间复杂度： O ( 1 ) O(1) O(1)

1137. 第 N 个泰波那契数【简单】

class Solution {
    public int tribonacci(int n) {
        if(n<3)
            return n<2?n:1;
        int first=0,second=1,third=1,forth=0;
        for(int i=3;i<=n;i++){
            forth=first+second+third;
            first=second;
            second=third;
            third=forth;
        }
        return forth;
    }
}

时间复杂度： O ( n ) O(n) O(n)

空间复杂度： O ( 1 ) O(1) O(1)

class Solution {
    public int tribonacci(int n) {
        if(n<3)
            return n<2?n:1;
        int[][] a={{1,1,1},{1,0,0},{0,1,0}};
        int[][] res=mi(a,n);
        return res[0][2];
    }
    //矩阵快速幂
    public int[][] mi(int[][] a,int n){
        int[][] ret={{1,0,0},{0,1,0},{0,0,1}};
        while(n>0){
            if((n&1)==1)
                ret=multiply(ret,a);
            a=multiply(a,a);
            n>>=1;
        }
        return ret;
    }
    //矩阵乘法
    public int[][] multiply(int[][] a,int[][] b){
        int[][] c=new int[3][3];
        for(int i=0;i<3;i++){
            for(int j=0;j<3;j++){
                c[i][j]=a[i][0]*b[0][j]+a[i][1]*b[1][j]+a[i][2]*b[2][j];
            }
        }
        return c;
    }
}

时间复杂度： O ( l o g n ) O(logn) O(logn)

空间复杂度： O ( 1 ) O(1) O(1)

p.s. 听师兄的建议，开始了动态规划的每日训练~每天两三道，动态规划真的让人头疼，希望能通过21天的训练拿下！