题目描述
写一个函数,输入 n
,求斐波那契(Fibonacci)数列的第 n
项(即 F(N)
)。斐波那契数列的定义如下:
1 | F(0) = 0, F(1) = 1 |
斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。
示例 1:
1 | 输入:n = 2 |
示例 2:
1 | 输入:n = 5 |
提示:0 <= n <= 100
题目链接
题目解答
解法一
由递推公式,我们很容易写出求解数列第n
项的递归形式,当n
比较小的时侯可以直接得到结果,但是递归求解的时间复杂度是指数级别的,随着n
的增大,计算所需耗费的时间也是呈指数增长,当n
比较大的时侯,不推荐使用递归求解。
时间复杂度:$O(2^n)$ 空间复杂度:$O(1)$
1 | class Solution { |
超出时间限制,最后执行的输入:43
解法二
从斐波那契数列的定义出发,我们可以使用迭代法求解数列的第n
项。
时间复杂度:$O(n)$ 空间复杂度:$O(1)$
1 | class Solution { |
执行用时:0 ms, 在所有 Java 提交中击败了100.00%的用户
内存消耗:35.1 MB, 在所有 Java 提交中击败了88.73%的用户