原题

写一个函数，输入 n ，求斐波那契（Fibonacci）数列的第 n 项（即 F(N)）。斐波那契数列的定义如下：

F(0) = 0,   F(1) = 1 F(N) = F(N - 1)   F(N - 2), 其中 N > 1. 

斐波那契数列由 0 和 1 起初，斐波那契数是由之前的两数加起来的。

答案需要模具 1e9 7.如果计算初始结果为:1万万万8，请返回 1。

示例 1：

输入：n = 2 输出：1 

示例 2：

输入：n = 5 输出：5 

题解

/** * @param {number} n * @return {number} */ var fib = function(n) { 
             if(n < 2) return n;     return (fib(n - 1)   fib(n - 2)) % (1e9   7); }; 

/** * @param {number} n * @return {number} */ var fib = function(n) { 
             if(n < 2) return n;     let tmp = 0;     let res = 1;     for(let i = 2; i <= n; i ) { 
                 res = res   tmp;         tmp = res - tmp;         res = res % (1e9 7); // 结果取模     }     return res; };

• 矩阵快速幂 (空间复杂度 O(1), 时间复杂度 O(log n) )
  • 大佬题解, 超详细

/** * @param {number} n * @return {number} */
var fib = function(n) { 
        
    if(n < 2) return n;
    let m = [[1, 1], [1, 0]];
    let res = pow(m, n-1);
    return res[0][0];
};
function pow(a, n) { 
        
    let ret = [[1, 0], [0, 1]];
    while(n > 0) { 
        
        if((n&1) == 1) { 
        
            ret = multiply(ret, a);
        } 
        n >>= 1;
        a = multiply(a, a);
    }
    return ret;
}
function multiply(a, b) { 
        
    const c = [[0, 0], [0, 0]];
    for(let i = 0; i < 2; i++) { 
        
        for(let j = 0; j < 2; j++) { 
        
            c[i][j] = (BigInt(a[i][0]) * BigInt(b[0][j]) + BigInt(a[i][1]) * BigInt(b[1][j])) % BigInt(1000000007);
        }
    }
    return c;
}