微信公众号：路人zhang
扫码关注微信公众号

回复“面试手册”，获取本站PDF版

回复“简历”，获取高质量简历模板

回复“加群”，加入程序员交流群

回复“电子书”，获取程序员类电子书

当前位置： 算法 > 剑指offer > 10-1.斐波那契数列

10-1.斐波那契数列

题目描述

写一个函数，输入 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

题解 1

(迭代) O(n)

a 存放 fib(n) 的结果，b 存放 fib(n + 1) 的结果。

时间复杂度

O(n)

空间复杂度

O(1)

C++ 代码

class Solution {

const int mod = 1e9 + 7;
public:
    int fib(int n) {
        if (n <= 1) return n;
        int a = 0, b = 1;
        while ( -- n) {
            int c = (a + b) % mod;
            a = b, b = c;
        }
        return b;
    }
};

Java 代码

class Solution {
    private static final int mod = 1000000007;
    
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        int a = 0, b = 1;
        while ( -- n > 0) {
            int c = (a + b) % mod;
            a = b;
            b = c;
        }
        return b;
    }
}

Python 代码

class Solution:
    def fib(self, n: int) -> int:
        if n <= 1:
            return n
        a, b = 0, 1
        while n > 1:
            c = (a + b) % (10 ** 9 + 7)
            a, b = b, c
            n -= 1
        return b

题解 2 （超时！！！）

(递归) O(2^n)

递归的逻辑：

  • n <= 1，直接返回 n
  • 否则返回 fib(n – 1) + fib(n – 2)

时间复杂度

O(2^n)

空间复杂度

递归系统栈所需空间 O(n)。

C++ 代码

class Solution {
public:
    const int MOD = 1000000007;

    int fib(int n) {
        if (n <= 1) return n;
        return (fib(n - 1) + fib(n - 2)) % MOD;
    }
};

Java 代码

class Solution {
    private static final int MOD = 1000000007;
    
    public int fib(int n) {
        if (n <= 1) {
            return n;
        }
        return (fib(n - 1) + fib(n - 2)) % MOD;
    }
}

Python 代码

class Solution:
    def fib(self, n: int) -> int:
        MOD = 1000000007
        
        if n <= 1:
            return n
        return (self.fib(n - 1) + self.fib(n - 2)) % MOD

本文由读者提供，Github地址：https://github.com/tonngw

点击面试手册，获取本站面试手册PDF完整版

剑指offer