剑指Offer 10-Ⅰ斐波那契数列

mario 2020年09月12日 78次浏览

前言

在leetcode上做了几天题了,每天一道简单和中等,没有一题是独立做出来的。BUT!今天,我站起来了,我终于独立完成一个题了。

image.png
好吧,虽然这题很简单T-T,来看看题目。

image.png

纵使简单,我依旧提交了四次才对,没考虑到一些边界case。

分析题目

斐波那契数列的特点是每一项等于前两项之和,也就是说每一项都可以由前两项推导出来,动态规划的味道有没有。

解法1

class Solution {
    public int fib(int n) {
        if (n == 0) return 0;
        if (n == 1) return 1;
        int[] res = new int[n + 1];
        res[0] = 0;
        res[1] = 1;
        int mod = 1000000007;
        for (int i = 2; i <= n; i++) {
            res[i] = (res[i - 1] + res[i - 2]) % mod;
        }
        return res[n];
    }
}

我想到的是这样的解法,时间复杂度和空间复杂度都是O(N)

解法2

class Solution {
    public int fib(int n) {
        if(n == 0) return 0;
        int fn0 = 0;
        int fn1 = 1;
        int temp;
        for(int i = 2; i <= n; i++){
            temp = fn0 + fn1;
            fn0 = fn1;
            fn1 = temp% 1000000007; // 每次运算都取模 避免越界
        }
        return fn1;
    }
}

评论区的另一种解法,fn0和fn1两个难兄难弟一前一后往前走,不用定义数组,时间复杂度是O(N),空间复杂度O(1),妙啊。