剑指Offer[10-1]-斐波那契数列

题目

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

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

斐波那契数列由 0 和 1 开始,之后的斐波那契数就是由之前的两数相加而得出。
答案需要取模 1e9+7(1000000007),如计算初始结果为:1000000008,请返回 1。

python代码

class Solution(object):
    def __init__(self):
        self._a = 10**9+7
    def fib(self, n):
        if n<=1:
            return n
        f0 = 0
        f1 = 1
        f_sum = 0
        for i in range(n-1):
            f_sum = f0+f1
            f0,f1 = f1,f_sum
        return f_sum%self._a

上述代码直接从斐波那契数列的定义出发,逐步求出所需的值。

class Solution(object):
    def __init__(self):
        self._a = 10**9+7
    def fib(self, n):
        if n<=1:
            return n
        return self.fib(n-1)+self.fib(n-2)

当然我们还可以使用递归,因为斐波那契数列的特殊规律,可以很简洁的构造出递归结构(注意:上述的递归代码在leetcode中判定为超时

拓展

这道题考察的比较常规,无论是直接法还是递归法都是容易想到的。在后面重刷时无意间看到别人分享的代码,发现了一个有趣的做法,使递归在leetcode的判定系统中顺利通过

class Solution:
    from functools import lru_cache
    @lru_cache(None)
    def fib(self, n: int) -> int:
        if n<=1:
            return n
        return (self.fib(n-1)+self.fib(n-2))%1000000007
  • 代码需要在Python3中运行
  • 使用了lru_cache修饰器,它减少了fib函数计算的次数,当fib遇到之前计算过得值时,直接从缓存取值。

lru_cache

python 标准库中的 functools.lru_cache 装饰器实现了一个 LRU 算法的缓存,用来缓存方法所有参数与返回值的对应关系,用来提升一个方法频繁用相同参数调用场景下的性能。

比如对于fib(4),我们需要计算fib(0)两次,fib(1)三次,fib(2)两次,fib(3)一次,当n更大时,重复计算的项也会增加,相同项重复的次数也会增加,所以lru_cache装饰器就是将之前计算过得函数输出缓存下来,当后面再次遇到相同的输入值时,直接从缓存区拿出对应的函数输出。当使用lru_cache后,再去计算fib(4),我们实际g只需计算fib(0)、fib(1)、fib(2)、fib(3)各一次即可。

发表评论

电子邮件地址不会被公开。