题目
写一个函数,输入 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)各一次即可。