Python 算法竞赛/刷题全指南
前言
如果你习惯了 C++或者 Java 语法，初次尝试用 Python 刷算法题，那建议看看这篇博客，这不是 Python 基础语法教程，而是一份针对算法竞赛实战指南。这里汇集了最常用的库、那些让你事半功倍的语法糖，以及 C++/Java 选手容易踩的坑。
一：输入输出与环境配置 (I/O & Setup)
在 LeetCode 这种核心代码模式下不需要关心 I/O，但在 ACM 模式（如各大厂笔试、牛客、Codeforces）中，Python 的 I/O 速度是瓶颈。
1. 极速输入输出
当数据量达到 级别时，input() 和 print() 可能会导致 TLE (Time Limit Exceeded）
import sys # 替代 input() input = sys.stdin.readline # 使用方式 n = int(input()) arr = list(map(int, input().split())) # 替代 print()，注意 write 需要传入字符串且手动加换行 sys.stdout.write(str(ans) + '\n') 2. 解除递归深度限制
Python 默认递归深度通常是 1000，做 DFS 或深搜时容易报错 RecursionError。
import sys sys.setrecursionlimit(10**6) # 设置为 100万，足够应对大多数题目 二：核心数据结构与黑魔法 (Data Structures)
1. 数组 (List)
Python 的 List 是动态数组，对应 C++ vector / Java ArrayList。
初始化二维数组 (避坑)：
# ❌ 错误：所有行都指向同一个对象 grid = [[0] * m] * n # ✅ 正确 grid = [[0] * m for _ in range(n)] 切片 (Slicing)：
arr = [0, 1, 2, 3, 4, 5] print(arr[::-1]) # 翻转数组，O(N) print(arr[1:4]) # [1, 2, 3] # 技巧：复制数组要用 b = a[:]，不能直接 b = a（那是引用） 2. 双端队列 (Deque)
Python 的 list 模拟栈（Stack）很快 append/pop 是 O(1)，但模拟队列（Queue）在头部插入/删除是 O(N)。务必使用 collections.deque
from collections import deque q = deque([1, 2, 3]) q.append(4) # 队尾进 q.popleft() # 队头出，O(1) # 也可以作为单调队列使用 3. 哈希表 (Dict & Set)
Counter (计数器)：
from collections import Counter s = "abacaba" c = Counter(s) # Counter({'a': 4, 'b': 2, 'c': 1}) print(c.most_common(1)) # 返回出现次数最多的元素 Defaultdict (神器)：C++/Java 中访问不存在的 Key 会报错或返回 null，Python 的 defaultdict 可以自动初始化
from collections import defaultdict # 计数器：默认值为 0 cnt = defaultdict(int) cnt[x] += 1 # 邻接表：默认值为列表 graph = defaultdict(list) graph[u].append(v) 4. 堆 (Heap)
Python 只有小顶堆。如果需要大顶堆，存入负数。
import heapq nums = [3, 1, 4, 1, 5] heapq.heapify(nums) # O(N) 建堆 min_val = heapq.heappop(nums) # 弹出最小值 1 heapq.heappush(nums, 2) # 压入 2 三：必备标准库 (The Standard Library)
有些题如果是 C++ 写需要手撸几十行，Python 调库即可。
1. 二分查找 (bisect)
不需要手写 left <= right 了。
import bisect arr = [1, 3, 4, 4, 6] # 查找第一个 >= x 的位置 (lower_bound) idx1 = bisect.bisect_left(arr, 4) # 返回 2 # 查找第一个 > x 的位置 (upper_bound) idx2 = bisect.bisect_right(arr, 4) # 返回 4 2. 排列组合 (itertools)
import itertools nums = [1, 2, 3] # 全排列 perm = list(itertools.permutations(nums)) # 组合 (C(n, k)) comb = list(itertools.combinations(nums, 2)) 3. 记忆化搜索 (functools)
这是 DP（动态规划）选手的最爱。不用手动开 memo 数组，加个装饰器即可。
from functools import lru_cache @lru_cache(None) # None 表示无大小限制 def dfs(i, j): if i < 0 or j < 0: return 0 # ... 你的逻辑 return res 4. 数学工具 (math)
import math math.gcd(a, b) # 最大公约数 math.lcm(a, b) # 最小公倍数 (Python 3.9+) math.comb(n, k) # 组合数 C(n, k) x = float('inf') # 无穷大 四：Pythonic 技巧与语法糖
1. 自定义排序 (Lambda)
对复杂对象排序，不需要写 Comparator 类。
points = [[1, 2], [3, 1], [2, 4]] # 先按 x 升序，若 x 相同按 y 降序 points.sort(key=lambda x: (x[0], -x[1])) 2. 同时遍历 (Zip & Enumerate)
# 想要 index 和 value for i, val in enumerate(nums): pass # 同时遍历两个数组 for a, b in zip(nums1, nums2): pass 3. 解包 (Unpacking)
# 交换变量 a, b = b, a # 拆分数组 head, *mid, tail = [1, 2, 3, 4, 5] # head=1, mid=[2,3,4], tail=5 4. 任意与所有 (Any & All)
检查数组是否满足条件，比写循环优雅。
if any(x < 0 for x in nums): print("存在负数") if all(x > 0 for x in nums): print("全是正数") 五：C++/Java 转 Python 的易错点
1. 整数没有溢出！
Python 的 int 是高精度整数。
- 优点：不用担心
long long越界，大数运算直接算。 - 缺点：无法利用 32 位整数溢出来做某些位运算 trick。
2. 变量全是引用 (Reference)
这是最大的坑。在函数传参时：
- 不可变对象（int, str, tuple）：表现像值传递。
- 可变对象（list, dict, set）：表现像引用传递。
def modify(arr): arr.append(1) # 会改变外部变量 a = [0] b = a # b 是 a 的引用 c = a[:] # c 是 a 的浅拷贝 3. 字符不可变
Python 的 str 是不可变的。
- 不要在循环里做
s += "c"，这是 $O(N^2)$ 的复杂度。 - 做法：先用 list 收集字符，最后
''.join(list)。
4. 没有 do-while 和 i++
- 用
while True: ... if break代替do-while。 - 用
i += 1，Python 不支持++运算符。
结语
Python 在算法题中的优势在于将你的思维快速转化为代码。虽然它的原生运行速度不如 C++，但在大多数算法题的时间限制（Time Limit）设置上，Python 会有更宽裕的时间（通常是 C++ 的 2-5 倍）。
最后一句口诀：
遇到数组用 List，频繁增删用 Deque，快速查找用 Set，计数统计用 Counter，排序规则用 Lambda，人生苦短用 Python。
