【每日算法】NC65 斐波那契数列1

发表于

这是我参与11月更文挑战的第17天，活动详情查看：2021最后一次更文挑战。

描述

大家都知道斐波那契数列，现在要求输入一个正整数 n ，请你输出斐波那契数列的第 n 项。

斐波那契数列是这样一个数列：1、1、2、3、5、8、13、21、34….

就是第一和第二位都是 1，后面的数都是前面两个数之和。

数据范围：1 ≤ n ≤ 39

要求：空间复杂度 O(1)，时间复杂度 O(n) ，本题也有时间复杂度 O(logn)的解法

输入描述：

一个正整数n

返回值描述：

输出一个正整数。

做题

做这种题，肯定不用递归啦，递归🐕都不用。

肯定需要两个变量：former、latter，前者用来存储比较旧的数据，后者用来存储当前位置的数据，当要求出下一位斐波那契数，就只需要把这两个变量相加就可以了，所以这两个变量是肯定要创建的，创建数组就没必要了，我们只是要一个数而已。

两个变量相加的结果就直接存放到 latter，这里想要在保存原来 latter 的值，就只能再创建一个变量来存储了。

还有循环，直接从 2 开始循环，当 n 小于或等于 2 时，就不走循环，直接返回 latter(1)。

1
2
3
4
5
6
7
8
9
10
11
ini复制代码public int Fibonacci(int n) {
    int former=1;
    int latter=1;
    int temp=0;
    for(int i=2;i<n;i++){
        temp=latter;
        latter+=former;
        former=temp;
    }
    return latter;
}

运行！

image.png

运行速度还是挺不错的，占用内存就比较拉跨了。

再试

网上说的斐波那契数组最佳的解的时间复杂度是 log(n)，我们肯定要想最优的解看齐啦。

我也找了很多网上的博客，很多是跟线性代数有关的，但更多的是拿时间度为 n 的来凑数，搞得我看了半天，最后这不是我已经写出来的吗？！

未完待续。。。

这里是程序员徐小白，【每日算法】是我新开的一个专栏，在这里主要记录我学习算法的日常，也希望我能够坚持每日学习算法，不知道这样的文章风格您是否喜欢，不要吝啬您免费的赞，您的点赞、收藏以及评论都是我下班后坚持更文的动力。

本文转载自: 掘金

开发者博客 – 和开发相关的 这里全都有

0%