LeetCode509. 斐波那契数列

62 views次阅读
没有评论

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

F(0) = 0, F(1) = 1 F(N) = F(N – 1) + F(N – 2), 其中 N > 1. 给定 N,计算 F(N)。

示例 1:

输入:2 输出:1 解释:F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2:

输入:3 输出:2 解释:F(3) = F(2) + F(1) = 1 + 1 = 2.

答案看这里哦👇️

  function fib (num) {
    if (num <= 0 ) { return 0;}
    if (num === 1 || num === 2) { return 1;}
    if (num > 2) {
      let arr = [0, 1];
      for (let i = 2; i <= num; i++) {
        arr[i] = arr[i-1] + arr[i-2];
      }
      return arr[num];
      // return arr;
    }
  }
  let num = 20;
  console.log("20的斐波那契数是:",fib(num)); // 6765

进一步优化

通过上面的例子,可以发现有些结果是可以重复利用的,比如fib(3)、fib(4)、fib(5)等等,在计算过程中都会被使用两次,所以可以进一步优化,提高效率。

第一种

  const fib  = (num) => {
    if (num < 2) return num;
    let prev = 1, next = 1;
    for (let i = 3; i <= num; i++) {
      let sum = prev + next;
      prev = next;
      next = sum;
    }
    return next;
  };
  let num = 20;
  console.log("20的斐波那契数是:", fib(num)); // 6765

第二种

  const fib  = (num) => {
    if (num < 2) return num;
    let prev = 0, next = 1;
    while (num--) {
      [prev, next] = [next, prev + next];
    }
    return prev;
  };
  let num = 20;
  console.log("20的斐波那契数是:", fib(num)); // 6765

第三种

  let obj = {
    0: 0,
    1: 1
  };
  const fib  = (num) => {
    if (obj[num] === undefined) obj[num] = fib(num - 1) + fib(num - 2);
    return obj[num];
  };
  let num = 20;
  console.log("20的斐波那契数是:", fib(num)); // 6765
1
guxuerui
版权声明:本站原创文章,由guxuerui于2020年07月27日发表,共计1856字。
转载提示:除特殊说明外本站文章皆由CC-4.0协议发布,转载请注明出处。
评论(没有评论)
Loading...