在刷题中，经常会用到一些常用的数据结构，自己实现费事费力，而且由于语言的原因，运行速度也比较慢。还好官方提供了很多方便的实现。
list
list，用[]表示。类似于C++的vector，Java的ArrayList，是一个可变长度的连续数组。便于插入删除最后一个元素。
常用操作：
-
append，在之后增加一个元素 -
pop，取出最后一个元素。pop(0)可以取出第一个元素，但是一般不推荐用这个来实现队列，因为取出第一个元素后需要复制整个数组。 -
__len__，获取长度。一般通过len(a)的形式调用。
tuple
元组，用()表示。表示多个元素的组合。如(1, 2, 3)
栈
list就是一个栈，操作用append，pop，top指令可以用x[-1]替代
队列
list也可以当队列。操作用append，pop(0)，front指令可以用x[0]替代。一般不推荐。建议使用deque当队列。后续介绍。
dict
dict是字典，用{}表示，如{k: v}。类似于HashMap。
常用操作：
-
keys，获取key的列表。 -
in，判断key是否在dict。如if a in d: -
items，迭代器。如for k, v in d.items(): -
__len__，获取长度。一般通过len(a)的形式调用。 -
get(x, y)，获取key为x的元素，如果x不存在，返回y。 -
setdefault(x, y)，获取key为x的元素，如果x不存在，设置d[x] = y。常用于d.setdefault(k, []).append(1)
set
无序集合。用{}表示，如{a, b, c}。类似于C++的 unordered_set
常用操作：
-
add增加一个元素 -
remove删除一个元素 -
in判断元素是否在set中。如if a in s:
defaultdict
带有默认值的dict。类似于C++的unordered_map。获取不存在的元素时，会自动创建。用法：
from collections import defaultdict
d = defaultdict(list)
d['x'].append(1)
sums = defaultdict(int)
sums['apple'] += 1
deque
双头队列。操作前需要from collections import deque
常用操作：
-
append，在之后（右边）增加一个元素 -
popleft，pop最左边的元素 -
appendleft，在开头（左边）增加一个元素 -
pop，pop最右边的元素
heapq
小根堆。语法比较诡异，用于扩展list来支持堆操作。一般结合tuple来实现复杂的排序逻辑。
常用操作：
-
heapq.heapify(list)，把一个list转化为一个heap，这是一个原地操作，即只影响list中元素的顺序。 -
heapq.heappush(heap, item)push一个元素 -
heapq.heappop(heap)pop一个元素 -
heapq.nlargest(n, iterable)，返回迭代器中最大的n个元素 -
heapq.nsmallest(n, iterable), 返回迭代器中最小的n个元素
堆排序方法：
>>> from heapq import *
>>> def heapsort(iterable):
... h = []
... for value in iterable:
... heappush(h, value)
... return [heappop(h) for i in range(len(h))]
...
>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
使用dijkstra算法求最小路径和：
# 给定一个包含非负整数的 m x n 网格，请找出一条从左上角到右下角的路径，使得路径上的数字总和为最小。
import heapq
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
q = []
q.append((0, 0, 0))
m, n = len(grid), len(grid[0])
dists = [[-1 for i in range(n)] for j in range(m)]
while len(q) > 0:
d, i, j = heapq.heappop(q)
if dists[i][j] != -1:
continue
dists[i][j] = d
if i < m - 1:
heapq.heappush(q, (d + grid[i][j], i + 1, j))
if j < n - 1:
heapq.heappush(q, (d + grid[i][j], i, j + 1))
return dists[m - 1][n - 1] + grid[m - 1][n - 1]
lru_cache
lru_cache用于存储函数的返回值。可以方便实现记忆化搜索。lru_cache第一个参数为max_size，表示存储的步数，设置为None回退为存储所有情况
如：
from functools import lru_cache
import sys
class Solution:
def minPathSum(self, grid: List[List[int]]) -> int:
m, n = len(grid), len(grid[0])
@lru_cache(None)
def dfs(i, j):
if i == m - 1 and j == n - 1:
return grid[i][j]
if i == m or j == n:
return sys.maxsize
rst = min(dfs(i + 1, j) + grid[i][j], dfs(i, j + 1) + grid[i][j])
return rst
return dfs(0, 0)
sys
刷题中常用的两个，一个是获取int最大值，一个是设置最大递归深度。
- 获取int最大值
import sys
sys.maxsize
- 设置最大递归深度，Python默认最大递归深度为1000。
sys.setrecursionlimit(1500)
