509. 斐波那契数

题目:https://leetcode-cn.com/problems/fibonacci-number/

代码:

方法一:递归

class Solution {

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

}

递归是最简单的一个解法,但是性能上不行,因为会有很多重复的计算,比如计算fib(5),就要重复的调用5次fib(1),性能严重浪费。

方法二:循环

class Solution {

    public int fib(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];
    }

}

使用一个数组存储数据,第i个数的值就等于第i-1和第i-2的值之和。相比第一种递归的方法减少了大量重复的计算。

方法三:带缓存的循环

class Solution {

    private static int[] cache = new int[]{0, 1};

    public int fib(int N) {
        int i = cache.length;
        if (N >= i) {
            cache = Arrays.copyOf(cache, N + 1);
            for (; i <= N; i++) {
                cache[i] = cache[i - 1] + cache[i - 2];
            }
        }
        return cache[N];
    }

}

方法三是方法二的优化版本,通过将数组缓存起来的方式,实现多次调用fib函数时性能上的提升,避免每一次都去计算。但是此方法会有并发的线程安全问题(这里暂不考虑,考虑的话方法加锁即可)

方法四:数学解法

采用各种数学公式直接计算值,具体参考百度。

支付宝搜索:344355 领取随机红包

如果文章对您有帮助的话,欢迎老板打赏↑↑↑(请我吃饭😋