前言
本讲义围绕算法与数据结构的两大学习阶段展开：必会篇（18 个核心主题）和进阶篇（13 个高级主题）。每个主题均包含概念讲解、Python 代码示例、复杂度分析以及典型应用场景，力求帮助读者从基础到进阶，系统掌握算法思维与编程实践能力。
第一部分：必会篇
1. 数组（Array）
数组是最基础的数据结构，在内存中连续存储相同类型的元素，支持 O(1) 的随机访问。Python 中的 list 本质上是一个动态数组。
# 数组的基本操作arr = [3, 1, 4, 1, 5, 9, 2, 6]# 随机访问 —— O(1)print(arr[0])# 3print(arr[-1])# 6# 尾部追加 —— 均摊 O(1)arr.append(8)# 指定位置插入 —— O(n)arr.insert(2, 99)# 删除元素 —— O(n)arr.remove(1)# 删除第一个值为 1 的元素# 遍历 —— O(n)for i, val in enumerate(arr): print(f”arr[{i}] = {val}”)
关键点：数组适合频繁的随机访问，不适合频繁在中间插入/删除。
2. 字符串（String）
Python 中字符串是不可变序列，底层实现为紧凑的 Unicode 字符数组，支持切片、拼接和丰富的内置方法。
s = ”Hello, 算法世界”# 切片 —— O(k)，k 为切片长度print(s[0:5])# Hello# 查找子串 —— O(n)print(s.find(”算法”))# 7# 替换 —— O(n)print(s.replace(”世界”, ”入门”))# 分割 —— O(n)print(”a,b,c”.split(”,”))# ['a', 'b', 'c']# 判断与转换print(”123”.isdigit())# Trueprint(”AbC”.lower())# 'abc'
常见模式：回文判断、字符计数、子串匹配（KMP）。
3. 排序（Sorting）
Python 内置的 sort() 和 sorted() 使用 Timsort 算法，时间复杂度 O(n log n)，空间复杂度 O(n)。
arr = [5, 2, 8, 1, 9, 3]# 升序排序（原地）arr.sort()# 降序排序arr.sort(reverse=True)# 按自定义键排序words = [”apple”, ”banana”, ”kiwi”, ”pear”]words.sort(key=len)# 按长度排序# 稳定排序：先按长度，再按字母序words.sort(key=lambda x: (len(x), x))
手写快排理解原理：
def quick_sort(nums): if len(nums) <= 1: return nums pivot = nums[len(nums) // 2] left = [x for x in nums if x < pivot] mid = [x for x in nums if x == pivot] right = [x for x in nums if x > pivot] return quick_sort(left) + mid + quick_sort(right)
4. 前缀和（Prefix Sum）
前缀和用于快速计算区间和，预处理 O(n)，查询 O(1)。核心思想是 pre[i] 表示前 i 个元素的和。
def build_prefix_sum(nums): pre = [0] * (len(nums) + 1) for i in range(len(nums)): pre[i + 1] = pre[i] + nums[i] return predef range_sum(pre, left, right): ”””返回 nums[left..right] 的区间和（闭区间）””” return pre[right + 1] - pre[left]nums = [1, 2, 3, 4, 5]pre = build_prefix_sum(nums)print(range_sum(pre, 1, 3))# 2 + 3 + 4 = 9
扩展：二维前缀和、差分数组。
5. 递归（Recursion）
递归是函数调用自身解决问题的编程范式，由终止条件和递归体两部分构成。
# 经典示例：计算阶乘def factorial(n): if n <= 1:# 终止条件 return 1 return n * factorial(n - 1)# 递归体# 斐波那契数列（带记忆化）def fib(n, memo={}): if n in memo: return memo[n] if n <= 1: return n memo[n] = fib(n - 1, memo) + fib(n - 2, memo) return memo[n]
关键点：递归深度受 Python 栈限制（默认约 1000），可用 sys.setrecursionlimit 调整，但更推荐转为迭代或尾递归优化。
6. 循环（Loop / Iteration）
循环是程序中最基本的控制结构，Python 提供了 for 和 while 两种形式。
# for 循环遍历可迭代对象for i in range(5): print(i)# while 循环 —— 适用于不确定迭代次数left, right = 0, 10while left < right: mid = (left + right) // 2 left = mid + 1# 列表推导式 —— Pythonic 的循环写法squares = [x ** 2 for x in range(10)]
技巧：enumerate 同时获取索引和值；zip 并行遍历多个序列；itertools 提供丰富的迭代器工具。
7. 滑动窗口（Sliding Window）
滑动窗口用于在数组/字符串上维护一个可变大小的区间，将 O(n²) 的暴力枚举优化为 O(n)。
def max_sum_subarray(nums, k): ”””固定窗口大小 k 的最大子数组和””” window_sum = sum(nums[:k]) max_sum = window_sum for i in range(k, len(nums)): window_sum += nums[i] - nums[i - k] max_sum = max(max_sum, window_sum) return max_sumdef longest_substring_without_repeating(s): ”””变长窗口：最长无重复字符子串””” seen = {} left = 0 max_len = 0 for right, ch in enumerate(s): if ch in seen and seen[ch] >= left: left = seen[ch] + 1 seen[ch] = right max_len = max(max_len, right - left + 1) return max_len
关键点：固定窗口用 for 循环维护；可变窗口用 while 收缩左边界。
8. 双指针（Two Pointers）
双指针通过两个索引协同移动，将部分 O(n²) 问题降为 O(n)。常见有对撞指针、快慢指针、分离指针三种模式。
def two_sum_sorted(nums, target): ”””对撞指针：在有序数组中找两数之和””” left, right = 0, len(nums) - 1 while left < right: s = nums[left] + nums[right] if s == target: return [left, right] elif s < target: left += 1 else: right -= 1 return []def remove_duplicates(nums): ”””快慢指针：原地去重有序数组””” if not nums: return 0 slow = 0 for fast in range(1, len(nums)): if nums[fast] != nums[slow]: slow += 1 nums[slow] = nums[fast] return slow + 1
9. 栈（Stack）
栈是后进先出（LIFO）的线性结构。Python 的 list 可直接模拟栈（append / pop）。
stack = []# 入栈 —— O(1)stack.append(1)stack.append(2)stack.append(3)# 出栈 —— O(1)print(stack.pop())# 3# 查看栈顶 —— O(1)print(stack[-1])# 2# 典型应用：括号匹配def is_valid_brackets(s): pair = {')': '(', ']': '[', '}': '{'} stack = [] for ch in s: if ch in pair: if not stack or stack.pop() != pair[ch]: return False else: stack.append(ch) return not stack
典型场景：表达式求值、单调栈（找下一个更大元素）、函数调用栈模拟。
10. 进制转换（Base Conversion）
进制转换涉及数字在不同进制表示之间的换算，Python 内置了便捷的转换函数。
# 十进制转其他进制n = 255print(bin(n))# '0b11111111' 二进制print(oct(n))# '0o377' 八进制print(hex(n))# '0xff' 十六进制# 其他进制转十进制print(int('1010', 2))# 10print(int('1A', 16))# 26# 通用进制转换（2-36 进制）def to_base(n, base): digits = ”0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ” if n == 0: return ”0” result = [] while n > 0: result.append(digits[n % base]) n //= base return ''.join(reversed(result))print(to_base(255, 2))# 11111111print(to_base(255, 16))# FF
11. 位运算（Bitwise Operations）
位运算直接操作二进制位，速度极快。Python 中整数以补码形式存储，支持任意精度。
a, b = 5, 3# 5 = 0101, 3 = 0011print(a & b)# 1 (0101 & 0011 = 0001) 按位与print(a | b)# 7 (0101 | 0011 = 0111) 按位或print(a ^ b)# 6 (0101 ^ 0011 = 0110) 按位异或print(~a)# -6 按位取反print(a << 1)# 10 左移一位 = 乘以 2print(a >> 1)# 2 右移一位 = 整除 2# 常用技巧def is_odd(n): return n & 1 == 1# 判断奇偶def is_power_of_two(n): return n > 0 and (n & (n - 1)) == 0# 2 的幂def count_bits(n): ”””统计二进制中 1 的个数””” count = 0 while n: n &= n - 1 count += 1 return count
12. 队列（Queue）
队列是先进先出（FIFO）的线性结构。Python 中推荐使用 collections.deque。
from collections import dequeq = deque()# 入队 —— O(1)q.append(1)q.append(2)q.append(3)# 出队 —— O(1)print(q.popleft())# 1# 查看队首和队尾 —— O(1)print(q[0])# 2print(q[-1])# 3# 双端队列也支持右侧操作q.appendleft(0)# 左侧入队q.pop()# 右侧出队
典型场景：BFS、滑动窗口最大值、生产者-消费者模式。
13. 哈希表（Hash Table）
Python 的 dict 和 set 底层是哈希表，平均 O(1) 的插入、删除和查找。
# dict —— 键值对映射d = {}d[”apple”] = 1d[”banana”] = 2print(d.get(”apple”, 0))# 1print(d.get(”grape”, 0))# 0（默认值）# 遍历for key, val in d.items(): print(f”{key}: {val}”)# set —— 无序不重复集合s = {1, 2, 3}s.add(4)s.remove(2)print(3 in s)# Trueprint(s & {1, 3, 5})# {1, 3} 交集# 典型应用：两数之和def two_sum(nums, target): seen = {} for i, num in enumerate(nums): diff = target - num if diff in seen: return [seen[diff], i] seen[num] = i return []
关键点：Python 字典在 3.7+ 版本保持插入顺序。哈希冲突通过开放寻址法解决。
14. 链表（Linked List）
链表由节点对象串联而成，每个节点包含数据和指向下一节点的指针。
class ListNode: def __init__(self, val=0, next_node=None): self.val = val self.next = next_node# 反转链表（迭代法）def reverse_list(head): prev = None curr = head while curr: nxt = curr.next curr.next = prev prev = curr curr = nxt return prev# 检测环（快慢指针）def has_cycle(head): slow = fast = head while fast and fast.next: slow = slow.next fast = fast.next.next if slow == fast: return True return False# 合并两个有序链表def merge_two_lists(l1, l2): dummy = ListNode() curr = dummy while l1 and l2: if l1.val < l2.val: curr.next = l1 l1 = l1.next else: curr.next = l2 l2 = l2.next curr = curr.next curr.next = l1 or l2 return dummy.next
15. 线性表（Linear List）
线性表是数据元素之间存在一对一关系的抽象数据结构，数组和链表是其两种主要实现。
# Python list 是顺序表的典型实现seq_list = [10, 20, 30, 40]# 自定义简单链表实现线性表接口class LinearList: def __init__(self): self.data = [] def get(self, index): return self.data[index]# O(1) def insert(self, index, val): self.data.insert(index, val)# O(n) def remove(self, index): return self.data.pop(index)# O(n) def size(self): return len(self.data)# O(1)
16. 二分查找（Binary Search）
二分查找在有序序列中每次排除一半搜索空间，时间复杂度 O(log n)。
def binary_search(nums, target): left, right = 0, len(nums) - 1 while left <= right: mid = left + (right - left) // 2 if nums[mid] == target: return mid elif nums[mid] < target: left = mid + 1 else: right = mid - 1 return -1# 查找第一个大于等于 target 的位置（lower_bound）def lower_bound(nums, target): left, right = 0, len(nums) while left < right: mid = left + (right - left) // 2 if nums[mid] < target: left = mid + 1 else: right = mid return left# 二分查找的泛化：在单调函数上搜索def sqrt_binary(x, eps=1e-6): ”””用二分法求平方根””” low, high = 0, max(1, x) while high - low > eps: mid = (low + high) / 2 if mid * mid < x: low = mid else: high = mid return (low + high) / 2
关键点：mid = left + (right - left) // 2 防止溢出；边界条件需根据场景选择 <= 或 <。
17. 矩阵（二维数组）
矩阵是二维数组，Python 中通常用嵌套列表表示。
# 创建 3x4 矩阵matrix = [[0] * 4 for _ in range(3)]# 初始化矩阵matrix = [ [1, 2, 3], [4, 5, 6], [7, 8, 9]]# 遍历for i in range(len(matrix)): for j in range(len(matrix[0])): print(f”({i},{j})={matrix[i][j]}”, end=” ”) print()# 矩阵转置def transpose(mat): return [list(row) for row in zip(*mat)]# 顺时针旋转 90°def rotate_90(mat): return [list(row)[::-1] for row in zip(*mat)]# 螺旋遍历def spiral_order(mat): if not mat: return [] top, bottom = 0, len(mat) - 1 left, right = 0, len(mat[0]) - 1 result = [] while top <= bottom and left <= right: for j in range(left, right + 1): result.append(mat[top][j]) top += 1 for i in range(top, bottom + 1): result.append(mat[i][right]) right -= 1 if top <= bottom: for j in range(right, left - 1, -1): result.append(mat[bottom][j]) bottom -= 1 if left <= right: for i in range(bottom, top - 1, -1): result.append(mat[i][left]) left += 1 return result
注意：创建矩阵时使用列表推导式 [[0]*n for _ in range(m)]，避免 [[0]*n]*m 导致的浅拷贝共享引用问题。
18. 正则表达式（Regular Expression）
正则表达式是强大的字符串模式匹配工具，Python 的 re 模块提供了完整的正则支持。
import retext = ”联系电话：138-1234-5678，邮箱：user@example.com”# 匹配手机号pattern = r”1[3-9]\d-\d{4}-\d{4}”match = re.search(pattern, text)print(match.group())# 138-1234-5678# 匹配邮箱emails = re.findall(r”[\w\.-]+@[\w\.-]+\.\w+”, text)print(emails)# ['user@example.com']# 替换cleaned = re.sub(r”\d{3}-\d{4}-\d{4}”, ”***-****-****”, text)print(cleaned)# 常用元字符速查# . 匹配任意字符（除换行）# \d 数字 \w 字母数字下划线 \s 空白# * 0或多次 + 1或多次 ? 0或1次# {n} 恰好n次 {n,m} n到m次# ^ 开头 $ 结尾# () 分组 | 或
第二部分：进阶篇
19. 树（Tree）
树是非线性层次结构，由节点和边组成。二叉树是最常见的树形结构，每个节点最多有两个子节点。
class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = right# 前序遍历（根 → 左 → 右）def preorder(root): if not root: return [] return [root.val] + preorder(root.left) + preorder(root.right)# 中序遍历（左 → 根 → 右）def inorder(root): if not root: return [] return inorder(root.left) + [root.val] + inorder(root.right)# 后序遍历（左 → 右 → 根）def postorder(root): if not root: return [] return postorder(root.left) + postorder(root.right) + [root.val]# 层序遍历（BFS）from collections import dequedef level_order(root): if not root: return [] result, q = [], deque([root]) while q: level = [] for _ in range(len(q)): node = q.popleft() level.append(node.val) if node.left: q.append(node.left) if node.right: q.append(node.right) result.append(level) return result# 求树的最大深度def max_depth(root): if not root: return 0 return 1 + max(max_depth(root.left), max_depth(root.right))
扩展：二叉搜索树（BST）、平衡树（AVL / 红黑树）、字典树（Trie）、堆。
20. DFS 搜索（Depth-First Search）
深度优先搜索沿一条路径深入到底再回溯，是树和图遍历的基石算法。
def dfs_graph(adj, start): ”””邻接表图的 DFS 递归实现””” visited = set() result = [] def dfs(node): visited.add(node) result.append(node) for neighbor in adj.get(node, []): if neighbor not in visited: dfs(neighbor) dfs(start) return resultdef dfs_iterative(adj, start): ”””DFS 迭代实现（显式栈）””” visited = set() stack = [start] result = [] while stack: node = stack.pop() if node not in visited: visited.add(node) result.append(node) stack.extend(adj.get(node, [])) return result# 示例：无向图graph = { 0: [1, 2], 1: [0, 3, 4], 2: [0, 5], 3: [1], 4: [1], 5: [2]}print(dfs_graph(graph, 0))# [0, 1, 3, 4, 2, 5]
典型场景：连通分量、拓扑排序、路径搜索、子集枚举。
21. BFS 搜索（Breadth-First Search）
广度优先搜索逐层向外扩展，天然适合求解最短路径（无权图）。
from collections import dequedef bfs_graph(adj, start): ”””邻接表图的 BFS””” visited = set([start]) q = deque([start]) result = [] while q: node = q.popleft() result.append(node) for neighbor in adj.get(node, []): if neighbor not in visited: visited.add(neighbor) q.append(neighbor) return result# 最短路径（无权图）def shortest_path(adj, start, target): visited = set([start]) q = deque([(start, 0)])# (节点, 距离) while q: node, dist = q.popleft() if node == target: return dist for neighbor in adj.get(node, []): if neighbor not in visited: visited.add(neighbor) q.append((neighbor, dist + 1)) return -1# 示例graph = {0: [1, 2], 1: [0, 3], 2: [0, 4], 3: [1, 5], 4: [2, 5], 5: [3, 4]}print(bfs_graph(graph, 0))# [0, 1, 2, 3, 4, 5]print(shortest_path(graph, 0, 5))# 3
DFS vs BFS：DFS 适合穷举和回溯；BFS 适合最短路径和层序遍历。DFS 用栈（递归或显式），BFS 用队列。
22. 图（Graph）
图由顶点集和边集组成，分为有向/无向、带权/无权。Python 中常用邻接表或邻接矩阵表示。
from collections import defaultdictimport heapqclass Graph: def __init__(self): self.adj = defaultdict(list) def add_edge(self, u, v, weight=1): self.adj[u].append((v, weight)) self.adj[v].append((u, weight))# 无向图# Dijkstra 最短路径（非负权）def dijkstra(graph, start): dist = {start: 0} pq = [(0, start)] while pq: d, u = heapq.heappop(pq) if d > dist.get(u, float('inf')): continue for v, w in graph.adj[u]: nd = d + w if nd < dist.get(v, float('inf')): dist[v] = nd heapq.heappush(pq, (nd, v)) return dist# 拓扑排序（Kahn 算法，BFS）def topological_sort(graph, n): indegree = [0] * n for u in graph.adj: for v, _ in graph.adj[u]: indegree[v] += 1 q = deque([i for i in range(n) if indegree[i] == 0]) result = [] while q: u = q.popleft() result.append(u) for v, _ in graph.adj[u]: indegree[v] -= 1 if indegree[v] == 0: q.append(v) return result if len(result) == n else []# 空 = 有环
23. 贪心（Greedy）
贪心算法在每一步选择当前最优解，不回溯，期望全局最优。适用于具有最优子结构性质的问题。
# 经典问题：活动选择（最大不重叠区间数）def max_activities(intervals): intervals.sort(key=lambda x: x[1])# 按结束时间排序 count = 0 last_end = float('-inf') for start, end in intervals: if start >= last_end: count += 1 last_end = end return count# 跳跃游戏（最少跳跃次数）def jump_game(nums): jumps = 0 cur_end = 0 farthest = 0 for i in range(len(nums) - 1): farthest = max(farthest, i + nums[i]) if i == cur_end: jumps += 1 cur_end = farthest return jumps# 示例print(max_activities([(1, 3), (2, 5), (3, 6), (4, 7), (6, 8)]))# 输出: 3（选 (1,3), (3,6), (6,8)）
关键点：贪心正确性需要严格的数学证明。常见题型包括区间调度、哈夫曼编码、最小生成树（Kruskal / Prim）。
24. 排列组合（Permutations and Combinations）
排列组合涉及元素的选择与排列，Python 的 itertools 模块提供了便捷工具。
from itertools import permutations, combinations, productitems = [1, 2, 3]# 全排列print(list(permutations(items)))# [(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)]# 选 k 个的组合print(list(combinations(items, 2)))# [(1,2), (1,3), (2,3)]# 笛卡尔积print(list(product(items, repeat=2)))# [(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)]# 手写回溯生成全排列def permute(nums): result = [] def backtrack(path, used): if len(path) == len(nums): result.append(path[:]) return for i in range(len(nums)): if used[i]: continue used[i] = True path.append(nums[i]) backtrack(path, used) path.pop() used[i] = False backtrack([], [False] * len(nums)) return result
25. 动态规划（Dynamic Programming）
动态规划将复杂问题分解为重叠子问题，通过存储中间结果避免重复计算。核心步骤：定义状态、找出转移方程、确定初始条件和遍历顺序。
# 经典 DP：0-1 背包def knapsack(weights, values, capacity): n = len(weights) dp = [0] * (capacity + 1) for i in range(n): for w in range(capacity, weights[i] - 1, -1): dp[w] = max(dp[w], dp[w - weights[i]] + values[i]) return dp[capacity]# 最长递增子序列（LIS）def length_of_lis(nums): dp = [1] * len(nums) for i in range(len(nums)): for j in range(i): if nums[j] < nums[i]: dp[i] = max(dp[i], dp[j] + 1) return max(dp)# 编辑距离（Levenshtein Distance）def edit_distance(word1, word2): m, n = len(word1), len(word2) dp = [[0] * (n + 1) for _ in range(m + 1)] for i in range(m + 1): dp[i][0] = i for j in range(n + 1): dp[0][j] = j for i in range(1, m + 1): for j in range(1, n + 1): if word1[i-1] == word2[j-1]: dp[i][j] = dp[i-1][j-1] else: dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) return dp[m][n]# 示例print(knapsack([2, 3, 4, 5], [3, 4, 5, 6], 8))# 10print(length_of_lis([10, 9, 2, 5, 3, 7, 101, 18]))# 4print(edit_distance(”horse”, ”ros”))# 3
关键点：DP 两个核心要素——最优子结构和重叠子问题。空间优化常用滚动数组。
26. 回溯（Backtracking）
回溯是系统搜索问题所有解的算法，通过尝试-撤销的方式探索解空间树，本质是 DFS + 剪枝。
# N 皇后问题def solve_n_queens(n): result = [] board = [['.'] * n for _ in range(n)] cols = set() diag1 = set()# 主对角线 r - c diag2 = set()# 副对角线 r + c def backtrack(row): if row == n: result.append([''.join(r) for r in board]) return for col in range(n): if col in cols or (row - col) in diag1 \ or (row + col) in diag2: continue board[row][col] = 'Q' cols.add(col) diag1.add(row - col) diag2.add(row + col) backtrack(row + 1) board[row][col] = '.' cols.remove(col) diag1.remove(row - col) diag2.remove(row + col) backtrack(0) return result# 子集生成def subsets(nums): result = [] def backtrack(start, path): result.append(path[:]) for i in range(start, len(nums)): path.append(nums[i]) backtrack(i + 1, path) path.pop() backtrack(0, []) return result
回溯 vs DP：回溯求所有解，DP 求最优解。回溯模板：做选择→递归→撤销选择。
27. 状态机（State Machine）
状态机通过定义状态和转移规则来建模系统行为，在算法中常用于处理有明确状态切换逻辑的问题。
# 经典应用：字符串转整数（atoi）def my_atoi(s): START, SIGN, NUMBER, END = 0, 1, 2, 3 state = START sign = 1 result = 0 INT_MAX = 2**31 - 1 INT_MIN = -2**31 for ch in s: if state == START: if ch == ' ': continue elif ch in '+-': sign = 1 if ch == '+' else -1 state = SIGN elif ch.isdigit(): result = int(ch) state = NUMBER else: break elif state == SIGN: if ch.isdigit(): result = int(ch) state = NUMBER else: break elif state == NUMBER: if ch.isdigit(): digit = int(ch) if result > (INT_MAX - digit) // 10: return INT_MAX if sign == 1 else INT_MIN result = result * 10 + digit else: break return sign * result# 买卖股票最佳时机（含冷冻期）—— DP + 状态机def max_profit_with_cooldown(prices): if not prices: return 0 hold = float('-inf')# 持有 sold = 0# 刚卖出（冷冻期） rest = 0# 不持有（非冷冻期） for p in prices: prev_sold = sold hold = max(hold, rest - p) sold = hold + p rest = max(rest, prev_sold) return max(sold, rest)
28. 并查集（Union-Find / Disjoint Set Union）
并查集维护不相交集合的合并与查询，支持近乎 O(1) 的 find 和 union 操作（含路径压缩和按秩合并）。
class UnionFind: def __init__(self, n): self.parent = list(range(n)) self.rank = [0] * 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]: self.parent[px] = py elif self.rank[px] > self.rank[py]: self.parent[py] = px else: self.parent[py] = px self.rank[px] += 1 return True def connected(self, x, y): return self.find(x) == self.find(y)# 典型应用：判断无向图是否有环def has_cycle(n, edges): uf = UnionFind(n) for u, v in edges: if not uf.union(u, v): return True return False# 岛屿数量def num_islands(grid): if not grid: return 0 m, n = len(grid), len(grid[0]) uf = UnionFind(m * n) count = sum(grid[i][j] == '1' for i in range(m) for j in range(n)) uf.count = count# 实际编码时可用一个 size 计数器来跟踪连通分量数 return count# 简化示意
29. 分治（Divide and Conquer）
分治将问题分解为同类型的子问题，递归求解后合并结果。经典代表：归并排序、快速排序、大整数乘法。
# 归并排序def merge_sort(nums): if len(nums) <= 1: return nums mid = len(nums) // 2 left = merge_sort(nums[:mid]) right = merge_sort(nums[mid:]) return merge(left, right)def merge(left, right): 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# 求数组中的逆序对数量def count_inversions(nums): def merge_count(arr, temp, left, mid, right): i, j, k = left, mid + 1, left inv_count = 0 while i <= mid and j <= right: if arr[i] <= arr[j]: temp[k] = arr[i] i += 1 else: temp[k] = arr[j] inv_count += (mid - i + 1) j += 1 k += 1 while i <= mid: temp[k] = arr[i] i += 1 k += 1 while j <= right: temp[k] = arr[j] j += 1 k += 1 for i in range(left, right + 1): arr[i] = temp[i] return inv_count def sort_count(arr, temp, left, right): inv_count = 0 if left < right: mid = (left + right) // 2 inv_count += sort_count(arr, temp, left, mid) inv_count += sort_count(arr, temp, mid + 1, right) inv_count += merge_count(arr, temp, left, mid, right) return inv_count return sort_count(nums[:], [0]*len(nums), 0, len(nums)-1)
核心思想：分解 → 解决 → 合并。时间复杂度通常为 O(n log n)。
30. 枚举（Enumeration）
枚举是暴力搜索所有可能解的算法策略，通常作为解题的底线方法，配合剪枝优化。
# 枚举所有子集def enumerate_subsets(nums): n = len(nums) result = [] for mask in range(1 << n):# 0 到 2^n - 1 subset = [] for i in range(n): if mask & (1 << i): subset.append(nums[i]) result.append(subset) return result# 枚举 + 剪枝：三数之和为 0def three_sum(nums): nums.sort() result = [] n = len(nums) for i in range(n - 2): if i > 0 and nums[i] == nums[i - 1]: continue# 剪枝：去重 if nums[i] + nums[i+1] + nums[i+2] > 0: break# 剪枝：最小值之和 > 0 if nums[i] + nums[n-2] + nums[n-1] < 0: continue# 剪枝：最大值之和 < 0 left, right = i + 1, n - 1 while left < right: s = nums[i] + nums[left] + nums[right] if s == 0: result.append([nums[i], nums[left], nums[right]]) while left < right and nums[left] == nums[left+1]: left += 1 while left < right and nums[right] == nums[right-1]: right -= 1 left += 1 right -= 1 elif s < 0: left += 1 else: right -= 1 return result
关键点：枚举是算法题的"保底策略"，当找不到更优解法时，先写枚举保分，再考虑优化。
31. 统计（Statistics / Counting）
统计类算法涉及计数、频率分析和概率计算，常与哈希表、前缀和、排序等技巧结合。
from collections import Counter# 频率统计data = [1, 2, 2, 3, 3, 3, 4, 4, 4, 4]counter = Counter(data)print(counter.most_common(2))# [(4, 4), (3, 3)]# 多数元素（Boyer-Moore 投票算法）def majority_element(nums): count = 0 candidate = None for num in nums: if count == 0: candidate = num count += 1 if num == candidate else -1 return candidate# 统计优美子数组（前缀和 + 计数）def number_of_subarrays(nums, k): ”””统计恰好包含 k 个奇数的子数组数量””” count = {0: 1} odd_count = 0 result = 0 for num in nums: if num % 2 == 1: odd_count += 1 result += count.get(odd_count - k, 0) count[odd_count] = count.get(odd_count, 0) + 1 return result# 中位数def median(nums): nums.sort() n = len(nums) if n % 2 == 1: return nums[n // 2] return (nums[n // 2 - 1] + nums[n // 2]) / 2
附录
复杂度速查表
学习建议
本讲义覆盖了 31 个核心算法主题，建议按以下路径学习：
- 先掌握必会篇的 18 个主题，打好基础，每学一个主题至少完成 3-5 道 LeetCode 题目；
- 再进入进阶篇，重点攻克树、DFS/BFS、动态规划和回溯这四个高频难点；
- 最后通过综合题目将各个知识点串联起来，形成完整的算法思维体系。
算法学习没有捷径，唯有持续练习与总结反思。祝学习顺利！
本讲义基于算法学习笔记整理，结合 Python 语言特性编写，适用于算法入门与面试准备。
10个月宝宝每天需要喝多少奶粉？
