Day9，Hot100（图论）

图论

图论部分保举 acm 模式，由于图的输入处置惩罚不一样
DFS，雷同二叉树的递归遍历
BFS，雷同二叉树的层次遍历
208. 实现 Trie (前缀树)

数据结构大概如下：

• 可以当作是 二十六叉树 （由于26个小写字母）
  
  
  
  

1. class Node:
2.     def __init__(self):
3.         self.son = {}
4.         self.end = False  # end=True, 表示当前结点已经构成一个单词
6. class Trie:
7.     def __init__(self):
8.         self.root = Node()
10.     def insert(self, word: str) -> None:
11.         cur = self.root
12.         for c in word:
13.             if c not in cur.son:
14.                 cur.son[c] = Node()
15.             cur = cur.son[c]
16.         cur.end = True
18.     def find(self, word: str) -> int:
19.         cur = self.root
20.         for c in word:
21.             if c not in cur.son:
22.                 return 0
23.             cur = cur.son[c]
24.         return 2 if cur.end else 1
26.     def search(self, word: str) -> bool:
27.         return self.find(word) == 2
29.     def startsWith(self, prefix: str) -> bool:
30.         return self.find(prefix) != 0

复制代码

---

DFS

（1）200. 岛屿数量

方法一：DFS

1. class Solution:
2.     def numIslands(self, grid: List[List[str]]) -> int:
3.         dx = [0,-1,0,1]
4.         dy = [-1,0,1,0]
6.         def dfs(i, j):
7.             if (not 0 <= i < m) or (not 0 <= j < n) or grid[i][j] == '0':
8.                 return
10.             grid[i][j] = '0'
12.             for idx in range(4):
13.                 x = i + dx[idx]
14.                 y = j + dy[idx]
15.                 dfs(x,y)
17.         m = len(grid)
18.         n = len(grid[0])
19.         ans = 0
20.         for i in range(m):
21.             for j in range(n):
22.                 if grid[i][j] == "1":
23.                     dfs(i,j)  # 把整个岛都标记
24.                     ans += 1
25.         return ans

复制代码

ACM 代码模式：99. 岛屿数量

读取每一行输入map(int, input().split())

• input().split()，将输入的行，按照空格切分每个元素，返回一个list
  
• map(int, input().split())，将 list 中每个元素转化为指定的 int范例，返回一个可迭代的对象
  

比方输入1 2 3 4

• input().split()，得到[‘1’, ‘2’, ‘3’, ‘4’]
  
• list(map(int, input().split()))，[1, 2, 3, 4]
  

1. dx = [-1,0,1,0]
2. dy = [0,-1,0,1]
4. def dfs(i, j):
5.     if not (0<=i<n) or not (0<=j<m) or grid[i][j]==0:
6.         return
7.    
8.     grid[i][j] = 0
9.    
10.     for idx in range(4):
11.         x = dx[idx] + i
12.         y = dy[idx] + j
13.         dfs(x, y)
16. if __name__ == '__main__':
17.     n,m = map(int, input().split())
18.     grid = []
19.     for i in range(n):
20.         grid.append(list(map(int, input().split())))
21.    
22.     # visited = [ [False] * m for _ in range(n) ]
23.    
24.     ans = 0
25.    
26.     for i in range(n):
27.         for j in range(m):
28.             if grid[i][j] == 1:
29.                 dfs(i, j)
30.                 ans += 1
31.    
32.     print(ans)

复制代码

---

（2）100. 岛屿的最大面积

1. dx = [-1, 0, 1, 0]
2. dy = [0, -1, 0, 1]
3. s = 0
5. def dfs(i, j):
6.     if not (0 <= i < n) or not (0 <= j < m) or grid[i][j] == 0:
7.         return
9.     global s
10.     s += 1
11.     grid[i][j] = 0
12.     for idx in range(4):
13.         x = dx[idx] + i
14.         y = dy[idx] + j
15.         dfs(x, y)
18. if __name__ == '__main__':
19.     n, m = map(int, input().split())
20.     grid = []
21.     for i in range(n):
22.         grid.append(list(map(int, input().split())))
24.     ans = 0
26.     for i in range(n):
27.         for j in range(m):
28.             if grid[i][j] == 1:
29.                 s = 0
30.                 dfs(i, j)
31.                 ans = max(ans, s)
32.     print(ans)

复制代码

---

（3）101. 孤岛的总面积

步骤

• 首先把四周靠边界的岛屿都设为 0
  
• 然后遍历剩余的孤岛面积
  

1. dx = [-1,0,1,0]
2. dy = [0,-1,0,1]
3. s = 0
5. def dfs(i,j):
6.     if not (0<=i<n) or not (0<=j<m) or grid[i][j] == 0:
7.         return
8.     global s
9.     s += 1
10.     grid[i][j] = 0
11.     for idx in range(4):
12.         x = dx[idx] + i
13.         y = dy[idx] + j
14.         dfs(x,y)
16. if __name__ == '__main__':
17.     n, m = map(int, input().split())
18.     grid = []
19.     for i in range(n):
20.         grid.append(list(map(int, input().split())))
22.     # 将四周贴边的非孤岛区域转为水
23.     # 遍历第一列和最后一列
24.     for i in range(n):
25.         if grid[i][0] == 1:
26.             dfs(i,0)
27.         elif grid[i][m-1] == 1:
28.             dfs(i,m-1)
30.     # 遍历第一行和最后一行
31.     for j in range(m):
32.         if grid[0][j] == 1:
33.             dfs(0,j)
34.         elif grid[n-1][j] == 1:
35.             dfs(n-1,j)
37.     # 计算孤岛面积
38.     s = 0
39.     for i in range(n):
40.         for j in range(m):
41.             if grid[i][j] == 1:
42.                 dfs(i,j)
43.     print(s)

复制代码

---

（4）102. 沉没孤岛

• 把靠四周的非孤岛标记为2
  
• 接着把剩余的1(孤岛)，标记为0
  
• 末了把2修改回1
  

1. dx = [-1,0,1,0]
2. dy = [0,-1,0,1]
4. def dfs(i,j):
5.     if not (0 <= i < n) or not(0 <= j < m) or grid[i][j] != 1:
6.         return
7.    
8.     grid[i][j] = 2
9.    
10.     for k in range(4):
11.         x = dx[k] + i
12.         y = dy[k] + j
13.         dfs(x,y)
15. if __name__ == '__main__':
16.     n,m = map(int, input().split())
17.     grid = []
18.    
19.     for _ in range(n):
20.         grid.append(list(map(int, input().split())))
21.    
22.     for i in range(n):
23.         if grid[i][0] == 1:
24.             dfs(i, 0)
25.         if grid[i][m-1] == 1:
26.             dfs(i, m-1)
27.    
28.     for j in range(m):
29.         if grid[0][j] == 1:
30.             dfs(0,j)
31.         if grid[n-1][j] == 1:
32.             dfs(n-1, j)
33.             
34.     for i in range(n):
35.         for j in range(m):
36.             if grid[i][j] == 1:
37.                 grid[i][j] = 0
38.             elif grid[i][j] == 2:
39.                 grid[i][j] = 1
40.         print(' '.join(map(str, grid[i])))

复制代码

---

BFS

（1）994. 腐烂的橘子

使用 BFS 是为了实现，同一个时间，当前所有腐烂的橘子同时腐烂周围

1. from collections import deque
2. class Solution:
3.     def orangesRotting(self, grid: List[List[int]]) -> int:
4.         n, m = len(grid), len(grid[0])
5.         q = deque()
6.         
7.         count = 0  # 新鲜橘子数
8.         for i in range(n):
9.             for j in range(m):
10.                 if grid[i][j] == 1:
11.                     count += 1
12.                 elif grid[i][j] == 2:
13.                     q.append((i,j))
15.         dx = [-1,0,1,0]
16.         dy = [0,-1,0,1]
18.         round = 0  # 分钟数
19.         while count > 0 and len(q) > 0:
20.             round += 1
21.             cur = len(q)  # 这一轮有多少个腐烂的橘子一起腐烂周围
22.             for _ in range(cur):
23.                 i,j = q.popleft()
24.                 for idx in range(4):
25.                     x = dx[idx] + i
26.                     y = dy[idx] + j
27.                     if (0<=x<n) and (0<=y<m) and grid[x][y] == 1:
28.                         grid[x][y] = 2
29.                         count -= 1
30.                         q.append((x,y))
32.         if count > 0:
33.             return -1
34.         else:
35.             return round

复制代码

---

（2）207. 课程表

• 每次只能修当前可以修的课程——入度为0的课程
  
• 修完一轮后，再修可以休的课程——入度变为0的课程
  
• 以是我们必要记录每个课程的入度，
  
• 然后必要毗邻矩阵来关联课程之间的关系，从而更新入度
  
  
  
  

1. from collections import deque
2. class Solution:
3.     def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
4.         indegree = [0] * numCourses  # 每个课程的入度(即先修课程有几门)
5.         adj = defaultdict(list) # key为当前课，value为它的后续课程,用列表存
7.         # 初始化入度和邻接表
8.         for cur,pre in prerequisites:
9.             indegree[cur] += 1
10.             adj[pre].append(cur)
11.         # 把入度为0的入队列
12.         q = deque()
13.         for i in range(numCourses):
14.             if indegree[i] == 0:
15.                 q.append(i)
16.         
17.         while q:
18.             n = len(q)
19.             for i in range(n):
20.                 pre = q.popleft()
21.                 numCourses -= 1
22.                 # 遍历课程pre的邻接表：它的后续课程
23.                 for cur in adj[pre]:
24.                     # 将后续课程的入度 -1
25.                     indegree[cur] -= 1
26.                     if indegree[cur] == 0:
27.                         q.append(cur)
28.    
29.         return numCourses == 0

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。