练习题
# 基础题
# 130. 被围绕的区域(Medium)
搜索一圈边上的区域,记录所有与边界相连的 O ,所有内部的 O 都填充为 X
样例
X X X X
X O O X
X X O X
X O X X
1
2
3
4
2
3
4
运行你的函数后,矩阵变为:
X X X X
X X X X
X X X X
X O X X
1
2
3
4
2
3
4
代码
def dfs(i, j, visited, board):
if i < 0 or i >= len(board) or j < 0 or j >= len(board[0]) or visited[i][j]:
return
if board[i][j] != "O":
return
visited[i][j] = 1
dfs(i + 1, j, visited, board)
dfs(i - 1, j, visited, board)
dfs(i, j + 1, visited, board)
dfs(i, j - 1, visited, board)
class Solution:
def solve(self, board: List[List[str]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
if not board: return
n, m = len(board), len(board[0])
visited = [[0] * m for _ in range(n)]
# 搜索周围一圈
for i in range(m):
dfs(0, i, visited, board)
dfs(n - 1, i, visited, board)
for i in range(1, n - 1):
dfs(i, 0, visited, board)
dfs(i, m - 1, visited, board)
for i in range(n):
for j in range(m):
if board[i][j] == 'O' and not visited[i][j]:
board[i][j] = 'X'
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
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
# 257. 二叉树的所有路径(Easy)
使用回溯法
def dfs(root, ans, tmp):
if not root: return
tmp.append(str(root.val))
if not root.left and not root.right:
ans.append('->'.join(tmp))
dfs(root.left, ans, tmp)
dfs(root.right, ans, tmp)
tmp.pop()
class Solution:
def binaryTreePaths(self, root: TreeNode) -> List[str]:
ans = []
dfs(root, ans, [])
return ans
1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
3
4
5
6
7
8
9
10
11
12
13
14
# 进阶
# 310. 最小高度树(Medium)
本题思路难,编程也有不少坑。参考了:最容易理解的bfs,分析简单,注释详细 (opens new window)
思路上:使用BFS搜索,不断删除叶子节点,经过有限次的删除,最后一定剩下 1 或 2 个的节点。
编程上:
- 如何实现? 使用临接矩阵实现
- 如何删除叶子节点? 只调整节点的 degree,不用删除 link 临接矩阵的关系
- 什么时候判断找到结果? 节点只剩1-2个,实现上,直接每次保证最后的queue。当循环结束的时候,最后一个 queue 就是结果。
from collections import defaultdict, deque
class Solution:
def findMinHeightTrees(self, n: int, edges: List[List[int]]) -> List[int]:
if not edges:
return [0]
degree = [0] * n
link = defaultdict(list)
for edge in edges:
degree[edge[0]] += 1 # 节点的度
degree[edge[1]] += 1
link[edge[0]].append(edge[1])
link[edge[1]].append(edge[0])
queue = deque()
for i in range(n):
if degree[i] == 1:
queue.append(i)
while queue:
res = list(queue) # 最后一层是我们的答案!!!
for _ in range(len(queue)):
node = queue.popleft()
for next_node in link[node]:
degree[next_node] -= 1
if degree[next_node] == 1: # 去除 node 后变成叶子节点(度为1)
queue.append(next_node)
return res
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
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
编辑 (opens new window)
上次更新: 2022/10/25, 02:40:54