剑指offer 09. 斐波那契数列

简介: 剑指offer 09. 斐波那契数列

题目描述

输入一个整数 n ,求斐波那契数列的第 n 项。

假定从 0 开始,第 0 项为 0。

数据范围

0≤n≤39

样例

输入整数 n=5 
返回 5


方法一:递推 O(n)

我们可以只用常数个变量来进行计算,具体思路如下:


初始化 a=0 和 b=1 ,如果 n=0 则直接返回 a=0 。

如果 n>0 则计算 c=a+b ,然后将 a 和 b 往后移一位即 a=b,b=c 。

来看个例子加深一下印象,假设传入参数 n 为 4 :


第一步: 初始化变量 a=0,b=1 。


c05d5656515048ee8d38bd21f88067ff.png

第二步: 开始循环,计算 c=a+b=1a 更新为 bb 更新为 c ,并且 n 要减 1

第三步 ~ 第五步: 和第二步一样,类似于是一个滚动数组,一直往后面移动。

第六步: 直到 n0 ,返回 a 就是最终的答案。

b458c5d8e77941809437d5c61fa8d733.png

class Solution {
public:
    int Fibonacci(int n) {
        int a = 0, b = 1;
        while (n--)
        {
            int c = a + b;
            a = b, b = c;
        }
        return a;
    }
};

欢迎大家在评论区交流~

目录
打赏
0
0
0
0
37
分享
相关文章
|
9月前
|
简单斐波那契
简单斐波那契
87 0
|
9月前
斐波那契(快速矩阵幂)
斐波那契(快速矩阵幂)
46 0
LeedCode_04-斐波那契数列(剑指offer-10)
LeedCode_04-斐波那契数列(剑指offer-10)
【剑指offer】-斐波那契数列-07/67
【剑指offer】-斐波那契数列-07/67
|
9月前
剑指Offer LeetCode 面试题10- I. 斐波那契数列
剑指Offer LeetCode 面试题10- I. 斐波那契数列
49 0
剑指offer-9.斐波那契数列
剑指offer-9.斐波那契数列
61 1
剑指offer(C++)-JZ10:斐波那契数列(时间复杂度O(logn)解法)
剑指offer(C++)-JZ10:斐波那契数列(时间复杂度O(logn)解法)
剑指Offer - 面试题10:斐波那契数列
剑指Offer - 面试题10:斐波那契数列
99 0
斐波那契数列(剑指offer 10-I)
斐波那契数列(剑指offer 10-I)
119 0