需要掌握的地方
- 切片相關(guān)（倒序輸出鏈表）
-
list[i:j]包含list[seq],其中i <= seq < j - Python 中
list[::-1]和list.reverse()的區(qū)別
list相關(guān)方法實(shí)現(xiàn)（兩個(gè)棧實(shí)現(xiàn)隊(duì)列）
sorted、sort等排序使用了 Timesort 排序方法
pop如何實(shí)現(xiàn)的根據(jù)二叉樹中序和前序遍歷結(jié)果復(fù)原二叉樹
functools.lru_cache（斐波那契）斐波那契數(shù)（青蛙跳臺(tái)階）
-
列遞歸法時(shí)間復(fù)雜度為 O(2^n), fib(5）調(diào)用過(guò)程如下：
fib(5) 遞歸過(guò)程
遞歸法 Python 偽代碼如下：
if n < 2:
return n
return fbi[n - 1] + fbi[n -2]
- 非遞歸法時(shí)間復(fù)雜度 O(n), 空間復(fù)雜度 O(1)。
非遞歸法 Python 偽代碼如下：
fib_pre = 1
fib_ppre = 0
if n < 2:
return n
for i in range(2, n + 1):
temp = fbi_pre
fbi_pre = fbi_ppre + fbi_pre
fbi_ppre = temp
return fbi_pre
- 尾遞歸法
