剑指 Offer 10- I. 斐波那契数列

剑指 Offer 10- I. 斐波那契数列

题目

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

F(0) = 0, F(1) = 1

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

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

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

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

提示:

0 <= n <= 100

解题思路

根据斐波那契数列,我们可以利用两个变量来进行对数字赋值,来减少时间和空间上的开支。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int fib(int n) {
if(n==0){
return 0;
}
if(n==1){
return 1;
}
int a=0,b=1,res=0;
for(int i=1;i<n;i++){
res=(a+b)%1000000007;
a=b;
b=res;
}
return res;
}
}

复杂度分析

时间复杂度:O(n)

空间复杂度:O(1)

资源

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

剑指 Offer 10- I. 斐波那契数列

http://example.com/2021/03/30/10- I 斐波那契数列/

Author

John Doe

Posted on

2021-03-30

Updated on

2021-06-08

Licensed under

You need to set install_url to use ShareThis. Please set it in _config.yml.
You forgot to set the business or currency_code for Paypal. Please set it in _config.yml.

Comments

You forgot to set the shortname for Disqus. Please set it in _config.yml.