此公众号会发表计算机考研(初复试信息)、夏令营等资料,方便考研人对信息的获取,节约自身查找资料的时间,回复408,可获得数据结构、操作系统、计算机网络、计算机组成原理全科资料
使用functools模块的lur_cache装饰器,可以缓存最多 maxsize 个此函数的调用结果,从而提高程序执行的效率,特别适合于耗时的函数,也就是说对于相同的计算不会再重复计算,直接在缓存中取出值,像动态规划中的数组,存储好已计算的值,为将来直接使用,适用于递归。参数maxsize
为最多缓存的次数,如果为None,则无限制,设置为2n时,性能最佳;如果 typed=True
(注意,在 functools32 中没有此参数),则不同参数类型的调用将分别缓存,例如 f(3) 和 f(3.0)。
被 lru_cache 装饰的函数会有 cache_clear
和 cache_info
两个方法,分别用于清除缓存和查看缓存信息。
例如:
写一个函数,输入 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。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/fei-bo-na-qi-shu-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
在这道题目中如果不加入缓存机制,则会超时,使用缓存机制可通过
python3解法
from functools import lru_cache
class Solution:
@lru_cache(None)
def fib(self, n: int) -> int:
if n<2:
return n
return (self.fib(n-1)+self.fib(n-2))%1000000007