剑指 Offer 10- I. 斐波那契数列

本问题对应的 leetcode 原文链接:剑指 Offer 10- I. 斐波那契数列
本问题对应打卡任务:【杂题】Offer 10- I. 斐波那契数列

问题描述

写一个函数,输入 n ,求斐波那契(Fibonacci)数列的第 n 项(即 F(N))。斐波那契数列的定义如下:

F(0) = 0, F(1) = 1;
F(N) = F(N – 1) + F(N – 2), 其中 N > 1.

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。

答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

示例 1:

输入:n = 2
输出:1

示例 2:

输入:n = 5
输出:5

限制:

  • 0 <= n <= 100

解题思路

视频讲解直达: 本题视频讲解

代码实现

    public int fib(int n) {
        if( n <= 1){
            return n;
        }

        int a = 0;
        int b = 1;
        int c = 0;;

        for(int i = 2; i <= n; i++){
            c = (a + b) % 1000000007;
          // a 原本指向的值不会在用到,所以让 a 保存 b,b 保存 c,之后重新计算 c,如此循环
            a = b;
            b = c;
        }

        return c;
    }

时间复杂度:O(n)
额外空间复杂度:O(1)

发表回复

后才能评论