Python 算法模板库¶
说明: 竞赛级算法模板，包含详细注释、时间/空间复杂度分析和使用示例
适用场景: LeetCode、算法竞赛、面试准备
目录¶
1. 复杂度分析速查表¶
时间复杂度（从快到慢）¶
| 复杂度 | 名称 | 典型算法 |
|---|---|---|
| O(1) | 常数时间 | 哈希表操作、数组访问 |
| O(log n) | 对数时间 | 二分搜索、平衡树操作 |
| O(√n) | 平方根时间 | 质数判断 |
| O(n) | 线性时间 | 遍历数组、链表 |
| O(n log n) | 线性对数 | 排序、堆操作 |
| O(n²) | 平方时间 | 双重循环、简单排序 |
| O(n³) | 立方时间 | 三重循环、Floyd算法 |
| O(2ⁿ) | 指数时间 | 子集枚举、回溯 |
| O(n!) | 阶乘时间 | 全排列 |
空间复杂度¶
| 复杂度 | 典型场景 |
|---|---|
| O(1) | 常数空间，原地操作 |
| O(n) | 一维数组、递归栈 |
| O(n²) | 二维数组、邻接矩阵 |
2. 排序算法¶
快速排序 - 简洁版¶
适用场景: 竞赛、快速实现
时间复杂度: O(n log n) 平均，O(n²) 最坏
空间复杂度: O(log n)
Python
def quick_sort(arr: list[int]) -> list[int]:
"""快速排序 - 简洁版（适合竞赛）"""
if len(arr) <= 1:
return arr
pivot = arr[len(arr) // 2]
left = [x for x in arr if x < pivot]
middle = [x for x in arr if x == pivot]
right = [x for x in arr if x > pivot]
return quick_sort(left) + middle + quick_sort(right)
使用示例:
快速排序 - 原地版¶
适用场景: 面试、空间敏感
Python
def quick_sort_inplace(arr: list[int], low: int = 0, high: int = None) -> None:
"""快速排序 - 原地版（面试推荐）"""
if high is None:
high = len(arr) - 1
if low < high:
pivot_idx = _partition(arr, low, high)
quick_sort_inplace(arr, low, pivot_idx - 1)
quick_sort_inplace(arr, pivot_idx + 1, high)
def _partition(arr: list[int], low: int, high: int) -> int:
"""快速排序分区函数"""
pivot = arr[high] # 选择最右元素作为基准
i = low - 1 # i指向小于等于pivot区域的右边界
for j in range(low, high):
if arr[j] <= pivot: # 当前元素小于等于基准值
i += 1 # 扩展小于等于区域
arr[i], arr[j] = arr[j], arr[i] # 交换到小于等于区域
# 将基准元素放到正确位置（小于等于区域的右侧）
arr[i + 1], arr[high] = arr[high], arr[i + 1]
return i + 1
归并排序¶
特点: 稳定排序
时间复杂度: O(n log n)
空间复杂度: O(n)
Python
def merge_sort(arr: list[int]) -> list[int]:
"""归并排序 - 稳定排序"""
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort(arr[:mid])
right = merge_sort(arr[mid:])
return _merge(left, right)
def _merge(left: list[int], right: list[int]) -> list[int]:
"""合并两个有序数组"""
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
堆排序¶
特点: 原地排序
时间复杂度: O(n log n)
空间复杂度: O(1)
Python
def heap_sort(arr: list[int]) -> list[int]:
"""堆排序"""
n = len(arr)
# 建立大顶堆
for i in range(n // 2 - 1, -1, -1):
_heapify(arr, n, i)
# 逐个提取堆顶元素
for i in range(n - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
_heapify(arr, i, 0)
return arr
def _heapify(arr: list[int], n: int, i: int) -> None:
"""堆化函数：维护以i为根的子树的大顶堆性质"""
largest = i
left = 2 * i + 1 # 左子节点
right = 2 * i + 2 # 右子节点
# 找出当前节点、左子、右子中的最大值
if left < n and arr[left] > arr[largest]:
largest = left
if right < n and arr[right] > arr[largest]:
largest = right
if largest != i:
arr[i], arr[largest] = arr[largest], arr[i] # 交换到最大值位置
_heapify(arr, n, largest) # 递归修复被破坏的子树
3. 搜索算法¶
二分搜索 - 标准版¶
时间复杂度: O(log n)
空间复杂度: O(1)
返回值: target的索引，不存在返回-1
Python
def binary_search(arr: list[int], target: int) -> int:
"""二分搜索 - 标准版"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
elif arr[mid] < target:
left = mid + 1
else:
right = mid - 1
return -1
使用示例:
Lower Bound¶
功能: 查找第一个 >= target 的元素索引
时间复杂度: O(log n)
Python
def lower_bound(arr: list[int], target: int) -> int:
"""查找第一个 >= target 的元素索引"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] < target:
left = mid + 1
else:
right = mid
return left
Upper Bound¶
功能: 查找第一个 > target 的元素索引
时间复杂度: O(log n)
Python
def upper_bound(arr: list[int], target: int) -> int:
"""查找第一个 > target 的元素索引"""
left, right = 0, len(arr)
while left < right:
mid = left + (right - left) // 2
if arr[mid] <= target:
left = mid + 1
else:
right = mid
return left
旋转排序数组二分搜索¶
时间复杂度: O(log n)
Python
def binary_search_rotated(arr: list[int], target: int) -> int:
"""旋转排序数组二分搜索"""
left, right = 0, len(arr) - 1
while left <= right:
mid = left + (right - left) // 2
if arr[mid] == target:
return mid
# 判断哪半边有序
if arr[left] <= arr[mid]: # 左半边有序
if arr[left] <= target < arr[mid]:
right = mid - 1
else:
left = mid + 1
else: # 右半边有序
if arr[mid] < target <= arr[right]:
left = mid + 1
else:
right = mid - 1
return -1
4. 图论算法¶
BFS - 广度优先搜索¶
时间复杂度: O(V + E)
空间复杂度: O(V)
Python
from collections import deque
def bfs(graph: dict[int, list[int]], start: int) -> list[int]:
"""广度优先搜索（BFS）"""
visited = set([start])
queue = deque([start])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
return result
使用示例:
Python
graph = {
0: [1, 2],
1: [0, 3, 4],
2: [0, 4],
3: [1],
4: [1, 2]
}
result = bfs(graph, 0)
print(result) # [0, 1, 2, 3, 4]
DFS - 深度优先搜索（递归版）¶
时间复杂度: O(V + E)
空间复杂度: O(V)
Python
def dfs_recursive(graph: dict[int, list[int]], start: int) -> list[int]:
"""深度优先搜索（DFS）- 递归版"""
visited = set()
result = []
def _dfs(node):
visited.add(node)
result.append(node)
for neighbor in graph.get(node, []):
if neighbor not in visited:
_dfs(neighbor)
_dfs(start)
return result
DFS - 深度优先搜索（迭代版）¶
Python
def dfs_iterative(graph: dict[int, list[int]], start: int) -> list[int]:
"""深度优先搜索（DFS）- 迭代版"""
visited = set()
stack = [start]
result = []
while stack:
node = stack.pop()
if node not in visited:
visited.add(node)
result.append(node)
# 反向添加邻居以保持遍历顺序
for neighbor in reversed(graph.get(node, [])):
if neighbor not in visited:
stack.append(neighbor)
return result
Dijkstra最短路径算法¶
时间复杂度: O((V + E) log V)
空间复杂度: O(V)
Python
import heapq
def dijkstra(graph: dict[int, list[tuple[int, int]]], start: int) -> dict[int, int]:
"""Dijkstra最短路径算法
Args:
graph: {node: [(neighbor, weight), ...]}
Returns:
从start到各节点的最短距离
"""
# 初始化所有节点距离为无穷大
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)] # 最小堆：(距离, 节点)
while pq:
d, node = heapq.heappop(pq) # 取出当前最短距离的节点
if d > dist[node]: # 已找到更短路径，跳过过期条目
continue
# 松弛操作：尝试通过当前节点更新邻居的最短距离
for neighbor, weight in graph.get(node, []):
new_dist = dist[node] + weight
if new_dist < dist[neighbor]:
dist[neighbor] = new_dist
heapq.heappush(pq, (new_dist, neighbor))
return dist
5. 动态规划¶
爬楼梯¶
问题: 每次可以爬1或2阶，n阶楼梯有多少种爬法
时间复杂度: O(n)
空间复杂度: O(1)
Python
def climb_stairs(n: int) -> int:
"""爬楼梯问题"""
if n <= 2:
return n
prev, curr = 1, 2
for _ in range(3, n + 1):
prev, curr = curr, prev + curr
return curr
打家劫舍¶
问题: 不能偷相邻房子，求最大金额
时间复杂度: O(n)
空间复杂度: O(1)
Python
def rob_house(nums: list[int]) -> int:
"""打家劫舍（不能偷相邻房子）"""
if not nums:
return 0
if len(nums) == 1:
return nums[0]
prev2, prev1 = 0, nums[0]
for i in range(1, len(nums)):
curr = max(prev2 + nums[i], prev1)
prev2, prev1 = prev1, curr
return prev1
0-1背包问题¶
时间复杂度: O(n × capacity)
空间复杂度: O(capacity)
Python
def knapsack_01(weights: list[int], values: list[int], capacity: int) -> int:
"""0-1背包问题"""
n = len(weights)
dp = [0] * (capacity + 1) # dp[w]表示容量为w时的最大价值
for i in range(n):
# 逆序遍历保证每个物品只使用一次（0-1背包关键）
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) # 不选 vs 选第i个物品
return dp[capacity]
完全背包问题¶
时间复杂度: O(n × capacity)
空间复杂度: O(capacity)
Python
def knapsack_unbounded(weights: list[int], values: list[int], capacity: int) -> int:
"""完全背包问题（每种物品无限个）"""
n = len(weights)
dp = [0] * (capacity + 1) # dp[w]表示容量为w时的最大价值
for i in range(n):
# 正序遍历允许同一物品被重复选取（与0-1背包的关键区别）
for w in range(weights[i], capacity + 1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
最长公共子序列（LCS）¶
时间复杂度: O(m × n)
空间复杂度: O(m × n)
Python
def longest_common_subsequence(text1: str, text2: str) -> int:
"""最长公共子序列（LCS）"""
m, n = len(text1), len(text2)
# dp[i][j]表示text1前i个字符与text2前j个字符的LCS长度
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i - 1] == text2[j - 1]:
dp[i][j] = dp[i - 1][j - 1] + 1 # 字符相同，LCS长度+1
else:
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) # 取跳过任一字符的较大值
return dp[m][n]
最长递增子序列（LIS）- 二分优化版¶
时间复杂度: O(n log n)
空间复杂度: O(n)
Python
import bisect
def longest_increasing_subsequence(nums: list[int]) -> int:
"""最长递增子序列（LIS）- 二分优化版"""
if not nums:
return 0
# tails[i]表示长度为i+1的递增子序列的最小末尾元素
tails = []
for num in nums:
# 在tails中二分查找第一个>=num的位置
idx = bisect.bisect_left(tails, num)
if idx == len(tails):
tails.append(num) # num比所有末尾都大，扩展最长子序列
else:
tails[idx] = num # 用更小的值替换，为后续元素留更多空间
return len(tails)
最大子数组和（Kadane算法）¶
时间复杂度: O(n)
空间复杂度: O(1)
Python
def max_subarray_sum(nums: list[int]) -> int:
"""最大子数组和（Kadane算法）"""
if not nums:
return 0
current_sum = max_sum = nums[0]
for num in nums[1:]:
current_sum = max(num, current_sum + num)
max_sum = max(max_sum, current_sum)
return max_sum
6. 数据结构¶
链表节点¶
Python
class ListNode:
"""链表节点"""
def __init__(self, val: int = 0, next: 'ListNode' = None):
self.val = val
self.next = next
二叉树节点¶
Python
class TreeNode:
"""二叉树节点"""
def __init__(self, val: int = 0, left: 'TreeNode' = None, right: 'TreeNode' = None):
self.val = val
self.left = left
self.right = right
并查集（Union-Find）¶
时间复杂度: 均摊O(α(n))，近似O(1)
空间复杂度: O(n)
Python
class UnionFind:
"""并查集（Union-Find）"""
def __init__(self, n: int):
self.parent = list(range(n))
self.rank = [0] * n
self.count = n
def find(self, x: int) -> int:
"""带路径压缩的查找"""
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def union(self, x: int, y: int) -> bool:
"""按秩合并"""
root_x, root_y = self.find(x), self.find(y)
if root_x == root_y:
return False
if self.rank[root_x] < self.rank[root_y]:
root_x, root_y = root_y, root_x
self.parent[root_y] = root_x
if self.rank[root_x] == self.rank[root_y]:
self.rank[root_x] += 1
self.count -= 1
return True
def connected(self, x: int, y: int) -> bool:
return self.find(x) == self.find(y)
使用示例:
Python
uf = UnionFind(5)
uf.union(0, 1)
uf.union(1, 2)
print(uf.connected(0, 2)) # True
print(uf.count) # 3
Trie树（前缀树）¶
时间复杂度: 插入/搜索/前缀匹配都是O(m)，m为单词长度
空间复杂度: O(N × m)，N为单词数
Python
class TrieNode:
"""Trie树节点"""
def __init__(self):
self.children = {}
self.is_end = False
self.count = 0
class Trie:
"""Trie树（前缀树）"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
node = self.root
for char in word:
if char not in node.children:
node.children[char] = TrieNode()
node = node.children[char]
node.count += 1
node.is_end = True
def search(self, word: str) -> bool:
node = self.root
for char in word:
if char not in node.children:
return False
node = node.children[char]
return node.is_end
def starts_with(self, prefix: str) -> bool:
node = self.root
for char in prefix:
if char not in node.children:
return False
node = node.children[char]
return True
线段树¶
时间复杂度: 查询/修改都是O(log n)
空间复杂度: O(4n)
Python
class SegmentTree:
"""线段树（区间查询/修改）"""
def __init__(self, arr: list[int]):
self.n = len(arr)
self.tree = [0] * (4 * self.n) # 线段树数组，4倍空间保证足够
self.lazy = [0] * (4 * self.n) # 懒标记数组，用于区间更新的延迟传播
self._build(arr, 1, 0, self.n - 1)
def _build(self, arr: list[int], node: int, start: int, end: int) -> None:
"""递归建树"""
if start == end: # 叶子节点，直接赋值
self.tree[node] = arr[start]
return
mid = (start + end) // 2
self._build(arr, 2 * node, start, mid) # 构建左子树
self._build(arr, 2 * node + 1, mid + 1, end) # 构建右子树
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1] # 合并子节点
def query(self, left: int, right: int) -> int:
"""查询区间[left, right]的和"""
return self._query(1, 0, self.n - 1, left, right)
def _query(self, node: int, start: int, end: int, left: int, right: int) -> int:
if left > end or right < start: # 查询区间与当前区间无交集
return 0
if left <= start and end <= right: # 当前区间完全被查询区间包含
return self.tree[node]
self._push_down(node, start, end) # 下推懒标记
mid = (start + end) // 2
return self._query(2 * node, start, mid, left, right) + \
self._query(2 * node + 1, mid + 1, end, left, right)
def update(self, idx: int, val: int) -> None:
"""单点修改"""
self._update_point(1, 0, self.n - 1, idx, val)
def _update_point(self, node: int, start: int, end: int, idx: int, val: int) -> None:
if start == end: # 到达叶子节点
self.tree[node] = val
return
self._push_down(node, start, end)
mid = (start + end) // 2
if idx <= mid:
self._update_point(2 * node, start, mid, idx, val) # 目标在左子树
else:
self._update_point(2 * node + 1, mid + 1, end, idx, val) # 目标在右子树
self.tree[node] = self.tree[2 * node] + self.tree[2 * node + 1] # 回溯更新
def _push_down(self, node: int, start: int, end: int) -> None:
"""下推懒标记：将父节点的延迟更新传播到子节点"""
if self.lazy[node] != 0:
mid = (start + end) // 2
# 更新左子节点：值增加 = 懒标记值 × 左子区间长度
self.tree[2 * node] += self.lazy[node] * (mid - start + 1)
self.lazy[2 * node] += self.lazy[node]
# 更新右子节点：值增加 = 懒标记值 × 右子区间长度
self.tree[2 * node + 1] += self.lazy[node] * (end - mid)
self.lazy[2 * node + 1] += self.lazy[node]
self.lazy[node] = 0 # 清除当前节点的懒标记
树状数组（Fenwick Tree / BIT）¶
时间复杂度: 查询/修改都是O(log n)
空间复杂度: O(n)
Python
class FenwickTree:
"""树状数组（Fenwick Tree / BIT）"""
def __init__(self, size: int):
self.n = size
self.tree = [0] * (self.n + 1) # 下标从1开始
def _lowbit(self, x: int) -> int:
"""获取x的最低位1对应的值，决定当前节点管辖区间长度"""
return x & (-x)
def update(self, idx: int, val: int) -> None:
"""单点更新：将idx位置的值增加val"""
idx += 1 # 转为1-indexed
while idx <= self.n:
self.tree[idx] += val
idx += self._lowbit(idx) # 向上更新所有包含该位置的节点
def query(self, idx: int) -> int:
"""查询前缀和[0, idx]"""
idx += 1 # 转为1-indexed
total = 0
while idx > 0:
total += self.tree[idx]
idx -= self._lowbit(idx) # 向前累加所有相关区间
return total
def range_query(self, left: int, right: int) -> int:
"""查询区间和[left, right]，利用前缀和相减"""
if left == 0:
return self.query(right)
return self.query(right) - self.query(left - 1)
LRU缓存¶
时间复杂度: get/put都是O(1)
空间复杂度: O(capacity)
Python
from collections import OrderedDict
class LRUCache:
"""LRU缓存"""
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.capacity = capacity
def get(self, key: int) -> int:
if key not in self.cache:
return -1
self.cache.move_to_end(key)
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key)
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False)
7. 回溯算法¶
全排列¶
时间复杂度: O(n! × n)
空间复杂度: O(n)
Python
def permutations(nums: list[int]) -> list[list[int]]:
"""全排列"""
result = []
n = len(nums)
used = [False] * n
def backtrack(current: list[int]):
if len(current) == n:
result.append(current[:])
return
for i in range(n):
if not used[i]:
used[i] = True
current.append(nums[i])
backtrack(current)
current.pop()
used[i] = False
backtrack([])
return result
组合¶
时间复杂度: O(C(n,k) × k)
空间复杂度: O(k)
Python
def combinations(n: int, k: int) -> list[list[int]]:
"""组合"""
result = []
def backtrack(start: int, current: list[int]):
if len(current) == k:
result.append(current[:])
return
# 剪枝
for i in range(start, n - (k - len(current)) + 2):
current.append(i)
backtrack(i + 1, current)
current.pop()
backtrack(1, [])
return result
子集¶
时间复杂度: O(2ⁿ × n)
空间复杂度: O(n)
Python
def subsets(nums: list[int]) -> list[list[int]]:
"""子集"""
result = []
def backtrack(start: int, current: list[int]):
result.append(current[:]) # 切片操作：[start:end:step]提取子序列
for i in range(start, len(nums)):
current.append(nums[i])
backtrack(i + 1, current)
current.pop()
backtrack(0, [])
return result
括号生成¶
时间复杂度: O(4ⁿ / √n)
空间复杂度: O(n)
Python
def generate_parentheses(n: int) -> list[str]:
"""括号生成"""
result = []
def backtrack(current: str, left: int, right: int):
if len(current) == 2 * n:
result.append(current)
return
if left < n:
backtrack(current + '(', left + 1, right)
if right < left:
backtrack(current + ')', left, right + 1)
backtrack('', 0, 0)
return result
8. 字符串算法¶
KMP字符串匹配¶
时间复杂度: O(m + n)
空间复杂度: O(m)
Python
def kmp_search(text: str, pattern: str) -> int:
"""KMP字符串匹配"""
def build_next(p: str) -> list[int]:
"""构建部分匹配表：next[i]表示p[0:i+1]的最长相等前后缀长度"""
m = len(p)
next_arr = [0] * m
j = 0 # 前缀指针
for i in range(1, m):
# 失配时回退：利用已知的前后缀信息跳过不必要的比较
while j > 0 and p[i] != p[j]:
j = next_arr[j - 1]
if p[i] == p[j]: # 匹配成功，前缀长度+1
j += 1
next_arr[i] = j
return next_arr
if not pattern:
return 0
next_arr = build_next(pattern)
j = 0 # 模式串指针
for i in range(len(text)):
# 失配时利用next数组回退，避免重新匹配已确认的前缀
while j > 0 and text[i] != pattern[j]:
j = next_arr[j - 1]
if text[i] == pattern[j]:
j += 1
if j == len(pattern): # 完全匹配
return i - len(pattern) + 1
return -1
Manacher算法 - 最长回文子串¶
时间复杂度: O(n)
空间复杂度: O(n)
Python
def manacher(s: str) -> str:
"""Manacher算法 - 最长回文子串"""
# 预处理：插入分隔符统一处理奇偶长度回文，如 "abc" → "^#a#b#c#$"
t = '#'.join('^{}$'.format(s))
n = len(t)
p = [0] * n # p[i]表示以t[i]为中心的最长回文半径
center = right = 0 # 当前已知的最右回文边界及其中心
for i in range(1, n - 1):
if i < right:
# 利用已知回文的对称性，镜像位置的回文半径可以直接复用
mirror = 2 * center - i
p[i] = min(right - i, p[mirror])
# 中心扩展：尝试向两侧扩展回文
while t[i + p[i] + 1] == t[i - p[i] - 1]:
p[i] += 1
# 如果扩展后超出已知最右边界，更新center和right
if i + p[i] > right:
center, right = i, i + p[i]
# 找到最长回文的中心和长度，映射回原始字符串
max_len, center_idx = max((length, i) for i, length in enumerate(p))
start = (center_idx - max_len) // 2
return s[start:start + max_len]
9. 数学算法¶
快速幂¶
时间复杂度: O(log exp)
空间复杂度: O(1)
Python
def fast_pow(base: int, exp: int, mod: int) -> int:
"""快速幂：利用二进制分解将O(n)降低到O(log n)"""
result = 1
base %= mod
while exp > 0:
if exp & 1: # 当前二进制位为1，乘入结果
result = result * base % mod
base = base * base % mod # 底数自乘（平方）
exp >>= 1 # 右移处理下一位
return result
GCD和LCM¶
Python
def gcd(a: int, b: int) -> int:
"""最大公约数"""
return a if b == 0 else gcd(b, a % b)
def lcm(a: int, b: int) -> int:
"""最小公倍数"""
return a // gcd(a, b) * b
埃氏筛¶
时间复杂度: O(n log log n)
空间复杂度: O(n)
Python
def sieve(n: int) -> list[bool]:
"""埃氏筛"""
is_prime = [True] * (n + 1)
is_prime[0] = is_prime[1] = False
for i in range(2, int(n**0.5) + 1):
if is_prime[i]:
for j in range(i * i, n + 1, i):
is_prime[j] = False
return is_prime
线性筛（欧拉筛）¶
时间复杂度: O(n)
空间复杂度: O(n)
Python
def linear_sieve(n: int) -> list[int]:
"""线性筛（欧拉筛）：每个合数只被其最小质因子筛掉一次"""
is_prime = [True] * (n + 1)
primes = []
is_prime[0] = is_prime[1] = False
for i in range(2, n + 1):
if is_prime[i]:
primes.append(i)
for p in primes:
if i * p > n: # 超出范围
break
is_prime[i * p] = False
if i % p == 0: # 关键：i已含因子p，更大的质数应由其他数来筛
break
return primes
组合数计算（预处理）¶
时间复杂度: 预处理O(n)，查询O(1)
空间复杂度: O(n)
Python
class Combination:
"""组合数计算（预处理阶乘和逆元，支持O(1)查询）"""
def __init__(self, n: int, mod: int = 10**9 + 7):
self.mod = mod
self.fact = [1] * (n + 1) # fact[i] = i! % mod
self.inv_fact = [1] * (n + 1) # inv_fact[i] = (i!)^(-1) % mod
# 预处理阶乘
for i in range(1, n + 1):
self.fact[i] = self.fact[i - 1] * i % mod
# 利用费马小定理求逆元：a^(-1) ≡ a^(p-2) (mod p)
self.inv_fact[n] = fast_pow(self.fact[n], mod - 2, mod)
# 逆向递推所有逆元阶乘
for i in range(n - 1, -1, -1):
self.inv_fact[i] = self.inv_fact[i + 1] * (i + 1) % mod
def C(self, n: int, k: int) -> int:
"""组合数C(n, k) = n! / (k! × (n-k)!)"""
if k < 0 or k > n:
return 0
return self.fact[n] * self.inv_fact[k] % self.mod * self.inv_fact[n - k] % self.mod
def P(self, n: int, k: int) -> int:
"""排列数P(n, k) = n! / (n-k)!"""
if k < 0 or k > n:
return 0
return self.fact[n] * self.inv_fact[n - k] % self.mod
10. 大厂高频面试题¶
两数之和¶
时间复杂度: O(n)
空间复杂度: O(n)
Python
def two_sum(nums: list[int], target: int) -> list[int]:
"""两数之和"""
num_to_idx = {}
for i, num in enumerate(nums):
complement = target - num
if complement in num_to_idx:
return [num_to_idx[complement], i]
num_to_idx[num] = i
return []
接雨水¶
时间复杂度: O(n)
空间复杂度: O(1)
Python
def trap_rain_water(height: list[int]) -> int:
"""接雨水 - 双指针法"""
if not height:
return 0
left, right = 0, len(height) - 1
left_max, right_max = height[left], height[right]
water = 0
# 从两端向中间收缩，较矮的一侧决定水位
while left < right:
if left_max < right_max:
left += 1
left_max = max(left_max, height[left])
water += left_max - height[left] # 当前柱子能接的水 = 左侧最高 - 当前高度
else:
right -= 1
right_max = max(right_max, height[right])
water += right_max - height[right] # 当前柱子能接的水 = 右侧最高 - 当前高度
return water
滑动窗口最大值¶
时间复杂度: O(n)
空间复杂度: O(k)
Python
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
"""滑动窗口最大值"""
if not nums or k <= 0:
return []
dq = deque()
result = []
for i, num in enumerate(nums): # enumerate同时获取索引和值
# 移除超出窗口的元素
while dq and dq[0] <= i - k:
dq.popleft()
# 移除比当前元素小的元素
while dq and nums[dq[-1]] < num: # 负索引：从末尾倒数访问元素
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
零钱兑换¶
时间复杂度: O(amount × len(coins))
空间复杂度: O(amount)
Python
def coin_change(coins: list[int], amount: int) -> int:
"""零钱兑换 - 完全背包变体"""
# dp[i]表示凑出金额i所需的最少硬币数
dp = [float('inf')] * (amount + 1)
dp[0] = 0 # 金额为0不需要硬币
for coin in coins:
# 正序遍历（完全背包：每种硬币可以无限使用）
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1) # 不使用 vs 使用当前硬币
return dp[amount] if dp[amount] != float('inf') else -1
岛屿数量¶
时间复杂度: O(m × n)
空间复杂度: O(m × n)
Python
def num_islands(grid: list[list[str]]) -> int:
"""岛屿数量"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
count = 0
def dfs(i: int, j: int):
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] != '1':
return
grid[i][j] = '2' # 标记已访问
dfs(i + 1, j)
dfs(i - 1, j)
dfs(i, j + 1)
dfs(i, j - 1)
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
count += 1
dfs(i, j)
return count
11. 工具函数¶
链表相关¶
Python
def create_linked_list(arr: list[int]) -> ListNode:
"""从数组创建链表"""
if not arr:
return None
dummy = ListNode()
current = dummy
for val in arr:
current.next = ListNode(val)
current = current.next
return dummy.next
def linked_list_to_array(head: ListNode) -> list[int]:
"""链表转数组"""
result = []
while head:
result.append(head.val)
head = head.next
return result
二叉树相关¶
Python
from collections import deque
def create_binary_tree(arr: list[int]) -> TreeNode:
"""从数组创建二叉树（层序）"""
if not arr or arr[0] is None:
return None
root = TreeNode(arr[0])
queue = deque([root])
i = 1
while queue and i < len(arr):
node = queue.popleft()
if i < len(arr) and arr[i] is not None:
node.left = TreeNode(arr[i])
queue.append(node.left)
i += 1
if i < len(arr) and arr[i] is not None:
node.right = TreeNode(arr[i])
queue.append(node.right)
i += 1
return root
def level_order_traversal(root: TreeNode) -> list[list[int]]:
"""二叉树层序遍历"""
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
result.append(level)
return result
使用建议¶
学习路径¶
- 基础阶段: 掌握排序、二分搜索、基础数据结构
- 进阶阶段: 学习动态规划、图论算法、高级数据结构
- 面试阶段: 重点练习大厂高频题、设计题
竞赛技巧¶
- 快速复制: 将常用模板整理成代码片段
- 理解原理: 不要死记硬背，理解算法原理
- 多练多用: 通过做题巩固模板的使用
面试技巧¶
- 先讲思路: 写代码前先讲解思路
- 注意边界: 处理好边界条件和特殊情况
- 分析复杂度: 主动分析时间/空间复杂度
最后更新: 2026-01-28
作者: 誌