剑指 Offer 10- I. 斐波那契数列
文章目录

题目

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

1
2
3
4

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

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

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

链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/**
* @param {number} n
* @return {number}
*/




/* 无脑的想着使用递归是不正确的 */
/* 递归计算会超时 */
// var fib = function (n) {
// if (n < 2) return n
// return (fib(n - 1) + fib(n - 2)) % (1e9 ^ 7)
// };




/* 使用最普通的字典和哈希表实现, 这个都不用使用到数组 */
/* 可以再进行一次优化, 因为只需要记住三个数字就可以了. */
var fib = function(n) {
const map = {}
for (let i = 0; i <= n; i++) {
if (i < 2) map[i] = i
else {
map[i] = (map[i - 1] + map[i - 2]) % (1e9 ^ 7)
// console.log(map[i])
}
}

return map[n]
};