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函数时性能上的提升,避免每一次都去计算。但是此方法会有并发的线程安全问题(这里暂不考虑,考虑的话方法加锁即可)

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


觉得内容还不错?打赏个钢镚鼓励鼓励!!👍

彩虹烘鞋器可伸缩快速干鞋机家用旅行便携式烤鞋暖鞋器成人儿童安全烘干器鞋靴除湿机 伸缩款Q8103
¥46.00
番茄红素维生素E软胶囊增强免疫力喜倍力搭配片男性成人保健品 1瓶装60粒
¥46.00
卫龙魔芋爽600g香辣素毛肚休闲零食大礼包情人节送女友生日礼物辣条
¥35.90
瓦力【抗蓝光】荣耀80pro钢化膜荣耀80pro手机膜 曲面防摔耐磨保护手机贴膜
¥41.80
墨斗鱼 无火香薰120ml蓝风铃香型0130卧室香氛藤条香薰送男友女生情人节创意实用礼物室内空气清新剂持久留香
¥39.80
实瞳SEED 可芙蕾Sister原装进口 日本美瞳小直径 男女彩色隐形眼镜月抛 1片装 流韵 700度
¥32.00
天莱香牛 国产新疆 有机原切肥牛肉卷300g 谷饲排酸冷冻牛肉 火锅食材
¥42.90
年年好1.2米*5付空白手写对联《经典版》2023兔年通用
¥27.90