图论
岛屿数量
给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [
[‘1’,‘1’,‘1’,‘1’,‘0’],
[‘1’,‘1’,‘0’,‘1’,‘0’],
[‘1’,‘1’,‘0’,‘0’,‘0’],
[‘0’,‘0’,‘0’,‘0’,‘0’]
]
输出：1
grid[i][j] 的值为 ‘0’ 或 ‘1’
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
|
from typing import List
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
"""
使用 DFS（深度优先搜索）或 BFS（广度优先搜索）遍历网格
思路：
- 遍历整个网格，遇到 '1'（陆地）就开始一次 DFS/BFS
- 从这块陆地出发，将所有相邻的陆地都标记为已访问（'0'）
- 每完成一次 DFS/BFS，岛屿数量 +1
- 时间 O(m*n)，空间 O(m*n)（递归栈或队列）
方法一：DFS（深度优先搜索）
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
islands = 0
def dfs(i, j):
"""从 (i, j) 出发，将相邻的陆地都标记为已访问"""
# 越界或遇到水，直接返回
if i < 0 or i >= m or j < 0 or j >= n or grid[i][j] == '0':
return
# 标记为已访问
grid[i][j] = '0'
# 递归访问上下左右四个方向
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':
islands += 1 # 发现新岛屿
dfs(i, j) # 标记整个岛屿为已访问
return islands
def numIslands_bfs(self, grid: List[List[str]]) -> int:
"""
方法二：BFS（广度优先搜索）
思路：
- 使用队列存储待访问的陆地
- 从发现的新岛屿开始，将所有相邻陆地加入队列并标记
- 时间 O(m*n)，空间 O(min(m*n, 岛屿面积))
"""
from collections import deque
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
islands = 0
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
for i in range(m):
for j in range(n):
if grid[i][j] == '1':
islands += 1
grid[i][j] = '0' # 标记为已访问
# BFS
queue = deque([(i, j)])
while queue:
x, y = queue.popleft()
for dx, dy in directions:
nx, ny = x + dx, y + dy
if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':
grid[nx][ny] = '0'
queue.append((nx, ny))
return islands
# 测试用例
grid1 = [
['1', '1', '1', '1', '0'],
['1', '1', '0', '1', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '0', '0', '0']
]
assert Solution().numIslands(grid1) == 1
grid2 = [
['1', '1', '0', '0', '0'],
['1', '1', '0', '0', '0'],
['0', '0', '1', '0', '0'],
['0', '0', '0', '1', '1']
]
assert Solution().numIslands(grid2) == 3
grid3 = [['1']]
assert Solution().numIslands(grid3) == 1
grid4 = [['0']]
assert Solution().numIslands(grid4) == 0
grid5 = [
['1', '1', '1'],
['0', '1', '0'],
['1', '1', '1']
]
assert Solution().numIslands(grid5) == 1
# 手动推导 grid1（DFS）：
# 遍历找到第一个 '1' 在 (0,0)
# islands = 1
# DFS(0,0) 标记整个岛屿：
# (0,0) -> 标记0 -> 递归访问 (1,0),(0,1)
# (1,0) -> 标记0 -> 递归访问 (2,0),(1,1)
# (2,0) -> 标记0 -> ...
# (1,1) -> 标记0 -> 递归访问 (1,2)
# (1,2) -> 标记0 -> ...
# 最终所有陆地都被标记，整个岛屿只算 1 个
# 结果：1
|
腐烂的橘子
在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。
输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
grid[i][j] 仅为 0、1 或 2
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
78
79
80
81
82
83
84
85
86
87
88
|
from typing import List
from collections import deque
class Solution:
def orangesRotting(self, grid: List[List[int]]) -> int:
"""
使用 BFS（广度优先搜索）模拟腐烂传播过程
思路：
- 将所有腐烂橘子（值为2）作为 BFS 的起点
- 每分钟，腐烂橘子会感染周围的新鲜橘子（值为1）
- 用队列记录腐烂橘子的位置和时间
- 最后检查是否还有新鲜橘子未被感染
- 时间 O(m*n)，空间 O(m*n)
"""
if not grid or not grid[0]:
return 0
m, n = len(grid), len(grid[0])
queue = deque()
fresh_count = 0 # 统计新鲜橘子数量
# 初始化：找到所有腐烂橘子，并统计新鲜橘子
for i in range(m):
for j in range(n):
if grid[i][j] == 2:
queue.append((i, j, 0)) # (行, 列, 时间)
elif grid[i][j] == 1:
fresh_count += 1
# 如果没有新鲜橘子，直接返回 0
if fresh_count == 0:
return 0
# BFS 传播腐烂
directions = [(1, 0), (-1, 0), (0, 1), (0, -1)]
minutes = 0
while queue:
i, j, time = queue.popleft()
minutes = time # 记录当前时间
# 感染周围的新鲜橘子
for di, dj in directions:
ni, nj = i + di, j + dj
if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == 1:
grid[ni][nj] = 2 # 感染
fresh_count -= 1
queue.append((ni, nj, time + 1))
# 如果还有新鲜橘子未被感染，返回 -1
if fresh_count > 0:
return -1
return minutes
# 测试用例
assert Solution().orangesRotting([[2, 1, 1], [1, 1, 0], [0, 1, 1]]) == 4
assert Solution().orangesRotting([[2, 1, 1], [0, 1, 1], [1, 0, 1]]) == -1
assert Solution().orangesRotting([[0, 2]]) == 0
assert Solution().orangesRotting([[0]]) == 0
assert Solution().orangesRotting([[1]]) == -1
assert Solution().orangesRotting([[2]]) == 0
assert Solution().orangesRotting([[1, 2]]) == 1
assert Solution().orangesRotting([[1, 1], [1, 1]]) == -1
# 手动推导 grid = [[2,1,1],[1,1,0],[0,1,1]]：
# 初始状态：
# 腐烂橘子位置: (0,0), (0,1), (0,2), (1,0), (2,1)
# 新鲜橘子数量: 5
# 队列: [(0,0,0), (0,1,0), (0,2,0), (1,0,0), (2,1,0)]
#
# 第0分钟: 队列中的腐烂橘子感染周围
# (0,0) -> 感染 (1,0) -> fresh=4
# (0,1) -> 感染 (1,1) -> fresh=3
# (0,2) -> 感染 (1,2) -> fresh=2
# (1,0) -> 感染 (2,0) -> fresh=1
# (2,1) -> 感染 (1,1), (2,0), (2,2) -> (1,1)已感染，只剩 (2,2) -> fresh=1
#
# 第1分钟: 继续感染...
# (1,1) -> 感染 (2,1)...都已感染
# (1,2) -> 感染 (2,2)...已感染
# ...
#
# 第4分钟: 所有新鲜橘子都被感染，fresh=0
# 结果: 4
|
课程表
你这个学期必须选修 numCourses 门课程，记为 0 到 numCourses - 1 。
在选修某些课程之前需要一些先修课程。 先修课程按数组 prerequisites 给出，其中 prerequisites[i] = [ai, bi] ，表示如果要学习课程 ai 则 必须 先学习课程 bi 。
例如，先修课程对 [0, 1] 表示：想要学习课程 0 ，你需要先完成课程 1 。
请你判断是否可能完成所有课程的学习？如果可以，返回 true ；否则，返回 false 。
输入：numCourses = 2, prerequisites = [[1,0]]
输出：true
解释：总共有 2 门课程。学习课程 1 之前，你需要完成课程 0 。这是可能的。
prerequisites[i] 中的所有课程对 互不相同
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
|
from typing import List
from collections import deque, defaultdict
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
检测有向图中是否存在环（拓扑排序）
思路：
- 将课程和先修关系建模为有向图
- prerequisites[i] = [ai, bi] 表示一条边 bi -> ai（bi 是 ai 的前置课程）
- 如果图中存在环，说明有循环依赖，无法完成所有课程
- 使用 Kahn 算法（BFS 拓扑排序）或 DFS 检测环
- 时间 O(V+E)，空间 O(V+E)
方法一：Kahn 算法（BFS 拓扑排序）
- 计算每个节点的入度
- 将入度为 0 的节点加入队列（没有前置课程的课程）
- 不断取出队列中的节点，删除其所有出边
- 如果最后能处理所有节点，说明无环
"""
# 构建邻接表和入度数组
graph = defaultdict(list)
in_degree = [0] * numCourses
for course, prereq in prerequisites:
graph[prereq].append(course) # prereq -> course
in_degree[course] += 1
# 将所有入度为 0 的课程加入队列
queue = deque([i for i in range(numCourses) if in_degree[i] == 0])
visited = 0 # 已访问的课程数
while queue:
course = queue.popleft()
visited += 1
# 删除该课程的所有出边
for next_course in graph[course]:
in_degree[next_course] -= 1
if in_degree[next_course] == 0:
queue.append(next_course)
return visited == numCourses
def canFinish_dfs(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
"""
方法二：DFS 检测环
思路：
- 使用三种状态标记节点：0=未访问, 1=正在访问（在当前dfs路径中）, 2=已完成
- 对每个未访问的节点进行 DFS
- 如果在 DFS 过程中遇到"正在访问"的节点，说明有环
- 时间 O(V+E)，空间 O(V+E)
"""
# 构建邻接表
graph = [[] for _ in range(numCourses)]
for course, prereq in prerequisites:
graph[prereq].append(course)
# 0=未访问, 1=正在访问, 2=已完成
visited = [0] * numCourses
def dfs(course):
"""检测从 course 出发是否有环"""
if visited[course] == 1: # 遇到正在访问的节点，有环
return False
if visited[course] == 2: # 已完成，无需重复检测
return True
visited[course] = 1 # 标记为正在访问
for next_course in graph[course]:
if not dfs(next_course):
return False
visited[course] = 2 # 标记为已完成
return True
# 对每个节点进行 DFS
for course in range(numCourses):
if not dfs(course):
return False
return True
# 测试用例
assert Solution().canFinish(2, [[1, 0]]) == True
assert Solution().canFinish(2, [[1, 0], [0, 1]]) == False
assert Solution().canFinish(3, [[1, 0], [2, 1]]) == True
assert Solution().canFinish(3, [[1, 0], [2, 1], [0, 2]]) == False
assert Solution().canFinish(1, []) == True
assert Solution().canFinish(2, []) == True
# 手动推导 numCourses=2, prerequisites=[[1,0],[0,1]]（有环）：
# 构建图：0 -> 1, 1 -> 0
# 入度：in_degree[0] = 1, in_degree[1] = 1
# 队列：[]
# 无法找到入度为0的节点，无法完成拓扑排序
# 结果：False
# 手动推导 numCourses=3, prerequisites=[[1,0],[2,1]]（无环）：
# 构建图：0 -> 1, 1 -> 2
# 入度：in_degree[0] = 0, in_degree[1] = 1, in_degree[2] = 1
# 队列：[0]
#
# 第1次：取出0，visited=1
# 删除0->1的边，in_degree[1] = 0，队列加入1
# 第2次：取出1，visited=2
# 删除1->2的边，in_degree[2] = 0，队列加入2
# 第3次：取出2，visited=3
#
# visited = 3 = numCourses，可以完成所有课程
# 结果：True
|
实现 Trie (前缀树)
Trie（发音类似 “try”）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。这一数据结构有相当多的应用情景，例如自动补全和拼写检查。
请你实现 Trie 类：
Trie() 初始化前缀树对象。
void insert(String word) 向前缀树中插入字符串 word 。
boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。
输入
[“Trie”, “insert”, “search”, “search”, “startsWith”, “insert”, “search”]
[[], [“apple”], [“apple”], [“app”], [“app”], [“app”], [“app”]]
输出
[null, null, true, false, true, null, true]
解释
Trie trie = new Trie();
trie.insert(“apple”);
trie.search(“apple”); // 返回 True
trie.search(“app”); // 返回 False
trie.startsWith(“app”); // 返回 True
trie.insert(“app”);
trie.search(“app”); // 返回 True
word 和 prefix 仅由小写英文字母组成
insert、search 和 startsWith 调用次数 总计 不超过 3 * 10^4 次
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
|
class TrieNode:
"""
Trie 树的节点
每个节点包含：
- children: 26个子节点（对应26个字母）
- is_end: 是否是某个单词的结尾
"""
def __init__(self):
self.children = {} # 使用字典存储子节点，比数组更节省空间
self.is_end = False
class Trie:
"""
前缀树（Trie）实现
核心思想：
- 将每个字符串拆分成字符路径
- 相同前缀的字符串共享路径
- 每个节点标记是否是某个单词的结尾
例如插入 "apple" 和 "app"：
root
|
a
|
p
|
p
/ | \
e l (空，is_end=True 表示 "app")
|
l
|
e (is_end=True 表示 "apple")
"""
def __init__(self):
self.root = TrieNode()
def insert(self, word: str) -> None:
"""
向前缀树中插入字符串
思路：
- 从根节点开始，逐个字符往下遍历
- 如果路径不存在，则创建新节点
- 遍历完成后，在最后一个节点标记 is_end = True
- 时间 O(len(word))，空间 O(len(word))
"""
node = self.root
for char in word:
# 如果子节点不存在，创建新节点
if char not in node.children:
node.children[char] = TrieNode()
# 移动到下一个节点
node = node.children[char]
# 标记单词结尾
node.is_end = True
def search(self, word: str) -> bool:
"""
搜索字符串是否存在于前缀树中
思路：
- 从根节点开始，逐个字符往下遍历
- 如果某个字符路径不存在，返回 False
- 遍历完成后，检查最后一个节点是否 is_end = True
- 时间 O(len(word))，空间 O(1)
"""
node = self._search_prefix(word)
# 需要检查 is_end，因为 "app" 可能是 "apple" 的前缀
return node is not None and node.is_end
def startsWith(self, prefix: str) -> bool:
"""
判断是否有字符串以前缀 prefix 开头
思路：
- 与 search 类似，但不检查 is_end
- 只要前缀路径存在即可
- 时间 O(len(prefix))，空间 O(1)
"""
return self._search_prefix(prefix) is not None
def _search_prefix(self, prefix: str) -> TrieNode:
"""
查找前缀对应的节点，如果不存在返回 None
"""
node = self.root
for char in prefix:
if char not in node.children:
return None
node = node.children[char]
return node
# 测试用例
trie = Trie()
# insert
trie.insert("apple")
# search
assert trie.search("apple") == True # "apple" 存在
assert trie.search("app") == False # "app" 不存在
assert trie.search("ap") == False # "ap" 不存在
assert trie.search("applee") == False # "applee" 不存在
# startsWith
assert trie.startsWith("app") == True # "app" 是 "apple" 的前缀
assert trie.startsWith("ap") == True # "ap" 是前缀
assert trie.startsWith("apple") == True # "apple" 是前缀
# 插入更多单词
trie.insert("app")
assert trie.search("app") == True # 现在 "app" 存在
assert trie.search("apple") == True # "apple" 仍存在
# 更多测试
trie2 = Trie()
trie2.insert("hello")
trie2.insert("hell")
trie2.insert("heaven")
trie2.insert("heavy")
assert trie2.search("hello") == True
assert trie2.search("hell") == True
assert trie2.search("heaven") == True
assert trie2.search("heavy") == True
assert trie2.search("he") == False
assert trie2.search("heav") == False
assert trie2.startsWith("he") == True
assert trie2.startsWith("hea") == True
assert trie2.startsWith("hell") == True
assert trie2.startsWith("z") == False
# 手动推导操作序列：
# ["Trie","insert","search","search","startsWith","insert","search"]
# [[],["apple"],["apple"],["app"],["app"],["app"],["app"]]
#
# insert("apple"):
# root -> 'a' -> 'p' -> 'p' -> 'l' -> 'e' (is_end=True)
#
# search("apple"):
# 路径存在且 e.is_end=True -> True
#
# search("app"):
# 路径 a->p->p 存在，但 p.is_end=False -> False
#
# startsWith("app"):
# 路径 a->p->p 存在 -> True
#
# insert("app"):
# 路径 a->p->p 存在，只需将 p.is_end=True
#
# search("app"):
# 路径 a->p->p 存在且 p.is_end=True -> True
#
# 结果：[None, None, True, False, True, None, True]
|
回溯
全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
nums 中的所有整数 互不相同
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
|
from typing import List
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
"""
全排列 - 回溯算法
思路：
- 使用回溯遍历所有可能的排列
- 用 used 数组标记已使用的元素
- 每层选择一个未使用的元素加入路径
- 当路径长度等于 nums 长度时，收集一个完整排列
- 时间 O(n! * n)，空间 O(n)
回溯树示例（nums = [1,2,3]）：
[]
/ | \\
[1] [2] [3]
/ \ / \ / \\
[1,2] [1,3] [2,1] [2,3] [3,1] [3,2]
| | | | | |
[1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]
"""
result = []
path = []
used = [False] * len(nums)
def backtrack():
# 终止条件：路径长度等于数组长度
if len(path) == len(nums):
result.append(path.copy()) # 注意要拷贝！
return
# 选择列表：所有未使用的元素
for i in range(len(nums)):
if not used[i]:
# 做选择
path.append(nums[i])
used[i] = True
# 递归
backtrack()
# 撤销选择
path.pop()
used[i] = False
backtrack()
return result
def permute_v2(self, nums: List[int]) -> List[List[int]]:
"""
方法二：交换法（原地修改数组）
思路：
- 不使用 used 数组，而是通过交换元素来标记已使用
- 第 i 层固定 nums[i]，递归排列剩余元素
- 递归结束后换回来（撤销操作）
- 时间 O(n! * n)，空间 O(n)
"""
result = []
def backtrack(start):
# 终止条件
if start == len(nums):
result.append(nums.copy())
return
# 从 start 开始，每个元素都可能成为当前位置的元素
for i in range(start, len(nums)):
# 做选择：将 nums[i] 换到 start 位置
nums[start], nums[i] = nums[i], nums[start]
# 递归：处理下一个位置
backtrack(start + 1)
# 撤销选择：换回来
nums[start], nums[i] = nums[i], nums[start]
backtrack(0)
return result
# 测试用例
assert Solution().permute([1, 2, 3]) == [
[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
]
assert Solution().permute([0, 1]) == [[0, 1], [1, 0]]
assert Solution().permute([1]) == [[1]]
assert Solution().permute([1, 2, 3, 4]) == 24 # 4! = 24 种排列
# 手动推导 nums = [1, 2, 3] 的全排列：
# path = [], used = [F, F, F]
# 第一次循环 (i=0, num=1):
# path = [1], used = [T, F, F]
# 第二次循环 (i=1, num=2):
# path = [1, 2], used = [T, T, F]
# 第三次循环 (i=2, num=3):
# path = [1, 2, 3], used = [T, T, T] -> 添加排列 [1, 2, 3]
# 回溯: path = [1, 2], used = [T, T, F]
# 回溯: path = [1], used = [T, F, F]
# 第三次循环 (i=2, num=3):
# path = [1, 3], used = [T, F, T]
# 第二次循环 (i=1, num=2):
# path = [1, 3, 2] -> 添加排列 [1, 3, 2]
# 回溯: ...
# 第二次循环 (i=1, num=2): 类似...
# 第三次循环 (i=2, num=3): 类似...
# 最终得到 6 种排列
|
子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
nums 中的所有元素 互不相同
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
|
from typing import List
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
"""
子集 - 回溯算法
思路：
- 生成所有可能的子集，等价于遍历所有选择/不选择每个元素的情况
- 从空集开始，每个元素都有"选择"和"不选择"两种分支
- 时间 O(n * 2^n)，空间 O(n)
回溯树示例（nums = [1,2,3]）：
[]
/ \\
[1] []
/ \\ / \\
[1,2] [1] [2] []
/ \\ / \\ / \\ / \\
[1,2,3] [1,2] [1] [1,3] [1] [2,3] [2] [3] []
|
... (所有叶子节点即为所有子集)
子集总数：2^n（每个元素都有选/不选两种状态）
"""
result = []
path = []
def backtrack(start):
# 收集所有节点（不仅仅是叶子节点）
result.append(path.copy())
# 选择列表：nums[start:]
for i in range(start, len(nums)):
# 做选择
path.append(nums[i])
# 递归：注意 start 变成 i+1，避免重复选择
backtrack(i + 1)
# 撤销选择
path.pop()
backtrack(0)
return result
def subsets_v2(self, nums: List[int]) -> List[List[int]]:
"""
方法二：迭代法（逐个添加元素）
思路：
- 初始只有空集
- 遍历每个元素，将它加入所有已有子集，形成新子集
- 时间 O(n * 2^n)，空间 O(n)
"""
result = [[]] # 初始只有空集
for num in nums:
# 当前所有新子集 = 当前所有子集 + 当前子集 + num
new_subsets = [subset + [num] for subset in result]
result.extend(new_subsets)
return result
def subsets_bit(self, nums: List[int]) -> List[List[int]]:
"""
方法三：位运算
思路：
- n 个元素共有 2^n 个子集
- 用 0 到 2^n-1 的二进制数表示选择状态
- 第 i 位为 1 表示选择 nums[i]
- 时间 O(n * 2^n)，空间 O(1) 不计输出
"""
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
# 测试用例
assert Solution().subsets([1, 2, 3]) == [
[], [1], [2], [1, 2], [3], [1, 3], [2, 3], [1, 2, 3]
]
assert Solution().subsets([0]) == [[], [0]]
assert Solution().subsets([]) == [[]]
assert len(Solution().subsets([1, 2, 3, 4, 5, 6, 7, 8, 9, 10])) == 1024 # 2^10
# 手动推导 nums = [1, 2, 3] 的子集：
# backtrack(0):
# result = [[]] # 添加空集
# i=0:
# path = [1]
# backtrack(1):
# result = [[], [1]] # 添加 [1]
# i=1:
# path = [1, 2]
# backtrack(2):
# result = [[], [1], [1,2]] # 添加 [1,2]
# i=2:
# path = [1, 2, 3]
# backtrack(3):
# result = [[], [1], [1,2], [1,2,3]] # 添加 [1,2,3]
# path = [1, 2]
# path = [1]
# i=2:
# path = [1, 3]
# backtrack(3):
# result = [[], [1], [1,2], [1,2,3], [1,3]] # 添加 [1,3]
# path = [1]
# i=1:
# path = [2]
# backtrack(2):
# result = [[], [1], [1,2], [1,2,3], [1,3], [2]] # 添加 [2]
# i=2:
# path = [2, 3]
# backtrack(3):
# result = [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3]] # 添加 [2,3]
# path = [2]
# i=2:
# path = [3]
# backtrack(3):
# result = [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]] # 添加 [3]
# 最终：[[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]
|
电话号码的字母组合
给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。
给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。
输入：digits = “23”
输出：[“ad”,“ae”,“af”,“bd”,“be”,“bf”,“cd”,“ce”,“cf”]
digits[i] 是范围 [‘2’, ‘9’] 的一个数字。
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
|
from typing import List
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
"""
电话号码的字母组合 - 回溯算法
思路：
- 建立数字到字母的映射
- 对每个数字，遍历其对应的所有字母
- 使用回溯构建所有可能的组合
- 时间 O(4^n * n)，空间 O(n)
数字到字母映射：
2 -> abc
3 -> def
4 -> ghi
5 -> jkl
6 -> mno
7 -> pqrs
8 -> tuv
9 -> wxyz
回溯树示例（digits = "23"）：
""
/ | \\
"a" "b" "c"
/|\\ /|\\ /|\\
ad ae af bd be bf cd ce cf
"""
if not digits:
return []
# 建立映射
phone = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
result = []
path = []
def backtrack(index):
# 终止条件：处理完所有数字
if index == len(digits):
result.append(''.join(path))
return
# 当前数字对应的所有字母
letters = phone[digits[index]]
for letter in letters:
# 做选择
path.append(letter)
# 递归处理下一个数字
backtrack(index + 1)
# 撤销选择
path.pop()
backtrack(0)
return result
def letterCombinations_bfs(self, digits: str) -> List[str]:
"""
方法二：BFS（队列）
思路：
- 从空字符串开始
- 对每个数字，将队列中每个字符串扩展为该数字对应的所有字母
- 时间 O(4^n * n)，空间 O(4^n)
"""
if not digits:
return []
phone = {
'2': 'abc', '3': 'def', '4': 'ghi', '5': 'jkl',
'6': 'mno', '7': 'pqrs', '8': 'tuv', '9': 'wxyz'
}
from collections import deque
queue = deque([''])
for digit in digits:
letters = phone[digit]
for _ in range(len(queue)):
cur = queue.popleft()
for letter in letters:
queue.append(cur + letter)
return list(queue)
# 测试用例
assert Solution().letterCombinations("23") == [
"ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"
]
assert Solution().letterCombinations("2") == ["a", "b", "c"]
assert Solution().letterCombinations("") == []
assert Solution().letterCombinations("79") == [
"pw", "px", "py", "pz", "qw", "qx", "qy", "qz", "rw", "rx", "ry", "rz", "sw", "sx", "sy", "sz"
]
# 手动推导 digits = "23"：
# 初始：queue = [""]
# 处理 digit='2':
# queue.pop() = ""
# 扩展 "": ["a", "b", "c"]
# queue = ["a", "b", "c"]
# 处理 digit='3':
# i=0: queue.pop() = "a"
# 扩展 "a": ["ad", "ae", "af"]
# queue = ["b", "c", "ad", "ae", "af"]
# i=1: queue.pop() = "b"
# 扩展 "b": ["bd", "be", "bf"]
# queue = ["c", "ad", "ae", "af", "bd", "be", "bf"]
# i=2: queue.pop() = "c"
# 扩展 "c": ["cd", "ce", "cf"]
# queue = ["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
# 最终：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"]
|
组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
解释：
2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。
7 也是一个候选， 7 = 7 。
仅有这两种组合。
candidates 的所有元素 互不相同
1 <= target <= 40
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
|
from typing import List
class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
"""
组合总和 - 回溯算法（可重复选取元素）
思路：
- 每个元素可以重复选取（所以 start 仍然是 i）
- 对数组排序，便于剪枝（当 sum > target 时停止）
- 时间 O(T * n!)，空间 O(n)（递归栈深度）
与子集的区别：
- 子集：收集所有叶子节点
- 组合总和：收集路径和等于 target 的叶子节点
"""
result = []
path = []
candidates.sort() # 排序，便于剪枝
def backtrack(start, target):
# 终止条件
if target == 0:
result.append(path.copy())
return
if target < 0:
return # 剪枝：target 为负，提前终止
# 选择列表：candidates[start:]
for i in range(start, len(candidates)):
# 剪枝：如果当前元素大于 target，后面的也一定大于（已排序）
if candidates[i] > target:
break
# 做选择
path.append(candidates[i])
# 递归：i 不变，因为元素可以重复选取
backtrack(i, target - candidates[i])
# 撤销选择
path.pop()
backtrack(0, target)
return result
def combinationSum_v2(self, candidates: List[int], target: int) -> List[List[int]]:
"""
方法二：动态规划（分组背包）
思路：
- dp[i] 表示和为 i 的所有组合
- 对于每个 candidate，将其加入所有已有的和
- 时间 O(target * n * count)，空间 O(target * count)
"""
dp = [[] for _ in range(target + 1)]
dp[0] = [[]] # 和为0只有空集
for candidate in candidates:
for i in range(candidate, target + 1):
for combo in dp[i - candidate]:
dp[i].append(combo + [candidate])
return dp[target]
# 测试用例
assert Solution().combinationSum([2, 3, 6, 7], 7) == [[2, 2, 3], [7]]
assert Solution().combinationSum([2, 3, 5], 8) == [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
assert Solution().combinationSum([2], 1) == []
assert Solution().combinationSum([1], 1) == [[1]]
assert Solution().combinationSum([1], 2) == [[1, 1]]
assert Solution().combinationSum([2, 5, 8], 10) == [[2, 2, 2, 2, 2], [2, 3, 5], [2, 8]]
# 手动推导 candidates = [2, 3, 6, 7], target = 7：
# candidates 排序后: [2, 3, 6, 7]
#
# backtrack(0, 7):
# i=0 (num=2):
# path=[2], backtrack(0, 5)
# i=0 (num=2):
# path=[2,2], backtrack(0, 3)
# i=0 (num=2):
# path=[2,2,2], backtrack(0, 1) -> target < 0, return
# i=1 (num=3):
# path=[2,2,3], backtrack(1, 0) -> target==0, 添加 [2,2,3]
# i=1 (num=3):
# path=[2,3], backtrack(1, 2)
# i=2 (num=6) > 2, break
# i=2 (num=6) > 5, break
# i=1 (num=3):
# path=[3], backtrack(1, 4)
# ... (无法组成7)
# i=2 (num=6):
# path=[6], backtrack(2, 1) -> target < 0, return
# i=3 (num=7):
# path=[7], backtrack(3, 0) -> target==0, 添加 [7]
#
# 结果: [[2,2,3], [7]]
|
括号生成
数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。
输入：n = 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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
|
from typing import List
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
"""
括号生成 - 回溯算法
思路：
- 合法括号序列的条件：
1. 左括号数量 <= n
2. 右括号数量 <= 左括号数量
3. 总括号数 = 2n
- 使用回溯生成所有可能的括号组合
- 时间 O(4^n / sqrt(n))，空间 O(n)
剪枝条件：
- open < n：可以添加左括号
- close < open：可以添加右括号
"""
result = []
path = []
def backtrack(open_cnt, close_cnt):
# 终止条件：左右括号都添加完毕
if open_cnt == n and close_cnt == n:
result.append(''.join(path))
return
# 添加左括号：只要左括号数量 < n
if open_cnt < n:
path.append('(')
backtrack(open_cnt + 1, close_cnt)
path.pop()
# 添加右括号：右括号数量 < 左括号数量
if close_cnt < open_cnt:
path.append(')')
backtrack(open_cnt, close_cnt + 1)
path.pop()
backtrack(0, 0)
return result
def generateParenthesis_v2(self, n: int) -> List[str]:
"""
方法二：递归（分治）
思路：
- 将问题分解为：("(" + 左边 + ")" + 右边)
- 左边和右边的括号对数之和 = n
- 时间 O(4^n / sqrt(n))，空间 O(n)
"""
if n == 0:
return [""]
result = []
for left in range(n):
for left_result in self.generateParenthesis(left):
for right_result in self.generateParenthesis(n - 1 - left):
result.append("(" + left_result + ")" + right_result)
return result
# 测试用例
assert Solution().generateParenthesis(3) == [
"((()))", "(()())", "(())()", "()(())", "()()()"
]
assert Solution().generateParenthesis(1) == ["()"]
assert Solution().generateParenthesis(0) == [""]
assert len(Solution().generateParenthesis(4)) == 14 # Catalan数 C(2n, n)/(n+1)
# 手动推导 n=3 的括号生成过程：
# backtrack(0, 0):
# 添加 '(': path="(", backtrack(1, 0)
# 添加 '(': path="((", backtrack(2, 0)
# 添加 '(': path="(((", backtrack(3, 0)
# # open_cnt == n == 3，不能再添加 '('
# 添加 ')': path="((()", backtrack(3, 1)
# 添加 ')': path="((())", backtrack(3, 2)
# 添加 ')': path="((()))", backtrack(3, 3) -> 添加 "((()))"
# 添加 ')': path="(()(", backtrack(2, 1)
# 添加 '(': path="(()()", backtrack(3, 1)
# ... -> 添加 "(()())"
# 添加 ')': path="(())(", backtrack(2, 2)
# ... -> 添加 "(())()"
# 添加 ')': path="()(", backtrack(1, 1)
# ... -> 添加 "()()()", "()(())"
#
# 结果: ["((()))", "(()())", "(())()", "()(())", "()()()"]
|
单词搜索
给定一个 m x n 二维字符网格 board 和一个字符串单词 word 。如果 word 存在于网格中，返回 true ；否则，返回 false 。
单词必须按照字母顺序，通过相邻的单元格内的字母构成，其中“相邻”单元格是那些水平相邻或垂直相邻的单元格。同一个单元格内的字母不允许被重复使用。
输入：board = [[‘A’,‘B’,‘C’,‘E’],[‘S’,‘F’,‘C’,‘S’],[‘A’,‘D’,‘E’,‘E’]], word = “ABCCED”
输出：true
board 和 word 仅由大小写英文字母组成
进阶：你可以使用搜索剪枝的技术来优化解决方案，使其在 board 更大的情况下可以更快解决问题？
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
|
from typing import List
class Solution:
def exist(self, board: List[List[str]], word: str) -> bool:
"""
单词搜索 - 回溯算法
思路：
- 从网格中每个格子出发，尝试匹配单词
- 使用 visited 标记已访问的格子
- 上下左右四个方向深度优先搜索
- 时间 O(m * n * 4^L)，空间 O(m * n + L)
L = len(word)，搜索空间是 4^L（每个位置有4个方向可选）
"""
if not board or not board[0]:
return False
m, n = len(board), len(board[0])
def dfs(i, j, index):
# 终止条件
if index == len(word):
return True
# 越界或已访问或字符不匹配
if i < 0 or i >= m or j < 0 or j >= n:
return False
if board[i][j] != word[index]:
return False
# 标记为已访问
board[i][j] = '#' # 用 '#' 标记，避免额外 visited 数组
# 四个方向搜索
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if dfs(i + di, j + dj, index + 1):
board[i][j] = word[index - 1] if index > 0 else word[0] # 恢复
return True
# 恢复
board[i][j] = word[index]
return False
# 从每个格子出发尝试
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
def exist_optimized(self, board: List[List[str]], word: str) -> bool:
"""
方法二：优化剪枝
思路：
- 预处理：统计 word 中每个字符出现的次数
- 在搜索前检查 board 中是否包含足够的字符
- 减少无效搜索
"""
from collections import Counter
# 预处理：检查字符频率
word_count = Counter(word)
board_count = Counter(c for row in board for c in row)
for ch, cnt in word_count.items():
if board_count[ch] < cnt:
return False
m, n = len(board), len(board[0])
def dfs(i, j, index):
if index == len(word):
return True
if i < 0 or i >= m or j < 0 or j >= n:
return False
if board[i][j] != word[index]:
return False
board[i][j] = '#'
for di, dj in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
if dfs(i + di, j + dj, index + 1):
board[i][j] = word[index]
return True
board[i][j] = word[index]
return False
for i in range(m):
for j in range(n):
if dfs(i, j, 0):
return True
return False
# 测试用例
board1 = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']]
assert Solution().exist(board1, "ABCCED") == True
assert Solution().exist(board1, "SEE") == True
assert Solution().exist(board1, "ABCB") == False
assert Solution().exist([['a']], "a") == True
assert Solution().exist([['a']], "b") == False
assert Solution().exist([['a', 'a']], "aaa") == False
# 手动推导 board = [['A','B','C','E'],['S','F','C','S'],['A','D','E','E']], word = "ABCCED"：
#
# 从 (0,0)='A' 开始：
# word[0]='A', 匹配
# 尝试四个方向：
# (1,0)='S', word[1]='B', 不匹配
# (0,1)='B', word[1]='B', 匹配
# 从 (0,1)='B' 继续：
# word[2]='C', (0,2)='C', 匹配
# 从 (0,2)='C' 继续：
# word[3]='C', (0,3)='E', 不匹配
# (1,2)='C', word[3]='C', 匹配
# 从 (1,2)='C' 继续：
# word[4]='E', (2,2)='E', 匹配
# 从 (2,2)='E' 继续：
# word[5]='D', (2,1)='D', 匹配 -> 找到！
#
# 结果: True
|
分割回文串
给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
输入：s = “aab”
输出：[[“a”,“a”,“b”],[“aa”,“b”]]
s 仅由小写英文字母组成
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
from typing import List
class Solution:
def partition(self, s: str) -> List[List[str]]:
"""
分割回文串 - 回溯算法
思路：
- 找到所有将字符串分割成回文子串的方案
- 从左到右遍历，每次截取一个子串检查是否回文
- 如果是回文，继续递归处理剩余部分
- 时间 O(n * 2^n)，空间 O(n)
判断回文的方法：
- 中心扩展法：枚举回文中心，向两边扩展
- 动态规划：预处理所有子串是否为回文
"""
result = []
path = []
def is_palindrome(sub: str) -> bool:
"""判断子串是否为回文"""
return sub == sub[::-1]
def backtrack(start):
# 终止条件：处理完整个字符串
if start == len(s):
result.append(path.copy())
return
# 选择列表：s[start:]
for i in range(start, len(s)):
# 截取子串
sub = s[start:i + 1]
# 剪枝：如果不是回文，跳过
if not is_palindrome(sub):
continue
# 做选择
path.append(sub)
# 递归：处理剩余部分
backtrack(i + 1)
# 撤销选择
path.pop()
backtrack(0)
return result
def partition_dp(self, s: str) -> List[List[str]]:
"""
方法二：动态规划预处理 + 回溯
思路：
- 先用 DP 预处理所有子串是否为回文
- 回溯时直接查表，避免重复判断
- 时间 O(n^2 + n * 2^n)，空间 O(n^2)
"""
n = len(s)
# dp[i][j] 表示 s[i:j+1] 是否为回文
dp = [[False] * n for _ in range(n)]
# 单字符都是回文
for i in range(n):
dp[i][i] = True
# 两字符
for i in range(n - 1):
dp[i][i + 1] = (s[i] == s[i + 1])
# 长度从 3 到 n
for length in range(3, n + 1):
for i in range(n - length + 1):
j = i + length - 1
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
result = []
path = []
def backtrack(start):
if start == n:
result.append(path.copy())
return
for i in range(start, n):
if dp[start][i]:
path.append(s[start:i + 1])
backtrack(i + 1)
path.pop()
backtrack(0)
return result
# 测试用例
assert Solution().partition("aab") == [["a", "a", "b"], ["aa", "b"]]
assert Solution().partition("a") == [["a"]]
assert Solution().partition("abc") == [["a", "b", "c"]]
assert Solution().partition("aabbaa") == [
["a", "a", "b", "b", "a", "a"],
["a", "a", "bb", "a", "a"],
["a", "a", "b", "b", "aa"],
["a", "a", "bb", "aa"],
["aa", "b", "b", "a", "a"],
["aa", "bb", "a", "a"],
["aa", "b", "b", "aa"],
["aa", "bb", "aa"]
]
# 手动推导 s = "aab" 的分割方案：
# backtrack(0):
# i=0: sub="a", 是回文
# path=["a"], backtrack(1)
# i=1: sub="a", 是回文
# path=["a","a"], backtrack(2)
# i=2: sub="b", 是回文
# path=["a","a","b"], backtrack(3) -> 添加 ["a","a","b"]
# i=2: sub="ab", 不是回文, 跳过
# i=1: sub="aa", 是回文
# path=["aa"], backtrack(2)
# i=2: sub="b", 是回文
# path=["aa","b"], backtrack(3) -> 添加 ["aa","b"]
# i=2: sub="aab", 不是回文, 跳过
#
# 结果: [["a","a","b"], ["aa","b"]]
|
N 皇后
按照国际象棋的规则，皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。
n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
给你一个整数 n ，返回所有不同的 n 皇后问题 的解决方案。
每一种解法包含一个不同的 n 皇后问题 的棋子放置方案，该方案中 ‘Q’ 和 ‘.’ 分别代表了皇后和空位。
输入：n = 4
输出：[[".Q..","…Q",“Q…”,"..Q."],["..Q.",“Q…”,"…Q",".Q.."]]
解释：如上图所示，4 皇后问题存在两个不同的解法。
1 <= n <= 9
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
|
from typing import List
class Solution:
def solveNQueens(self, n: int) -> List[List[str]]:
"""
N 皇后 - 回溯算法
思路：
- 逐行放置皇后
- 放置时检查当前位置是否与已放置的皇后冲突
- 冲突条件：
1. 同列：col_used[j]
2. 左上到右下的对角线：row - col = 常数
3. 右上到左下的对角线：row + col = 常数
- 时间 O(n!)，空间 O(n)
8皇后问题共有 92 种解法
N 皇后的约束条件可视化：
棋盘坐标 (r, c)，对角线编号：
- 主对角线 (左上到右下): r - c = 常数，范围 -(n-1) 到 (n-1)
- 副对角线 (右上到左下): r + c = 常数，范围 0 到 2(n-1)
"""
result = []
# 记录已放置皇后的列和对角线
cols = set() # 已使用的列
diag1 = set() # 主对角线 r - c
diag2 = set() # 副对角线 r + c
board = [['.' for _ in range(n)] for _ in range(n)]
def backtrack(row):
# 终止条件：所有行都放置了皇后
if row == n:
result.append([''.join(row) for row in board])
return
# 尝试在每一列放置皇后
for col in range(n):
# 计算对角线编号
d1 = row - col # 主对角线
d2 = row + col # 副对角线
# 检查是否冲突
if col in cols or d1 in diag1 or d2 in diag2:
continue
# 放置皇后
cols.add(col)
diag1.add(d1)
diag2.add(d2)
board[row][col] = 'Q'
# 递归放置下一行
backtrack(row + 1)
# 撤销放置
cols.remove(col)
diag1.remove(d1)
diag2.remove(d2)
board[row][col] = '.'
backtrack(0)
return result
def solveNQueens_optimized(self, n: int) -> List[List[str]]:
"""
方法二：位运算优化
思路：
- 使用位运算代替集合，效率更高
- 位掩码表示列和两条对角线的占用情况
- 时间 O(n!)，空间 O(n)
"""
result = []
board = [['.'] * n for _ in range(n)]
def backtrack(row, cols, diag1, diag2):
if row == n:
result.append([''.join(r) for r in board])
return
# 找出当前行可以放置皇后的列
# cols, diag1, diag2 的第 i 位为 1 表示不可用
available = (~(cols | diag1 | diag2)) & ((1 << n) - 1)
while available:
# 取出最低位的 1
col_bit = available & (-available)
col = (col_bit.bit_length() - 1)
# 放置皇后
board[row][col] = 'Q'
# 递归，bit 位为 1 表示占用
backtrack(
row + 1,
cols | col_bit,
(diag1 | col_bit) << 1,
(diag2 | col_bit) >> 1
)
# 撤销放置
board[row][col] = '.'
# 清除已使用的位
available &= available - 1
backtrack(0, 0, 0, 0)
return result
# 测试用例
assert Solution().solveNQueens(1) == [["Q"]]
assert Solution().solveNQueens(4) == [
[".Q..", "...Q", "Q...", "..Q."],
["..Q.", "Q...", "...Q", ".Q.."]
]
assert len(Solution().solveNQueens(8)) == 92 # 8皇后共有92个解
# 手动推导 n=4 的解法：
# 初始：cols={}, diag1={}, diag2={}, row=0
#
# row=0:
# col=0: d1=0, d2=0 -> 放置 Q
# cols={0}, diag1={0}, diag2={0}, row=1
# row=1:
# col=0: 冲突 (col=0)
# col=1: d1=0, 冲突 (diag1)
# col=2: d1=-1, d2=3 -> 放置 Q
# cols={0,2}, diag1={0,-1}, diag2={0,3}, row=2
# row=2:
# col=0: 冲突 (col)
# col=1: d1=1, d2=3 -> 冲突 (diag2)
# col=2: 冲突 (col)
# col=3: d1=-1 -> 冲突 (diag1)
# 回溯到 row=1
# col=3: d1=-3, d2=3 -> 放置 Q
# ...
# 最终找到解 ["..Q.", "Q...", "...Q", ".Q.."]
#
# 另一种解法: [".Q..", "...Q", "Q...", "..Q."]
|
记录生活