在刷题中，经常会用到一些常用的数据结构，自己实现费事费力，而且由于语言的原因，运行速度也比较慢。还好官方提供了很多方便的实现。

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)