需要掌握的地方
- 切片相关（倒序输出链表）
-
list[i:j]包含list[seq],其中i <= seq < j - Python 中
list[::-1]和list.reverse()的区别
list相关方法实现（两个栈实现队列）
sorted、sort等排序使用了 Timesort 排序方法
pop如何实现的根据二叉树中序和前序遍历结果复原二叉树
functools.lru_cache（斐波那契）斐波那契数（青蛙跳台阶）
-
列递归法时间复杂度为 O(2^n), fib(5）调用过程如下：
fib(5) 递归过程
递归法 Python 伪代码如下：
if n < 2:
return n
return fbi[n - 1] + fbi[n -2]
- 非递归法时间复杂度 O(n), 空间复杂度 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
- 尾递归法
