LeetCode算法题-Fibonacci Number(Java实现)

这是悦乐书的第250次更新,第263篇原创

01 看题和准备

今天介绍的是LeetCode算法题中Easy级别的第117题(顺位题号是509)。Fibonacci数字,通常表示为F(n),形成一个称为Fibonacci序列的序列,这样每个数字是前两个数字的总和,从0和1开始。即,F(0)= 0,F(1)= 1。对于N> 1,F(N)= F(N-1)+ F(N-2)。给定N,计算F(N)。例如:

输入:2
输出:1
说明:F(2)= F(1)+ F(0)= 1 + 0 = 1。

输入:3
输出:2
说明:F(3)= F(2)+ F(1)= 1 + 1 = 2。

输入:4
输出:3
说明:F(4)= F(3)+ F(2)= 2 + 1 = 3。

注意:0≤N≤30。

本次解题使用的开发工具是eclipse,jdk使用的版本是1.8,环境是win7 64位系统,使用Java语言编写和测试。

02 第一种解法

斐波那契数,最简单的方法是直接使用递归即可。

此解法的时间复杂度是O(n^2),空间复杂度是O(n)。

public int fib(int N) {
    if (N == 0) {
        return 0;
    }
    if (N == 1) {
        return 1;
    }
    return fib(N-1)+fib(N-2);
}


03 第二种解法

借助数组,将每一次计算的值存起来,计算新的数时直接从数组中取即可。

此解法的时间复杂度是O(n),空间复杂度是O(n)。

public int fib2(int N) {
    if (N <= 1) {
        return N;
    }
    int[] num = new int[N+1];
    num[0] = 0;
    num[1] = 1;
    for (int i=2; i<=N; i++) {
        num[i] = num[i-1] + num[i-2];
    }
    return num[N];
}


04 第三种解法

使用临时变量,只存储前两次的计算结果,每进行一次新的计算,都将值进行替换。

此解法的时间复杂度是O(n),空间复杂度是O(1)。

public int fib3(int N) {
    if (N <= 1) {
        return N;
    }
    int result = 0;
    int temp = 0;
    int temp2 = 1;
    for (int i=2; i<=N; i++) {
        result = temp + temp2;
        temp = temp2;
        temp2 = result;
    }
    return result;
}


05 小结

算法专题目前已日更超过三个月,算法题文章117+篇,公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词,获取系列文章合集。

以上就是全部内容,如果大家有什么好的解法思路、建议或者其他问题,可以下方留言交流,点赞、留言、转发就是对我最大的回报和支持!

上一篇:算法(七):斐波那契数列


下一篇:《算法笔记》11.1小节——动态规划专题->动态规划的递归写法和递推写法->问题 A: Fibonacci