剑指offer - 斐波那契数列(Java实现)

题目链接：https://www.nowcoder.com/practice/c6c7742f5ba7442aada113136ddea0c3?tpId=13&&tqId=11160&rp=1&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

  思路一：递归，如图递归的来计算第 n 个斐波那契数。

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return f(n);
    }
    public static int f(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        return f(n - 1) + f(n - 2);
    }
}

  思路二：记忆化数组，从递归方法中的图来看，在递归的过程中，我们需要进行大量的重复计算，这样就大大降低了程序的执行效率，我们可以使用一个记忆化数组来保存已经计算过的数组，这个就可以降低程序的时间复杂度。

public class Solution {
    static int[] F = new int[40];
    public int Fibonacci(int n) {
        for(int i = 0; i < 40; ++ i) F[i] = 0;
        if(n == 0) return 0;
        if(n == 1) return 1;
        return f(n);
    }
    public static int f(int n) {
        if(F[n] != 0) return F[n];
        if(n == 0) return 0;
        if(n == 1) return 1;
        return F[n] = f(n - 1) + f(n - 2);
    }
}

  思路三：递推，f[n] = f[n - 1] + f[n - 2];

public class Solution {
    static int[] F = new int[40];
    public int Fibonacci(int n) {
        F[0] = 0; F[1] = 1;
        for(int i = 2; i <= n; ++ i) {
            F[i] = F[i - 1] + F[i - 2];
        }
        return F[n];
    }
}

  思路四：矩阵快速幂。 ，我们令:
    
那么我们需要找到的矩阵 A 就满足：
      
又因为：
    
所以：
    
即：
    
综上所述：
    


我们用矩阵快速幂求出后，结果矩阵的第一行与上面公式中最后的做矩阵乘法即是最终结果。

快速幂：https://blog.nowcoder.net/n/f93bed69e38f474a839cb5105d0babc2

public class Solution {
    public int Fibonacci(int n) {
        if(n == 0) return 0;
        if(n == 1) return 1;
        int[][] a = new int[2][2];
        init(a);
        int[][] ans = quickPow(a, n - 1);
        return ans[0][0];
    }
    static int[][] init(int[][] a) {
        a[0][0] = 1; a[0][1] = 1;
        a[1][0] = 1; a[1][1] = 0;
        return a;
    }
    static int[][] quickPow(int[][] a, int b) {
        int[][] ans = new int[2][2], res = new int[2][2];
        init(ans); init(res);
        ans[0][1] = 0; ans[1][0] = 0; ans[1][1] = 1;
        while(b > 0) {
            if(b % 2 == 1) ans = mul(ans, res);
            res = mul(res, res);
            b >>= 1;
        }
        return ans;
    }

    static int[][] mul(int[][] a, int[][] b) {
        int[][] z = new int[2][2];
        for(int i = 0; i < 2; ++ i) {
            for(int j = 0; j < 2; ++ j) {
                z[i][j] = 0;
                for(int k = 0; k < 2; ++ k) {
                    z[i][j] += a[i][k] * b[k][j];
                }
            }
        }
        return z;
    }
}