LeetCode 斐波那契数算法题解 All In One

509. Fibonacci Number

510. 斐波那契数

最佳实践

性能优化

"use strict";

/**
 *
 * @author xgqfrms
 * @license MIT
 * @copyright xgqfrms
 * @created 2022-09-30
 * @modified
 *
 * @description 509. Fibonacci Number
 * @description 509. 斐波那契数
 * @difficulty Easy
 * @time_complexity O(n)
 * @space_complexity O(n)
 * @augments
 * @example
 * @link https://leetcode.com/problems/fibonacci-number/
 * @link https://leetcode.cn/problems/fibonacci-number/
 * @solutions
 *
 * @best_solutions
 *
 * @refs https://xiaochen1024.com/series/6196129fc1553b002e57bef5/619621d3c1553b002e57bef8
 *
 *
 */

const log = console.log;

function fib(n) {
  if(n === 0) {
    return 0;
  }
  if(n === 1 || n === 2) {
    return 1;
  }
  let n1 = 1;
  let n2 = 1;
  while (n > 2) {
    // ES6 swap
    [n1, n2] = [n2, (n1 + n2)];
    // ES5 swap
    // const temp = n1 + n2;
    // n1 = n2;
    // n2 = temp;
    n -= 1;
  }
  return n2;
}

// 测试用例 test cases
const testCases = [
  {
    input: 0,
    result: 0,
    desc: 'value equal to 0',
  },
  {
    input: 1,
    result: 1,
    desc: 'value equal to 1',
  },
  {
    input: 2,
    result: 1,
    desc: 'value equal to 1',
  },
  {
    input: 5,
    result: 5,
    desc: 'value equal to 5',
  },
  {
    input: 8,
    result: 21,
    desc: 'value equal to 21',
  },
  {
    input: 32,
    result: 2178309,
    desc: 'value equal to 2178309',
  },
  {
    input: 64,
    result: 10610209857723,
    desc: 'value equal to 10610209857723',
  },
  {
    input: 80,
    result: 23416728348467685,
    desc: 'value equal to 23416728348467685',
  },
  {
    input: 90,
    result: 2880067194370816120,
    desc: 'value equal to 2880067194370816120',
  },
  // {
  //   input: 100,
  //   result: 354224848179261915075,
  //   desc: 'value equal to 354224848179261915075',
  // },
];

log(`fib(80) ??? 23416728348467685 => 23416728348467684 =`, 23416728348467685 === 23416728348467684);
// fib(90) ??? 2880067194370816120 => 2880067194370816000 = true

log(`fib(90) ??? 2880067194370816120 => 2880067194370816000 =`, 2880067194370816000 === 2880067194370816120);
// fib(90) ??? 2880067194370816120 => 2880067194370816000 = true

log(`fib(100) 超出最大范围了 ❌ 354224848179261915075 => 354224848179262000000 =`, 354224848179261915075 === 354224848179262000000, `❌\n`);
// fib(100) 超出最大范围了 ❌ 354224848179261915075 => 354224848179262000000 = false

// 超出最大范围了 ❌
// fib(100) => 354224848179261915075 Math (https://r-knott.surrey.ac.uk/Fibonacci/fibtable.html)
// fib(100) => 354224848179262000000 Chrome ❌
// fib(100) => 354224848179262000000 Node.js ❌

// $node ./fib.js

for (const [i, testCase] of testCases.entries()) {
  const result = fib(testCase.input);
  // log(`test case ${i} result: `, result === testCase.result ? `✅ passed` : `❌ failed result = ${result}`, testCase.result);
  log(`test case ${i} result: `, result === testCase.result ? `✅ passed` : `❌ failed`, result);
}

// const testCases = [...new Uint8Array(100)].map((item, i) => ({
//   input: i,
//   result: fib(i),
//   desc: `value equal to ${fib(i)}`,
// }));
// ...spread 突破， 2**8 = 256 的 number 最大值的大小限制 ✅
// const testCases = [...new Uint8Array(100)].map((item, i) => i + 1);
// for (const [i, testCase] of testCases.entries()) {
//   const result = fib(testCase);
//   log(`

标签：case,fib,const,契数,题解,斐波,result,test,input	

From： https://www.cnblogs.com/xgqfrms/p/16748194.html