剑指offer - 斐波那契数列 - JavaScript

题目描述:写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

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

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

题目描述

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项。斐波那契数列的定义如下:

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

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

注意:由于测试数据会溢出 js 中的整数范围,所以请使用大数(bigint)类型!!!

本题和LeetCode.509. 斐波那契数一样。

解法 1: 数学定义

根据数学定义:f(n) = f(n - 1) + f(n - 2)。最初始情况是f(0) = 0f(1) = 1

因此直接循环更新即可。时间复杂度 O(N),空间复杂度 O(1)。

// ac地址:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
// 原文地址:https://xxoo521.com/2019-12-25-fei-bo-na-qi/

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    if (n === 0) {
        return 0;
    }
    if (n === 1) {
        return 1;
    }

    let a = 0n,
        b = 1n;
    for (let i = 2n; i < n; ++i) {
        let c = a + b;
        a = b;
        b = c;
    }

    return (a + b) % 1000000007n;
};

解法 2: 递归 + 动态规划

根据数学定义:f(n) = f(n - 1) + f(n - 2),代码可以实现为递归形式。

但是以 f(5)为例,它的过程如下:

  1. f(5) = f(4) + f(3)
  2. f(4) = f(3) + f(2)
  3. f(3) = f(2) + f(1)
  4. …省略

注意在第 2 步和第 3 步中,我们计算了 2 次 f(3)的值。当要求的 n 越大的时候,重复计算就会越多,时间复杂度就会越高。

在动态规划的一种做法中,可以借助“备忘录”来实现结果的缓存,避免重复计算

代码如下,时间复杂度是 O(N),空间复杂度是 O(1)。

// ac地址:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof/
// 原文地址:https://xxoo521.com/2019-12-25-fei-bo-na-qi/

/**
 * @param {number} n
 * @return {number}
 */
var fib = function(n) {
    const cache = {
        0: 0n,
        1: 1n
    };
    return Fibonacci(n) % 1000000007n;

    /**
     * @param {number} n
     * @return {number}
     */
    function Fibonacci(n) {
        if (cache[n] !== undefined) {
            return cache[n];
        }

        cache[n] = Fibonacci(n - 1) + Fibonacci(n - 2);
        return cache[n];
    }
};

“备忘录”的其他优点

虽然备忘录用了 O(N)的空间。但是重复计算同个 f(n)的结果时候,时间复杂度是 O(1)。比如之前调用过一次Fibonacci(10),那么 f(10)的结果就缓存在了 cache 中。再次调用函数,直接从缓存读取即可。

同样地,当 n < 10 时候,结果都是从 cache 中直接读取,时间复杂度均是 O(1)。

再推广,当计算 f(20)的时候,n < 10 的结果都计算完了,不需要重复计算。效率是高于第一种循环写法的调用。

总结:备忘录缓存了计算结果,避免了多次调用时的重复计算

更多资料

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×