本文記錄LeetCode刷題一些知識(shí)點(diǎn)，水平有限還望多多指正
斐波那契序列 Tn 定義如下：
T0 = 0, T1 = 1, 且在 n >= 0 的條件下 Tn+2 = Tn + Tn+1
給你整數(shù) n，請(qǐng)返回第 n 個(gè)泰波那契數(shù) Tn 的值。
方法一：使用遞歸
class Solution:
def fabonacci(self, n: int) -> int:
if n<2:return n
return self.tribonacci(n-1)+self.tribonacci(n-2)
結(jié)果：超時(shí)
改進(jìn)：使用lru緩存加速
import functools
class Solution:
@functools.lru_cache(None)
def fabonacci(self, n: int) -> int:
if n<2:return n
return self.tribonacci(n-1)+self.tribonacci(n-2)
結(jié)果：38ms 13.8 MB
方法二：使用循環(huán)
class Solution:
def fabonacci(self, n: int) -> int:
a, b = 0, 1
for i in range(n) :
a, b = b, a+b
return a
結(jié)果：40ms 13.8 MB
Note:functools模塊
functools模塊用于高階函數(shù)，作用與或者返回其它函數(shù)的函數(shù)。一般來說，對(duì)于該模塊，任何可調(diào)用對(duì)象都可以視為一個(gè)函數(shù)
-
@functools.lru_cache(maxsize=128, typed=False)：該函數(shù)裝飾器使用 LRU緩存算法來緩存相對(duì)耗時(shí)的函數(shù)結(jié)果，避免傳入相同的參數(shù)重復(fù)計(jì)算。同時(shí)，緩存并不會(huì)無限增長(zhǎng)，不用的緩存會(huì)被釋放。其中 maxsize 參數(shù)用于設(shè)置緩存占用的最大字節(jié)數(shù)，typed 參數(shù)用于設(shè)置將不同類型的緩存結(jié)果分開存放。
除此之外模塊中還有：
functools.cmp_to_key(func)：將老式的比較函數(shù)（func）轉(zhuǎn)換為關(guān)鍵字函數(shù)（key function）。在 Python 3 中比較大小、排序都是基于關(guān)鍵字函數(shù)的，Python 3 不支持老式的比較函數(shù)。@functools.total_ordering：這個(gè)類裝飾器（作用類似于函數(shù)裝飾器，只是它用于修飾類）用于為類自動(dòng)生成比較方法。通常來說，開發(fā)者只要提供 lt()、le()、gt()、ge() 其中之一（最好能提供 eq() 方法），@functools.total_ordering裝飾器就會(huì)為該類生成剩下的比較方法。functools.partial(func, *args, **keywords)：該函數(shù)用于為 func 函數(shù)的部分參數(shù)指定參數(shù)值，從而得到一個(gè)轉(zhuǎn)換后的函數(shù)，程序以后調(diào)用轉(zhuǎn)換后的函數(shù)時(shí)，就可以少傳入那些己指定值的參數(shù)。functools.partialmethod(func, *args, **keywords)：該函數(shù)與上一個(gè)函數(shù)的含義完全相同，只不過該函數(shù)用于為類中的方法設(shè)置參數(shù)值。functools.reduce(function, iterable[, initializer])：將初始值（默認(rèn)為 0，可由 initializer 參數(shù)指定）、迭代器的當(dāng)前元素傳入 function 函數(shù)，將計(jì)算出來的函數(shù)結(jié)果作為下一次計(jì)算的初始值、迭代器的下一個(gè)元素再次調(diào)用 function 函數(shù)……依此類推，直到迭代器的最后一個(gè)元素。＠functools.singledispatch：該函數(shù)裝飾器用于實(shí)現(xiàn)函數(shù)對(duì)多個(gè)類型進(jìn)行重載。比如同樣的函數(shù)名稱，為不同的參數(shù)類型提供不同的功能實(shí)現(xiàn)。該函數(shù)的本質(zhì)就是根據(jù)參數(shù)類型的變換，將函數(shù)轉(zhuǎn)向調(diào)用不同的函數(shù)。functools.update_wrapper(wrapper, wrapped, assigned=WRAPPER_ASSIGNMENTS, updated=WRAPPER_UPDATES：對(duì) wrapper 函數(shù)進(jìn)行包裝，使之看上去就像 wrapped（被包裝）函數(shù)。@functools.wraps(wrapped, assigned=WRAPPER_ASSIGNMENTS, updated=WRAPPER_UPDATES)：該函數(shù)裝飾器用于修飾包裝函數(shù)，使包裝函數(shù)看上去就像 wrapped 函數(shù)。
通過介紹不難發(fā)現(xiàn)，functools.update_wrapper 和 ＠functools.wraps 的功能是一樣的，只不過前者是函數(shù)，因此需要把包裝函數(shù)作為第一個(gè)參數(shù)傳入；而后者是函數(shù)裝飾器，因此使用該函數(shù)裝飾器修飾包裝函數(shù)即可，無須將包裝函數(shù)作為第一個(gè)參數(shù)傳入。
