算法刷题必备：Python 高效技巧全解析

一、列表 List：刷题最核心的数据结构

Python 的列表 List 基本对应其他语言的 Array，但功能更强大。

1.1 初始化技巧

一维数组初始化：

# 方法1：列表推导式（推荐）
l = [0 for _ in range(n)]

# 方法2：乘法初始化（注意：仅适用于不可变元素）
l = [0] * n

# ⚠️ 警告：乘法初始化二维数组的陷阱
# 错误做法（所有行共享同一引用）
wrong = [[0] * 3] * 3
wrong[0][0] = 1 # 所有行的第一个元素都变成1！

# 正确做法
correct = [[0 for _ in range(3)] for _ in range(3)]

二维数组初始化：

rows, cols = 3, 4
matrix = [[0 for _ in range(cols)] for _ in range(rows)]

1.2 反向索引与切片

Python 支持负数索引，从后往前访问极其方便：

l = [1, 2, 3, 4, 5]

last_element = l[–1] # 5，最后一个元素
last_two = l[–2:] # [4, 5]，最后两个元素
reverse = l[::–1] # [5, 4, 3, 2, 1]，反转列表

# 反向遍历
for i in range(len(l) – 1, –1, –1): # 从后往前
print(l[i])

# 步长为负的 range
for i in range(0, –10, –1):
print(i) # 0, -1, -2, -3, -4, -5, -6, -7, -8, -9

1.3 浅拷贝 vs 深拷贝

import copy

# 浅拷贝（只拷贝一层）
l2 = l1[:]
# 或
l2 = l1.copy()

# ⚠️ 浅拷贝的问题：嵌套列表未被真正复制
a = [1, 2, [3, 4]]
b = a[:]
a[2].append(5)
print(b) # [1, 2, [3, 4, 5]] # b 也被改变了！

# 深拷贝（完全独立）
b = copy.deepcopy(a)

1.4 枚举 enumerate

同时获取索引和值，避免手动维护计数器：

l = ["a", "b", "c"]

# 基础用法
for i, v in enumerate(l):
print(i, v)
# 0 a
# 1 b
# 2 c

# 指定起始索引（常用于算法题中的1-based索引）
for i, v in enumerate(l, 1):
print(i, v)
# 1 a
# 2 b
# 3 c

1.5 双端队列 deque

list 的 pop(0) 操作是 O(n)，而 deque 首尾操作均为 O(1)：

from collections import deque

dq = deque([1, 2, 3])

# 尾部操作（同 list）
dq.append(4) # deque([1, 2, 3, 4])
dq.pop() # 返回 4

# 头部操作（deque 独有，O(1)）
dq.appendleft(0) # deque([0, 1, 2, 3])
dq.popleft() # 返回 0

# 初始化空 deque
dq = deque()

# 常用于 BFS
queue = deque([(start_x, start_y)])
while queue:
x, y = queue.popleft()
# 处理邻居…

1.6 排序 sorted

sorted() 返回新列表，原列表不变；list.sort() 原地排序，返回 None。

# 基础排序
l = [3, 1, 4, 1, 5]
sorted(l) # [1, 1, 3, 4, 5]

# 按元组第一个元素排序
l1 = [(1, 2), (0, 1), (3, 10)]
l2 = sorted(l1, key=lambda x: x[0])
# [(0, 1), (1, 2), (3, 10)]

# 按第二个元素降序
l2 = sorted(l1, key=lambda x: x[1], reverse=True)

# 字符串排序（忽略大小写）
words = ["banana", "APPLE", "Watermelon"]
sorted(words, key=str.lower)
# ['APPLE', 'banana', 'Watermelon']

# 多条件排序：先按长度，再按字母
words.sort(key=lambda x: (len(x), x.lower()))

1.7 自定义比较排序（cmp_to_key）

Python 3 取消了 sorted 的 cmp 参数，需借助 functools：

from functools import cmp_to_key

def compare(a, b):
# 按绝对值排序，绝对值相同按原值排序
if abs(a) < abs(b):
return –1
elif abs(a) > abs(b):
return 1
else:
return a – b

arr = [–3, 1, –1, 2, –2]
sorted(arr, key=cmp_to_key(compare))
# [1, -1, 2, -2, -3] 或 [-1, 1, -2, 2, -3]

二、字符串处理：文本类题目的利器

2.1 字符与 ASCII 转换

# 字符转 ASCII
ord('a') # 97
ord('A') # 65

# ASCII 转字符
chr(97) # 'a'
chr(100) # 'd'

# 快速生成字母表
import string
letters = string.ascii_lowercase # 'abcdefghijklmnopqrstuvwxyz'

2.2 strip 去除字符

# 去除首尾空格
' spacious '.strip() # 'spacious'

# 去除指定字符（从首尾开始匹配，直到不匹配为止）
'www.example.com'.strip('cmowz.') # 'example'
# 注意：不是去除子串，而是去除字符集合中的任意字符

2.3 split 分割

# 基础分割
'1,2,3'.split(',') # ['1', '2', '3']

# 限制分割次数
'1,2,3'.split(',', maxsplit=1) # ['1', '2,3']

# 处理连续分隔符
'1,2,,3,'.split(',') # ['1', '2', '', '3', '']

# 常用技巧：快速解析输入
date = "2019-8-15"
Y, M, D = map(int, date.split('-'))
# Y=2019, M=8, D=15

2.4 zip 拉链操作

将多个列表像拉链一样聚合：

x = [1, 2, 3]
y = [4, 5, 6]
zipped = list(zip(x, y))
# [(1, 4), (2, 5), (3, 6)]

# 同时遍历多个列表
names = ["Alice", "Bob", "Charlie"]
scores = [85, 90, 78]
for name, score in zip(names, scores):
print(f"{name}: {score}")

# 解压（unzip）
pairs = [(1, 'a'), (2, 'b'), (3, 'c')]
nums, chars = zip(*pairs)
# nums = (1, 2, 3), chars = ('a', 'b', 'c')

# 矩阵转置（超级实用）
matrix = [[1, 2, 3], [4, 5, 6]]
transposed = list(zip(*matrix))
# [(1, 4), (2, 5), (3, 6)]

三、集合与字典：O(1) 查找的秘诀

3.1 集合 set

查找复杂度 O(1)，常用于去重和快速判断存在性：

s = set()

# 添加元素（注意是 add，不是 append）
s.add(1)
s.add(2)

# 删除元素
s.remove(1) # 元素不存在会报错 KeyError
s.discard(100) # 元素不存在不会报错，更安全

# 集合运算
a = {1, 2, 3, 4}
b = {3, 4, 5, 6}

a | b # 并集: {1, 2, 3, 4, 5, 6}
a & b # 交集: {3, 4}
a – b # 差集: {1, 2}
a ^ b # 对称差集: {1, 2, 5, 6}

# 判断子集
a.issubset(b) # False
{3, 4}.issubset(a) # True

# 列表去重（保持顺序需配合 dict.fromkeys）
nums = [1, 2, 2, 3, 3, 3]
unique = list(set(nums)) # [1, 2, 3]（顺序不保证）

3.2 字典 dict

相当于其他语言的 HashMap，读取 O(1)：

d = {'a': 1, 'b': 2}

# 安全获取（避免 KeyError）
d.get('c', 0) # 键不存在返回默认值 0

# 获取所有键、值、键值对
d.keys() # dict_keys(['a', 'b'])
d.values() # dict_values([1, 2])
d.items() # dict_items([('a', 1), ('b', 2)])

# setdefault：存在则返回，不存在则设置并返回默认值
# 常用于字典初始化
node = {}
for char in "abc":
node = node.setdefault(char, {})
# 构建嵌套字典

# 使用 get 简化计数
from collections import Counter
# 或手动：
count = {}
for c in "abracadabra":
count[c] = count.get(c, 0) + 1

3.3 defaultdict 自动初始化

避免每次判断 key 是否存在：

from collections import defaultdict

# value 为列表
d = defaultdict(list)
s = [('yellow', 1), ('blue', 2), ('yellow', 3), ('blue', 4)]
for k, v in s:
d[k].append(v)
# d = {'yellow': [1, 3], 'blue': [2, 4]}

# value 为整数（计数）
d = defaultdict(int)
for c in "abracadabra":
d[c] += 1
# d = {'a': 5, 'b': 2, 'r': 2, 'c': 1, 'd': 1}

# value 为集合
d = defaultdict(set)

3.4 OrderedDict 有序字典

记录插入顺序，底层是双向链表 + 哈希表：

from collections import OrderedDict

d = OrderedDict.fromkeys('abcde')
''.join(d.keys()) # 'abcde'

# 将元素移到末尾
d.move_to_end('b')
''.join(d.keys()) # 'acdeb'

# 将元素移到开头
d.move_to_end('b', last=False)
''.join(d.keys()) # 'bacde'

四、堆与优先队列

heapq 是 Python 的优先队列实现，默认小顶堆。

import heapq

# 创建堆（原地调整）
heap = [3, 1, 4, 1, 5, 9, 2]
heapq.heapify(heap) # 调整为小顶堆，O(n)

# 插入元素
heapq.heappush(heap, 0) # 添加 0

# 弹出最小元素
min_val = heapq.heappop(heap) # 返回 0

# 查看堆顶（不弹出）
heap[0]

# 大顶堆技巧：存入负数
max_heap = []
heapq.heappush(max_heap, –3)
heapq.heappush(max_heap, –1)
heapq.heappush(max_heap, –4)
–largest = heapq.heappop(max_heap) # 返回 -4，实际最大值为 4

# 获取前 k 大/小的元素
nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.nlargest(3, nums) # [9, 6, 5]
heapq.nsmallest(3, nums) # [1, 1, 2]

# 合并多个有序列表
list1 = [1, 3, 5]
list2 = [2, 4, 6]
merged = heapq.merge(list1, list2) # 返回迭代器
list(merged) # [1, 2, 3, 4, 5, 6]

堆排序实现：

def heapsort(iterable):
h = []
for value in iterable:
heapq.heappush(h, value)
return [heapq.heappop(h) for _ 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]

五、二分查找：bisect 模块

无需手写二分，直接调用内置库：

import bisect

a = [1, 2, 4, 4, 5, 7]

# 查找插入位置（保持有序）
bisect.bisect(a, 4) # 4，插入到现有 4 的右侧
bisect.bisect_left(a, 4) # 2，插入到现有 4 的左侧
bisect.bisect_right(a, 4) # 4，同 bisect

# 实际插入
bisect.insort(a, 3) # a 变为 [1, 2, 3, 4, 4, 5, 7]
bisect.insort_left(a, 4) # 插入到左侧

# 指定查找范围
bisect.bisect(a, 4, lo=0, hi=4) # 在 [0:4] 范围内查找

六、计数器 Counter

from collections import Counter

# 创建
c = Counter('abracadabra') # 从可迭代对象
c = Counter({'red': 4, 'blue': 2}) # 从字典
c = Counter(cats=4, dogs=8) # 从关键字参数

# 统计出现次数最多的 n 个
c.most_common(3)
# [('a', 5), ('b', 2), ('r', 2)]

# 计数器运算
c1 = Counter(a=3, b=1)
c2 = Counter(a=1, b=2)
c1 + c2 # Counter({'a': 4, 'b': 3})
c1 – c2 # Counter({'a': 2}) # 只保留正数
c1 & c2 # Counter({'a': 1, 'b': 1}) # 取最小
c1 | c2 # Counter({'a': 3, 'b': 2}) # 取最大

七、常用数学技巧

7.1 无穷大与无穷小

# 初始化最值
max_val = float('inf') # 正无穷
min_val = float('-inf') # 负无穷

# 比较
5 < float('inf') # True

# 也可用 sys.maxsize（整数最大）
import sys
max_int = sys.maxsize # 9223372036854775807

7.2 除法与次方

# Python 3 中 / 总是返回浮点数
3 / 2 # 1.5

# // 整除（向负无穷取整）
3 // 2 # 1
–3 // 2 # -2

# 次方
2 ** 10 # 1024
pow(2, 10) # 1024

# 取模
10 % 3 # 1
–10 % 3 # 2（结果始终非负）

7.3 条件表达式（三元运算符）

# Python 风格
res = a if condition else b

# 等价于 C/Java 风格
# res = condition ? a : b;

# 示例：求两数最大值
max_val = a if a > b else b

# 链式条件
grade = "A" if score >= 90 else "B" if score >= 80 else "C"

7.4 any 与 all

# any：任一元素为真则返回 True
any([0, 0, 1, 0]) # True
any([]) # False

# all：所有元素为真则返回 True
all([1, 2, 3]) # True
all([1, 0, 3]) # False
all([]) # True（空序列）

# 实战：判断数独是否有效（LeetCode 36）
def isValidSudoku(board):
row = [[x for x in y if x != '.'] for y in board]
col = [[x for x in y if x != '.'] for y in zip(*board)]
pal = [[board[i+m][j+n] for m in range(3) for n in range(3)
if board[i+m][j+n] != '.']
for i in (0, 3, 6) for j in (0, 3, 6)]
return all(len(set(x)) == len(x) for x in (*row, *col, *pal))

八、函数式编程工具

8.1 map 映射

# 将字符串转为整数列表
nums = list(map(int, "1 2 3 4 5".split()))
# [1, 2, 3, 4, 5]

# 配合 lambda
squares = list(map(lambda x: x**2, [1, 2, 3, 4]))
# [1, 4, 9, 16]

# 多参数 map
sums = list(map(lambda x, y: x + y, [1, 2, 3], [4, 5, 6]))
# [5, 7, 9]

8.2 reduce 累积

from functools import reduce

# 求和
reduce(lambda a, b: a + b, [1, 3, 5, 6, 2]) # 17

# 求积
reduce(lambda a, b: a * b, [1, 2, 3, 4]) # 24

# 找最大值
reduce(lambda a, b: a if a > b else b, [3, 1, 4, 1, 5]) # 5

# 字符串拼接
reduce(lambda a, b: a + b, ["a", "b", "c"]) # "abc"

8.3 filter 过滤

# 过滤偶数
evens = list(filter(lambda x: x % 2 == 0, [1, 2, 3, 4, 5, 6]))
# [2, 4, 6]

# 过滤非空字符串
non_empty = list(filter(None, ["a", "", "b", None, "c"]))
# ['a', 'b', 'c']

九、迭代器工具 itertools

import itertools

# 排列（permutations）
list(itertools.permutations('ABCD', 2))
# [('A','B'), ('A','C'), ('A','D'), ('B','A'), …] 共 12 个

# 组合（combinations）
list(itertools.combinations('ABCD', 2))
# [('A','B'), ('A','C'), ('A','D'), ('B','C'), ('B','D'), ('C','D')]

# 笛卡尔积
list(itertools.product([1, 2], ['a', 'b']))
# [(1, 'a'), (1, 'b'), (2, 'a'), (2, 'b')]

# 分组 groupby（需先排序）
[k for k, g in itertools.groupby('AAAABBBCCDAABBB')]
# ['A', 'B', 'C', 'D', 'A', 'B']

[list(g) for k, g in itertools.groupby('AAAABBBCCD')]
# [['A','A','A','A'], ['B','B','B'], ['C','C'], ['D']]

# 累积 accumulate
list(itertools.accumulate([1, 2, 3, 4, 5])) # [1, 3, 6, 10, 15]

# 无限迭代器
# itertools.count(10) # 10, 11, 12, …
# itertools.cycle('ABC') # A, B, C, A, B, C, …
# itertools.repeat(10, 3) # 10, 10, 10

十、缓存优化：lru_cache

functools.lru_cache 自动缓存函数结果，避免重复计算，是记忆化搜索的神器。

from functools import lru_cache

# 基础用法
@lru_cache(maxsize=None) # None 表示无限制
def fibonacci(n):
if n < 2:
return n
return fibonacci(n – 1) + fibonacci(n – 2)

# 带参数的缓存
@lru_cache(None)
def dp(i, j):
if i == 0 or j == 0:
return 0
return max(dp(i–1, j), dp(i, j–1)) + grid[i][j]

# 实战：石子游戏 II（LeetCode 1563）
class Solution:
def stoneGameII(self, piles: List[int]) –> int:
n = len(piles)
# 后缀和
for i in range(n – 2, –1, –1):
piles[i] += piles[i + 1]

@lru_cache(None)
def dp(i, m):
if i + 2 * m >= n:
return piles[i]
return piles[i] – min(dp(i + x, max(m, x))
for x in range(1, 2 * m + 1))

return dp(0, 1)

注意事项：

• 被装饰的函数参数必须可哈希（不可使用 list、dict 等）
• 如需缓存类方法，注意 self 也要可哈希

十一、综合实战技巧

11.1 矩阵操作

# 矩阵转置
matrix = [[1, 2, 3], [4, 5, 6]]
transposed = list(map(list, zip(*matrix)))
# [[1, 4], [2, 5], [3, 6]]

# 矩阵顺时针旋转 90 度
rotated = [list(row) for row in zip(*matrix[::–1])]

# 矩阵逆时针旋转 90 度
rotated = [list(row) for row in zip(*matrix)][::–1]

# 获取矩阵维度
rows, cols = len(matrix), len(matrix[0])

# 遍历四个方向
directions = [(–1, 0), (1, 0), (0, –1), (0, 1)] # 上、下、左、右
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < rows and 0 <= ny < cols:
# 处理邻居…

11.2 链表操作

# 创建链表节点
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next

# 从列表创建链表
def create_linked_list(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next

# 链表转列表
def linked_list_to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result

# 快慢指针找中点
def find_middle(head):
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow # 当 fast 到达末尾，slow 在中点

11.3 并查集模板

class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n # 连通分量数

def find(self, x):
# 路径压缩
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]

def union(self, x, y):
px, py = self.find(x), self.find(y)
if px == py:
return False
# 按秩合并
if self.rank[px] < self.rank[py]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
self.count -= 1
return True

def connected(self, x, y):
return self.find(x) == self.find(y)

11.4 快速读入（竞赛优化）

import sys

# 快速读入整数
input = sys.stdin.readline

# 读取一行多个整数
n, m = map(int, input().split())

# 读取多行
data = [list(map(int, input().split())) for _ in range(n)]

# 输出优化（避免多次 flush）
print('\\n'.join(map(str, results)))

11.5 常用代码片段速查

# 1. 创建二维访问标记数组
visited = [[False for _ in range(cols)] for _ in range(rows)]

# 2. 字典按值排序
sorted(d.items(), key=lambda x: x[1], reverse=True)

# 3. 列表去重并保持顺序
list(dict.fromkeys(nums))

# 4. 字符串反转
s[::–1]

# 5. 判断回文
s == s[::–1]

# 6. 求最大公约数
import math
math.gcd(a, b)

# 7. 求最小公倍数
a * b // math.gcd(a, b)

# 8. 二进制位操作
n & 1 # 判断奇偶
n >> 1 # 除以 2
n << 1 # 乘以 2
n & (n – 1) # 清除最低位的 1
n & –n # 获取最低位的 1

# 9. 枚举子集
subset = mask
while subset:
# 处理 subset
subset = (subset – 1) & mask

# 10. 前缀和
prefix = [0]
for num in nums:
prefix.append(prefix[–1] + num)
# sum[i:j] = prefix[j] – prefix[i]

总结

Python 凭借简洁的语法成为算法刷题的首选语言。掌握以上技巧，可以显著提升编码效率和代码优雅度：

推荐资源：

• Shortest LeetCode Python Solutions — 各种 Python trick 解题
• LeetCode 讨论区 StefanPochmann、lee215 等大神题解

纸上得来终觉浅，绝知此事要躬行。 建议每学一个技巧，立刻找 2-3 道相关题目实战巩固！