Nature's Beauty
Explore the wonders of the world
概述
本章节收录了一些在基础数据结构与算法之外的重要主题，涵盖位运算技巧、高级数据结构（线段树）、搜索算法（A*）、随机数生成（梅森旋转）、字符串匹配（KMP）、集合合并（并查集）等内容。
一、位运算
位运算是一种直接对二进制数进行操作的运算方式，具有极高的执行效率，常用于优化算法和系统底层编程。
1.1 基础位运算符
| 运算符 |
名称 |
说明 |
& |
与 |
两位都为 1 时结果为 1 |
| |
或 |
任一位为 1 时结果为 1 |
^ |
异或 |
相同为 0，不同为 1 |
<< |
左移 |
所有位向左移动指定的位数 |
>> |
右移 |
所有位向右移动指定的位数 |
~ |
取反 |
所有位取反（0 变 1，1 变 0） |
1.2 常用位运算技巧
判断奇偶性
1
|
n & 1 # 结果为 1 表示奇数，0 表示偶数
|
可以用来将某些位设置为 0
例如 n = n & (n-1) 可以用于判断一个数是否为 2 的幂
假设 n 的二进制表示为 1000，则 n-1 的二进制表示为 0111
1000 & 0111 的结果为 0000 即 0，说明 n 是 2 的幂
还可以用 n & 1 来判断一个数的奇偶性
如果结果为 1，则说明 n 是奇数
如果结果为 0，则说明 n 是偶数
判断是否为 2 的幂
1
2
3
4
|
# 2 的幂的二进制表示只有一个 1
n = 8 # 1000
n - 1 = 7 # 0111
n & (n - 1) == 0 # True，n 是 2 的幂
|
获取二进制最右边的 1
1
2
3
|
n = 12 # 二进制：1100
-n = -12 # 补码：0100
n & -n # 0100，获取最右边 1 的位置
|
-n 是 n 的补码，即 n 的反码加 1
假设 n = 12，其二进制表示为 1100
12 的反码为 0011，故补码为：0011 + 0001 = 0100
n & -n = 1100 & 0100 = 0100 即获取到了 1100 的最右边的 1
交换两个变量（无需临时变量）
1
2
3
4
|
a ^= b
b ^= a
a ^= b
# 等价于：a = a ^ b, b = b ^ a, a = a ^ b
|
原理：异或运算满足 a ^ a = 0、a ^ 0 = a 的特性。第一步 a = a ^ b，第二步 b = b ^ (a ^ b) = a，第三步 a = (a ^ b) ^ a = b。
将最低位设置为 1
1
2
|
n | 1 # 将 n 的二进制最低位设为 1
# 例如：1000 | 1 = 1001
|
1.3 位移运算的数学含义
1
2
|
n << k # 等价于 n * 2^k
n >> k # 等价于 n // 2^k（整数除法）
|
二、线段树
2.1 基本概念
线段树是一种用于维护区间信息的二叉树结构，常见应用包括：
- 区间求和
- 区间最大值/最小值
- 区间更新（如给区间中每个数加 1）
树的结构：根节点代表整个区间 [l, r]，子节点递归代表 [l, mid] 和 [mid+1, r]。若根节点编号为 1，则左子节点编号为 2*id，右子节点为 2*id+1。
2.2 懒标记（Lazy Propagation）
线段树的核心优化是懒标记，它将更新操作分为两个阶段：
- 下推（Push Down）：更新时不直接修改子节点，而是将信息暂存在父节点的懒标记中
- 上提（Pull Up）：查询时若遇到懒标记，先将其应用到子节点，再清除
2.3 完整实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
|
class SegNode:
def __init__(self):
self.l = 0 # 区间左端点
self.r = 0 # 区间右端点
self.sum = 0 # 区间和
self.lazytag = False # 懒标记（区间翻转场景）
class SegTree:
def __init__(self, nums):
n = len(nums)
self.arr = [SegNode() for _ in range(n * 4)]
self.build(1, 0, n - 1, nums)
def build(self, id, l, r, nums):
"""构建线段树"""
self.arr[id].l, self.arr[id].r = l, r
if l == r:
self.arr[id].sum = nums[l]
return
mid = (l + r) >> 1
self.build(id * 2, l, mid, nums)
self.build(id * 2 + 1, mid + 1, r, nums)
self.arr[id].sum = self.arr[id * 2].sum + self.arr[id * 2 + 1].sum
def pushdown(self, id):
"""下推懒标记到子节点"""
if self.arr[id].lazytag:
left, right = id * 2, id * 2 + 1
# 翻转子节点的区间和
self.arr[left].sum = (self.arr[left].r - self.arr[left].l + 1) - self.arr[left].sum
self.arr[right].sum = (self.arr[right].r - self.arr[right].l + 1) - self.arr[right].sum
self.arr[left].lazytag = not self.arr[left].lazytag
self.arr[right].lazytag = not self.arr[right].lazytag
self.arr[id].lazytag = False
def modify(self, id, l, r):
"""区间修改"""
if self.arr[id].l >= l and self.arr[id].r <= r:
self.arr[id].sum = (self.arr[id].r - self.arr[id].l + 1) - self.arr[id].sum
self.arr[id].lazytag = not self.arr[id].lazytag
return
self.pushdown(id)
mid = (self.arr[id].l + self.arr[id].r) >> 1
if self.arr[id * 2].r >= l:
self.modify(id * 2, l, r)
if self.arr[id * 2 + 1].l <= r:
self.modify(id * 2 + 1, l, r)
self.arr[id].sum = self.arr[id * 2].sum + self.arr[id * 2 + 1].sum
def query(self, id, l, r):
"""区间查询"""
if self.arr[id].l >= l and self.arr[id].r <= r:
return self.arr[id].sum
if self.arr[id].r < l or self.arr[id].l > r:
return 0
self.pushdown(id)
res = 0
if self.arr[id * 2].r >= l:
res += self.query(id * 2, l, r)
if self.arr[id * 2 + 1].l <= r:
res += self.query(id * 2 + 1, l, r)
return res
def sum_range(self, left, right):
return self.query(1, left, right)
def reverse_range(self, left, right):
self.modify(1, left, right)
|
复杂度：单次区间更新/查询的时间复杂度为 O(log n)，空间复杂度为 O(n)。
三、A* 寻路算法
3.1 算法原理
A* 算法是一种启发式搜索算法，用于在图形或网格中找到两点之间的最短路径。它结合了 Dijkstra 算法的完备性和最佳优先搜索的高效性。
- 将起点加入开放列表
- 循环直到找到终点或开放列表为空：
a. 从开放列表中取出 f 值最小的节点作为当前节点
b. 将当前节点移到关闭列表
c. 如果当前节点是终点，则回溯路径
d. 遍历当前节点的所有相邻节点：
i. 如果不可通过或在关闭列表中，跳过
ii. 如果不在开放列表中，加入开放列表并计算其 f,g,h 值
iii. 如果在开放列表中，检查是否通过当前节点到达它有更小的 g 值
- 如果开放列表为空且未找到终点，则路径不存在
核心公式：
$$f(n) = g(n) + h(n)$$
| 符号 |
含义 |
f(n) |
节点 n 的综合优先级（越小越优先） |
g(n) |
从起点到节点 n 的实际路径成本 |
h(n) |
从节点 n 到终点的估计成本（启发式函数） |
关键数据结构：
- 开放列表（Open Set）：待检查的节点集合
- 关闭列表（Closed Set）：已检查的节点集合
3.2 启发式函数选择
| 函数类型 |
公式 |
适用场景 |
| 曼哈顿距离 |
|x₁ - x₂| + |y₁ - y₂| |
四方向移动的网格 |
| 欧几里得距离 |
√((x₁-x₂)² + (y₁-y₂)²) |
八方向或任意角度移动 |
| 对角线距离 |
(dx + dy) + (√2 - 2) * min(dx, dy) |
对角线移动 |
3.3 Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
import heapq
import math
class Node:
def __init__(self, x, y, walkable=True):
self.x, self.y = x, y
self.walkable = walkable
self.g = 0 # 实际成本
self.h = 0 # 启发式估计
self.f = 0 # 综合成本
self.parent = None
def __lt__(self, other):
return self.f < other.f
def heuristic(node, end, mode='manhattan'):
"""计算启发式估计成本"""
dx, dy = abs(node.x - end.x), abs(node.y - end.y)
if mode == 'manhattan':
return dx + dy
elif mode == 'euclidean':
return math.sqrt(dx**2 + dy**2)
elif mode == 'diagonal':
return (dx + dy) + (math.sqrt(2) - 2) * min(dx, dy)
return 0
def a_star(grid, start, end, heuristic_mode='manhattan'):
"""A* 寻路算法"""
open_set = []
closed_set = set()
heapq.heappush(open_set, start)
while open_set:
current = heapq.heappop(open_set)
if current == end:
path = []
while current:
path.append((current.x, current.y))
current = current.parent
return path[::-1]
closed_set.add(current)
for dx, dy in [(0, 1), (1, 0), (0, -1), (-1, 0)]:
x, y = current.x + dx, current.y + dy
if not (0 <= x < len(grid) and 0 <= y < len(grid[0])):
continue
neighbor = grid[x][y]
if not neighbor.walkable or neighbor in closed_set:
continue
new_g = current.g + 1
if new_g < neighbor.g or neighbor not in open_set:
neighbor.g = new_g
neighbor.h = heuristic(neighbor, end, heuristic_mode)
neighbor.f = neighbor.g + neighbor.h
neighbor.parent = current
if neighbor not in open_set:
heapq.heappush(open_set, neighbor)
return None # 无路径
# 使用示例
def create_grid(w, h, obstacles):
return [[Node(x, y, (x, y) not in obstacles) for y in range(h)] for x in range(w)]
# 创建10x10网格，设置一些障碍物
grid = create_grid(10, 10, [(1, 1), (2, 1), (3, 1), (4, 1), (5, 1),
(5, 2), (5, 3), (5, 4), (5, 5)])
path = a_star(grid, grid[0][0], grid[7][7])
print("路径:", path)
|
3.4 优化与变体
| 变体 |
特点 |
双向 A* |
从起点和终点同时搜索，可加速 |
动态 A* |
适应环境变化 |
| JPS（跳点搜索） |
优化规则网格的路径查找 |
Theta* |
支持任意角度移动 |
四、梅森旋转算法
4.1 基本概念
梅森旋转算法（Mersenne Twister）是用于生成高质量伪随机数的算法，被广泛应用于科学计算、游戏开发等领域。Python 的 random 模块即基于此算法。
核心参数：
- 状态长度 N = 624
- 周期 M = 397
- 字长 W = 32 位
4.2 Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
|
class mt19937:
def __init__(self, seed):
self.W = 32 # 长度
self.N = 624 # 递归长度
self.M = 397 # 周期
self.R = 31 # 低位掩码
self.A = 0x9908B0DF # bin(int('0x9908B0DF', 16))='0b10011001000010001011000011011111'
self.F = 1812433253 # 初始化梅森旋转链所需参数
self.U = 11
# 位移量和掩码
self.S = 7
self.B = 0x9D2C5680 # '0b10011101001011000101011010000000'
self.T = 15
self.C = 0xEFC60000 # '0b11101111110001100000000000000000'
self.L = 18
self.MASK_LOWER = (1 << self.R) - 1 # 0x7FFFFFFF
self.MASK_UPPER = (1 << self.R) # 0x80000000
# 初始化状态
self.mt = [0] * self.N
self.index = self.N
self._initialize(seed)
def _initialize(self, seed):
# seed 的值作为梅森旋转链 mt 的第一个值 mt[0]
self.mt[0] = seed
# 递推式：mt[i] = F * (mt[i-1] xor (mt[i-1] >> (w-2))) + i
for i in range(1, self.N):
self.mt[i] = (self.F * (self.mt[i-1] ^ (self.mt[i-1] >> (self.W-2))) + i) & 0xFFFFFFFF
# 注意最后的 & 0xFFFFFFFF 操作
def _twist(self):
mt_old = self.mt.copy() # 使用原始状态的副本
# 遍历旋转链 mt，对每个元素进行处理
# mt[i] = mt[i+m] xor ((upper_mask(mt[i]) || lower_mask(mt[i+1]))A)
for i in range(self.N):
# 合并高位和低位：x = (高位 | 低位)
x = (mt_old[i] & self.MASK_UPPER) | (mt_old[(i+1) % self.N] & self.MASK_LOWER)
xA = x >> 1
# 条件异或：当x为奇数时，异或A
if x % 2 != 0:
xA ^= self.A
# 新状态计算
self.mt[i] = mt_old[(i + self.M) % self.N] ^ xA
self.index = 0
def extract_u32(self):
# 当状态耗尽时再执行 _twist
if self.index >= self.N:
self._twist()
y = self.mt[self.index]
self.index += 1
# 温度变换，通过位移和掩码打乱输出
y ^= (y >> self.U)
y ^= (y << self.S) & self.B
y ^= (y << self.T) & self.C
y ^= (y >> self.L)
# 返回 32 位无符号整数
return y & 0xFFFFFFFF
rng = mt19937(123)
print(rng.extract_u32()) # 2991312382
|
在初始化函数中，F 是 1812433253，乘以这个数可能导致数值超过 32 位
原 C 代码中使用的是 32 位无符号整数，而 Python 的整数是任意精度的
所以 Python 在移位和掩码操作时需要注意截断，将结果限制在 32 位
可以和 0xFFFFFFFF 进行按位与操作，以保证结果在 32 位以内
五、字符串 KMP 算法
5.1 算法原理
KMP（Knuth-Morris-Pratt，三位提出者的名字）是一种高效的字符串匹配算法，用于在一个主文本串中查找一个模式串的出现位置。KMP 算法在某些情况下具有更好的性能，特别是在模式串较长或者存在重复字符的情况下。
KMP 算法的核心思想是：当发生不匹配时，利用已经匹配的部分信息，尽可能地减少比较的次数。构建一个部分匹配表，用于保存在模式串中每个位置的最长相等真前缀和后缀的长度。在主文本串中，当发生不匹配时，根据部分匹配表，可以将模式串移动到相对于主文本串的合适位置，而不是重新开始匹配。这样就能够提高匹配的效率。
部分匹配表（Prefix Table）：记录模式串中每个位置的最长相等真前缀和真后缀长度。
5.2 Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
def build_prefix_table(pattern):
"""构建前缀表（部分匹配表）"""
m = len(pattern)
table = [0] * m
j = 0
for i in range(1, m):
while j > 0 and pattern[i] != pattern[j]:
j = table[j - 1]
if pattern[i] == pattern[j]:
j += 1
table[i] = j
return table
def kmp_search(text, pattern):
"""KMP 字符串匹配"""
n, m = len(text), len(pattern)
if m == 0:
return 0
table = build_prefix_table(pattern)
j = 0
for i in range(n):
while j > 0 and text[i] != pattern[j]:
j = table[j - 1]
if text[i] == pattern[j]:
j += 1
if j == m:
return i - m + 1
return -1
# 示例
text = "ABABDABACDABABCABAB"
pattern = "ABABCABAB"
print(kmp_search(text, pattern)) # 10
|
复杂度：预处理 O(m)，匹配 O(n)，总时间复杂度 O(n + m)。
5.3 结合哈希表：字母异位词分组
1
2
3
4
5
6
7
8
9
10
11
12
|
from collections import defaultdict
def group_anagrams(strs):
"""字母异位词分组"""
groups = defaultdict(list)
for s in strs:
key = ''.join(sorted(s))
groups[key].append(s)
return list(groups.values())
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
print(group_anagrams(strs)) # [['eat', 'tea', 'ate'], ['tan', 'nat'], ['bat']]
|
六、并查集
6.1 基本概念
并查集（Union-Find）是一种用于处理集合合并与查询的数据结构，主要支持两种操作：
- Find(x)：查找元素 x 所属集合的根节点
- Union(x, y)：合并元素 x 和 y 所在的集合
6.2 核心优化
| 优化策略 |
描述 |
| 路径压缩 |
查询时，将路径上所有节点直接指向根节点 |
| 按秩合并 |
合并时，将较小的树合并到较大的树下 |
6.3 Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
|
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]:
px, py = py, px
self.parent[py] = px
if self.rank[px] == self.rank[py]:
self.rank[px] += 1
return True
def connected(self, x, y):
"""判断两个元素是否连通"""
return self.find(x) == self.find(y)
# 示例：岛屿数量问题
def num_islands(grid):
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
uf = UnionFind(m * n)
land_count = 0
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
land_count += 1
idx = i * n + j
if j + 1 < n and grid[i][j + 1] == '1':
if uf.union(idx, idx + 1):
land_count -= 1
if i + 1 < m and grid[i + 1][j] == '1':
if uf.union(idx, idx + n):
land_count -= 1
return land_count
|
复杂度：近乎 O(1) 的均摊时间复杂度。
七、位运算实用技巧汇总
| 场景 |
代码 |
说明 |
| 判断奇偶 |
n & 1 |
奇数返回 1 |
| 判断 2 的幂 |
n & (n-1) == 0 |
是返回 True |
| 获取最低位 1 |
n & -n |
提取最右边 1 的值 |
| 消除最低位 1 |
n & (n-1) |
消除最右边 1 |
| 交换两数 |
a ^= b; b ^= a; a ^= b |
无临时变量交换 |
| 设置最低位为 1 |
n | 1 |
将二进制最低位置 1 |
| 判断是否相同 |
a ^ b == 0 |
相同返回 True |
有限状态机
https://www.cnblogs.com/21207-iHome/p/6085334.html
拓展与后续学习建议
-
深入进阶方向
- 树状数组（Fenwick Tree）：线段树的简化版本，适合单点更新 + 区间查询
- Trie 树：字典树，专用于字符串前缀匹配
- 布隆过滤器（Bloom Filter）：空间效率极高的概率数据结构
- 一致性哈希：分布式系统中的负载均衡算法
-
算法练习建议
- 位运算：LC 461（汉明距离）、LC 136（只出现一次的数）
- 线段树：LC 307（区域和检索）、LC 315（计算右侧小于当前元素的个数）
- 并查集：LC 200（岛屿数量）、LC 547（省份数量）
- KMP：LC 28（实现 strStr）
-
工程实践视角
- 游戏开发中的
A* 寻路与导航网格
- 数据库索引中的 B+ 树与跳表
- 编译器中的正则表达式引擎与有限自动机
- 分布式系统中的哈希分片与一致性哈希
记录生活