刷题之旅从数组类型的题目开始。第二十二道题目是斐波那契数，对应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;
    }
}