Python 算法竞赛与刷题实战指南

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。