面試的時候經常會問到怎麼用 JavaScript 解費氏數列,面試到後面整理了一下常見的 3 種解法:
首先說明一下費氏數列:[0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55] ,通常會請你用 JavaScript 求解陣列的最後一個值。
Table of Contents
1. JavaScript 費氏數列 – 遞迴解
// Time complexity = O(2^n)
function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
fib(10)
// 55
fib(6)
// 8
2. JavaScript 費氏數列 – 迴圈解
// Time Complexity = O(n)
function fib(n) {
const arr = [0, 1];
for (let i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + arr[i - 2];
}
return arr[n];
}
fib(10)
// 55
fib(6)
// 8
3. JavaScript 費氏數列 – Memoization
// Time Complexity = O(n)
// 好理解的版本
function fib(n) {
if (!fib.cache) {
fib.cache = {
0: 0,
1: 1
};
}
if (fib.cache[n] !== undefined) {
return fib.cache[n];
}
fib.cache[n] = fib(n - 1) + fib(n - 2);
return fib.cache[n];
}
// 其他函數通用版
function memoize(fn) {
const cache = {};
return function(...args) {
if (cache[args]) {
return cache[args];
}
const result = fn.apply(this, args);
cache[args] = result;
return result;
}
}
function fib(n) {
if (n < 2) {
return n;
}
return fib(n - 1) + fib(n - 2);
}
fib = memoize(fib);
fib(10)
// 55
fib(6)
// 8
看完這篇文章是不是想換工作了呢(咦?那就千萬別錯過 2024 職涯博覽會!想換工作的,有機會在博覽會遇見更好的另一半,不想換工作的,有機會在博覽會遇見更好的工作!趕快點擊下面的 banner,拯救你的人生!!!https://s.yourator.co/jimmy
如果覺得我的文章有幫助的話,歡迎幫我的粉專按讚哦~謝謝你!