▼点击下方卡片关注我
▲点击上方卡片关注我
刷算法题是不少小伙伴的痛点，看别人写的解法头都大了。不过别慌，今天咱聊聊Python刷题中那些好用的数据结构和算法套路，学会这些，刷题能省不少事。
数组和列表的花式玩法
Python里的列表可太强大了，咱们看看几个特别好用的操作：
1
# 快速创建特定数值的列表2
nums = [0] * 5 # [0， 0， 0， 0， 0]3
matrix = [[0] * 3 for _ in range(3)] # 3x3的二维数组5
# 切片翻转，比reverse()更优雅6
arr = [1， 2， 3， 4， 5]7
reversed_arr = arr[：：-1] # [5， 4， 3， 2， 1]9
# 列表推导式，一行搞定过滤和转换10
nums = [1， -2， 3， -4， 5]11
positive_nums = [x for x in nums if x > 0] # [1， 3， 5]
⚠️ 小贴士：
创建二维数组别用
[[0] * 3] * 3，这样会让所有行共享同一个引用数组切片产生的是新对象，占用额外空间
列表推导式虽然好用，但别嵌套太多层，可读性会变差
字典和集合的加速法则
说到查找，字典和集合绝对是提速利器：
1
# 计数神器 Counter2
from collections import Counter3
chars = “hello world”4
char_count = Counter(chars) # {'l'： 3， 'o'： 2， ...}6
# 默认值字典，再也不用担心KeyError7
from collections import defaultdict8
graph = defaultdict(list)9
graph[1].append(2) # 不需要先初始化graph[1]11
# 集合运算12
set1 = {1， 2， 3}13
set2 = {3， 4， 5}14
intersection = set1 & set2 # {3}15
union = set1 | set2 # {1， 2， 3， 4， 5}
队列和栈的妙用
解决一些特定问题，队列和栈简直是神器：
1
# 双端队列2
from collections import deque3
queue = deque([1， 2， 3])4
queue.append(4) # 右边加入5
queue.appendleft(0) # 左边加入6
queue.pop() # 右边弹出7
queue.popleft() # 左边弹出9
# 优先队列10
import heapq11
heap = []12
heapq.heappush(heap， 5)13
heapq.heappush(heap， 1)14
smallest = heapq.heappop(heap) # 1
⚠️ 小贴士：
deque的插入和删除是O(1)，比列表快多了
heapq默认是小顶堆，要实现大顶堆可以把数字取负
用栈解决括号匹配问题特别好使
递归和回溯的套路
递归看着吓人，其实套路很简单：
1
def fibonacci(n， memo=None)：2
if memo is None：3
memo = {}4
if n in memo：5
return memo[n]6
if n <= 1：7
return n8
memo[n] = fibonacci(n-1， memo) + fibonacci(n-2， memo)9
return memo[n]11
# 回溯模板12
def backtrack(路径， 选择列表)：13
if 满足结束条件：14
保存结果15
return17
for 选择 in 选择列表：18
做选择19
backtrack(路径， 选择列表)20
撤销选择
⚠️ 小贴士：
记忆化递归能大幅减少重复计算
递归一定要有base case，避免无限递归
回溯问题记住“选择”和“撤销选择”的套路
写算法题的时候，光知道数据结构不够，还得会分析时间复杂度。比如数组查找O(n)，字典查找O(1)，排序一般是O(nlogn)。多刷几道题，这些慢慢就有感觉了。
代码写多了你就发现，其实很多题目都是换汤不换药。掌握这些基本套路，啥题都不怕。
推 荐 阅 读
点赞分享
让钱和爱流向你
