刷题之旅从数组类型的题目开始。第二十二道题目是斐波那契数,对应leetcode的题号为509。

image

题目描述

斐波那契数,通常用 F(n) 表示,形成的序列称为斐波那契数列。该数列由 0 和 1 开始,后面的每一项数字都是前面两项数字的和。也就是:

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

给定 N,计算 F(N)。

示例 1:

1
2
3
输入:2
输出:1
解释:F(2) = F(1) + F(0) = 1 + 0 = 1.

示例 2:

1
2
3
输入:3
输出:2
解释:F(3) = F(2) + F(1) = 1 + 1 = 2.

示例 3:

1
2
3
输入:4
输出:3
解释:F(4) = F(3) + F(2) = 2 + 1 = 3.

提示:

0 ≤ N ≤ 30

解题思路

斐波那契数是我们的老朋友了,是一道经典的入门递归的题目。并且基于递归版本去改为非递归版本提高执行效率。递归版本很好写:

1
2
3
4
5
6
7
8
class Solution {
public int fib(int N) {
if(N == 0 || N == 1){
return N;
}
return fib(N-2) + fib(N-1);
}
}

不过我们知道递归的本质是调用了系统栈,优点是代码简洁,缺点是由于存在大量重复的计算,效率很低。本题的N最大为30还能不超时,再大点这个解法必超时。

1
2
执行用时 :11 ms, 在所有 Java 提交中击败了33.63%的用户
内存消耗 :33 MB, 在所有 Java 提交中击败了37.58%的用户

以下是完成斐波那契数计算的经典方法,用三个变量来承载前两个数字,从而计算出当前的数。就不再赘述分析啦。时间复杂度为O(n),空间复杂度为O(1)。

提交代码

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