剑指Offer10-斐波那契数列

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

一解

直接使用递归:


class Solution:

    def fib(self, n: int) -> int:

        if n == 0 or n == 1:

            return n

        return (self.fib(n-1)+self.fib(n-2)) % 1000000007

运算超时!!

因为递归会出现大量重复运算:

二解

每一个斐波那契数由前两个斐波那契数组成,设置 a 和 b :

  • a:前二个斐波那契数a = b

  • b:前一个斐波那契数b = a + b

计算 n 次 a 和 b ,即可得到第 n 次斐波那契数列。以 3 为例,其运算过程为(0, 1, 1, 2, 3):

当 n 为 2 时, 1 由 1 + 0 计算得出:

image

当 n 为 3 时,2 由 1 + 1 计算得出:

image

当 n 为 4 时,3 由 1 + 2 计算得出:

image


class Solution:

    def fib(self, n: int) -> int:

        a, b = 0, 1

        for _ in range(n):

            a, b = b, a + b

        

        return a % 1000000007

1 Like
关闭