image-20240305152551079

图论

在图论中，主要的遍历方法就是深度优先搜索和广度优先搜索

图的存储方式主要有以下两种：

  • 邻接矩阵（二维数组）
  • 邻接表

深度优先搜索DFS

深搜三部曲

1、确定递归函数和参数

2、确定终止条件

3、处理目前搜索节点出发的路径

代码框架

1
2
3
4
5
void dfs(参数) {
    处理节点
    dfs(图，选择的节点); // 递归
    回溯，撤销处理结果
}
1
2
3
4
5
6
7
8
9
10
11
direction = [(1, 0), (-1, 0), (0, 1), (0, -1)]

def dfs(grid, visited, x, y):
    for dx, dy in direction:
        nextx = x + dx
        nexty = y + dy
        if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
            continue
        if not visited[nextx][nexty]:
            visited[nextx][nexty] = True
            dfs(grid, visited, nextx, nexty)

广度优先搜索BFS

广度优先搜索适合用于解决两个点之间的最短路径问题

在广度优先搜索中 ，可以使用队列也可以使用栈这样的数据结构，区别就是每一圈的顺序有所不同

BFS的思想在之前的二叉树的层序遍历中已经被使用到了，当时使用了deque()队列进行层序遍历

在图中，我们也可以采用BFS的方式进行遍历，当然采取的数据结构可以是队列，也可以采用栈，但大多数情况下都是用队列的，所以下面的代码中也就采用队列来实现了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
from collections import deque

direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]


def bfs(grid, visited, x, y):
    queue = deque()
    queue.append((x, y))
    visited[x][y] = True
    while queue:
        x, y = queue.popleft()  # 弹出队首元素
        for dx, dy in direction:
            nextx, nexty = x + dx, y + dy
            if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid):
                continue
            if not visited[nextx][nexty]:
                queue.append((nextx, nexty))
                visited[nextx][nexty] = True

拓扑排序

图的应用（参照811）

  • 最小生成树
    • 克鲁斯卡尔算法
    • 普里姆算法
  • 拓扑排序
  • 最短路径问题
    • 单源最短路径
      • BFS
      • 迪杰斯特拉
    • 多源最短路径
      • 弗洛伊德
  • 关键路径
  • 有向无环图描述表达式

image-20240501005242111

并查集相关问题

并查集一般用来解决连通性问题

判断两个元素是否在同一个集合里的时候要使用到并查集

并查集的两个主要功能：

  • 将两个元素添加到同一个集合里
  • 判断两个元素是否在同一个集合里
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
class UnionFind:
    def __init__(self, n):
        self.father = [i for i in range(n)]

    def find(self, u):
        if u != self.father[u]:
            self.father[u] = self.find(self.father[u])  # 进行路径压缩，构成一个根结点连接多个孩子结点的情况
        return self.father[u]

    def isSame(self, u, v):
        return self.find(u) == self.find(v)

    def join(self, u, v):
        u = self.find(u)  # 寻找根的过程
        v = self.find(v)  # 寻找根的过程
        if u == v:
            return
        self.father[v] = u


if __name__ == "__main__":
    n = 1005  # 根据题目中节点数量而定，一般比节点数量稍大一些
    uf = UnionFind(n)
    uf.join(1, 2)
    uf.join(3, 2)
    print(uf.find(1))
    print(uf.find(3))
    print(uf.isSame(1, 4))
    print(uf.isSame(1, 2))
    # 在使用时，可以通过 uf.init() 进行初始化，但在 Python 中不需要显式的初始化函数。

练习题

797、所有可能的路径

所有可能的路径

本题中给出的graph[i]表示第i个节点可以访问的所有节点的列表

递归三部曲：

  • 确定递归函数和参数

1
2
def dfs(graph,path,x): # graph这个图作为最外层传过来的一个参数，其实可以不写
    pass

这里的参数分别代表的含义是：遍历的图，当前已经存在的路径和当前遍历到的顶点序号x

  • 确定终止条件

题目中的要求是需要遍历从节点0到节点n-1，因此终止条件就是当前遍历的顶点序号为len(graph)-1时，即可将该路径path加入到res列表中

  • 处理目前搜索节点出发的路径

1
2
3
4
for node in graph[x]:
    path.append(node)
    dfs(graph,path,node)
    path.pop()

完整代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []

        def backtracking(path, x):
            if x == len(graph) - 1:
                res.append(path[:])
                return

            for node in graph[x]:
                path.append(node)
                backtracking(path, node)
                path.pop()

        backtracking([0], 0)
        return res

image-20240201204537616

注意：初始化的时候需要将起点先加入到path数组中去

总结：

有向图路径问题比较适合用深度优先搜索。

深度优先搜索和广度优先搜索适合解决颜色类的问题

200、岛屿数量

image-20240202103424606

image-20240202103445158

本题类似于找有多少联通分量

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (0, -1), (-1, 0), (1, 0)]

    def dfs(self, grid, visited, x, y):
        for dx, dy in self.dir:
            nextx, nexty = x + dx, y + dy
            if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                continue
            if not visited[nextx][nexty] and grid[nextx][nexty] == "1":
                visited[nextx][nexty] = True
                self.dfs(grid, visited, nextx, nexty)

    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        visited = [[False] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == "1":
                    visited[i][j] = True
                    self.dfs(grid, visited, i, j)
                    res += 1
        return res

BFS

采用广度优先搜索，看看有多少grid[x][y]=='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
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (0, -1), (-1, 0), (1, 0)]

    def bfs(self, grid, visited, x, y):
        queue = deque()
        queue.append((x, y))
        visited[x][y] = True
        while queue:
            x, y = queue.popleft()
            for dx, dy in self.dir:
                nextx, nexty = x + dx, y + dy
                if (
                    nextx < 0
                    or nextx >= len(grid)
                    or nexty < 0
                    or nexty >= len(grid[0])
                ):
                    continue

                if not visited[nextx][nexty] and grid[nextx][nexty] == "1":  # 岛屿
                    visited[nextx][nexty] = True
                    queue.append((nextx, nexty))

    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        visited = [[False] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == "1":
                    self.bfs(grid, visited, i, j)
                    res += 1
        return res

image-20240429211941875

695、岛屿的最大面积

image-20240203222220240

img

image-20240203222235246

在bfs遍历过程中进行岛屿面积的求和，然后将得到的面积与res进行比较，取较大的那个。需要注意的是，在bfs函数一开始的时候，我们就访问了一个结点了，因此此时记录岛屿最大面积的tmp值应该加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
class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False]*n for _ in range(m)]
        dirs = [(-1,0),(0,1),(1,0),(0,-1)]
        res = 0
        tmp = 0
        def bfs(grid, i, j, visited):
            nonlocal tmp
            nonlocal res
            tmp+=1
            q = deque()
            q.append((i,j))
            visited[i][j] = True
            while q:
                x,y = q.popleft()
                for k in dirs:
                    next_i = x + k[0]
                    next_j = y + k[1]
                    if next_i<0 or next_i>=m:
                        continue
                    if next_j<0 or next_j>=n:
                        continue
                    if visited[next_i][next_j]:
                        continue
                    if grid[next_i][next_j]==0:
                        continue
                    q.append((next_i,next_j))
                    visited[next_i][next_j] = True
                    tmp+=1

        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j]==1:
                    tmp=0
                    bfs(grid,i,j,visited)
                    res = max(tmp,res)
        return res

BFS代码：

使用模板进行做题求解

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
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上右下左
        # self.dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        self.max_ = 0

    def bfs(self, grid, visited, x, y):
        queue = deque([(x, y)])
        visited[x][y] = True
        tmp = 1
        while queue:
            x, y = queue.popleft()
            for dx, dy in self.dir:
                nextx, nexty = x + dx, y + dy
                if (
                    nextx < 0
                    or nextx >= len(grid)
                    or nexty < 0
                    or nexty >= len(grid[0])
                ):
                    continue
                if grid[nextx][nexty] == 1 and not visited[nextx][nexty]:
                    queue.append((nextx, nexty))
                    visited[nextx][nexty] = True
                    tmp += 1
        self.max_ = max(self.max_, tmp)

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == 1:
                    self.bfs(grid, visited, i, j)
        return self.max_

DFS代码

本题在使用DFS进行遍历的时候需要注意，递归的过程中每遇到一个岛屿的时候，就需要将其值进行累加，这里给类中定义了一个变量max_用来记录每一次循环过程中的岛屿。

其实这里类似于图论中的联通分量，一个岛屿就是一个联通分量，每到一个联通分量中就会执行一次循环中的dfs，然后再去计算岛屿的面积

在for循环的开始即遍历到的那个节点处，需要将max_值初始化为1，因为当前节点如果是岛屿的话，在dfs过程中不会计算所以需要进行初始化，然后在dfs的最后，我们需要将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
28
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上右下左
        # self.dir = [[0, 1], [1, 0], [0, -1], [-1, 0]]
        self.max_ = 0

    def dfs(self, grid, visited, x, y):
        for dx, dy in self.dir:
            nextx, nexty = x + dx, y + dy
            if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                continue
            if not visited[nextx][nexty] and grid[nextx][nexty] == 1:
                visited[nextx][nexty] = True
                self.dfs(grid, visited, nextx, nexty)
                self.max_ += 1

    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        res = 0
        for i in range(m):
            for j in range(n):
                if not visited[i][j] and grid[i][j] == 1:
                    self.max_ = 1
                    visited[i][j] = True
                    self.dfs(grid, visited, i, j)
                    res = max(res, self.max_)
        return res

image-20240430192449132

1020、飞地的数量

image-20240203221823494

image-20240203221839899

本题的思路就是从边缘四周进行遍历，然后将遍历得到的节点值全部赋为0（和边缘能连通的陆地的1全部修改为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
class Solution:
    def numEnclaves(self, grid: List[List[int]]) -> int:
        # 先从边缘进行遍历，最后统计在中间的岛屿数量
        def dfs(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)
        
        m,n = len(grid),len(grid[0])
        for i in range(m):
            for j in range(n):
                if (i==0 or j==0 or i==m-1 or j==n-1) and grid[i][j]==1:
                    dfs(i,j)
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]==1:
                    res+=1
        return res

总结：

无需记录每个结点是否被访问过了（这是和前几题的区别），只需要在最后统计出grid中值为1有多少个即为最终结果。

BFS思路

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
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def numEnclaves(self, grid: List[List[int]]) -> int:
        # 将四周1改为0  然后遍历中间有多少1
        def bfs(x, y):
            # 修改所有可以联通的地方改成0
            queue = deque([(x, y)])
            # visited[x][y] = True
            if grid[x][y] == 1:
                grid[x][y] = 0
            while queue:
                x, y = queue.popleft()
                for dx, dy in self.dir:
                    nextx, nexty = x + dx, y + dy
                    if (
                        nextx < 0
                        or nextx >= len(grid)
                        or nexty < 0
                        or nexty >= len(grid[0])
                    ):
                        continue
                    if grid[nextx][nexty] == 1:
                        queue.append((nextx, nexty))
                        grid[nextx][nexty] = 0
                        # visited[nextx][nexty] = True

        m, n = len(grid), len(grid[0])

        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and (i == 0 or j == 0 or i == m - 1 or j == n - 1):
                    bfs(i, j)
        # print(mygrid)
        # print(grid)
        # print(grid)
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    res += 1
        return res

image-20240430193118374

130、被围绕的区域

image-20240203222521581

image-20240203222540429

本题的思路是首先将所有边缘能够遍历到的值为O的位置全部修改为A，然后再进行遍历这个图，将所有的O改为X，将所有的A改为O即可

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
class Solution:
    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """
        m, n = len(board), len(board[0])
        dirs = [(1, 0), (0, -1), (-1, 0), (0, 1)]

        def dfs(x, y):
            if 0 <= x < m and 0 <= y < n and board[x][y] == "O":
                board[x][y] = "A"
                for d in dirs:
                    dfs(x + d[0], y + d[1])

        for i in range(m):
            for j in range(n):
                if (i == 0 or i == m - 1 or j == 0 or j == n - 1) and board[i][j] == "O":
                    dfs(i, j)

        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "A":
                    board[i][j] = "O"

image-20240203222906431

dfs遍历实现：

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
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上右下左

    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        # 边缘的O都变成A，将其余的O变成X，再将所有的A变成O
        def dfs(board, x, y):
            # x y 需要满足边界条件
            for dx, dy in self.dir:
                nextx = x + dx
                nexty = y + dy
                if (
                    nextx < 0
                    or nextx >= len(board)
                    or nexty < 0
                    or nexty >= len(board[0])
                ):
                    continue
                if board[nextx][nexty] == "O":
                    board[nextx][nexty] = "A"
                    dfs(board, nextx, nexty)

        m, n = len(board), len(board[0])

        for i in range(m):
            for j in range(n):
                if (
                    i == 0 or i == len(board) - 1 or j == 0 or j == len(board[0]) - 1
                ) and board[i][j] == "O":
                    dfs(board, i, j)
                    board[i][j] = "A"
        # print(board)
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "A":
                    board[i][j] = "O"

image-20240501004056824

BFS实现遍历

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
class Solution:
    def __init__(self):
        self.dir = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上右下左

    def solve(self, board: List[List[str]]) -> None:
        """
        Do not return anything, modify board in-place instead.
        """

        # 边缘的O都变成A，将其余的O变成X，再将所有的A变成O
        def bfs(board, x, y):
            queue = deque([(x, y)])
            board[x][y] = "A"
            while queue:
                x, y = queue.popleft()
                for dx, dy in self.dir:
                    nextx = x + dx
                    nexty = y + dy
                    if (
                        nextx < 0
                        or nextx >= len(board)
                        or nexty < 0
                        or nexty >= len(board[0])
                    ):
                        continue
                    if board[nextx][nexty] == "O":
                        board[nextx][nexty] = "A"
                        queue.append((nextx, nexty))

        m, n = len(board), len(board[0])

        for i in range(m):
            for j in range(n):
                if (
                    i == 0 or i == len(board) - 1 or j == 0 or j == len(board[0]) - 1
                ) and board[i][j] == "O":
                    bfs(board, i, j)
        # print(board)
        for i in range(m):
            for j in range(n):
                if board[i][j] == "O":
                    board[i][j] = "X"
                if board[i][j] == "A":
                    board[i][j] = "O"

BFS这里需要注意在修改代码的最后要将最新符合条件的位置的内容添加到队列当中。

417、太平洋大西洋水流问题

image-20240204190605437

思路：用一个数据结构[(1,2,3,4)]存储所有的节点，如果一个节点是可以从大西洋到太平洋并且可以从太平洋到大西洋就可以添加到结果集合中。

注意：之前的代码有个错误，就是如果一个点既能到太平洋又能到大西洋就会会漏计算，要将elif改成if就可以了

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
class Solution:
    def __init__(self):
        self.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上右下左

    def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
        m, n = len(heights), len(heights[0])
        res = []
        visited = [
            [[False] * 2 for _ in range(n)] for _ in range(m)
        ]  # 用来标记当前位置是否能从太平洋或者大西洋到达 0:太平洋 1:大西洋

        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    visited[i][j][0] = True
                    self.dfs(heights, visited, i, j, 0)
                if i == m - 1 or j == n - 1:
                    visited[i][j][1] = True
                    self.dfs(heights, visited, i, j, 1)
        for i in range(m):
            for j in range(n):
                if visited[i][j][0] and visited[i][j][1]:
                    res.append([i, j])
        return res

    def dfs(self, heights, visited, x, y, flag):
        for dx, dy in self.direction:
            nextx = x + dx
            nexty = y + dy
            # 如果当前位置的高度高于x,y的高度，需要跳过
            if (
                nextx < 0
                or nextx >= len(heights)
                or nexty < 0
                or nexty >= len(heights[0])
                or heights[nextx][nexty] < heights[x][y]
                or visited[nextx][nexty][flag]
            ):
                continue
            # if visited[nextx][nexty][flag] == False:
            visited[nextx][nexty][flag] = True
            self.dfs(heights, visited, nextx, nexty, flag)

BFS代码：

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
from collections import deque


class Solution:
    def __init__(self):
        self.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]  # 上右下左

    def pacificAtlantic(self, heights):
        m, n = len(heights), len(heights[0])
        res = []
        visited = [[[False] * 2 for _ in range(n)] for _ in range(m)]  # 用来标记当前位置是否能从太平洋或者大西洋到达 0:太平洋 1:大西洋

        for i in range(m):
            for j in range(n):
                if i == 0 or j == 0:
                    self.bfs(heights, visited, i, j, 0)
                if i == m - 1 or j == n - 1:
                    self.bfs(heights, visited, i, j, 1)
        for i in range(m):
            for j in range(n):
                if visited[i][j][0] and visited[i][j][1]:
                    res.append([i, j])
        return res

    def bfs(self, heights, visited, x, y, flag):
        queue = deque([(x, y)])
        visited[x][y][flag] = True
        while queue:
            x, y = queue.popleft()
            for dx, dy in self.direction:
                nextx = x + dx
                nexty = y + dy
                if nextx < 0 or nextx >= len(heights) or nexty < 0 or nexty >= len(heights[0]) or heights[nextx][
                    nexty] < heights[x][y] or visited[nextx][nexty][flag]:
                    continue
                visited[nextx][nexty][flag] = True
                queue.append((nextx, nexty))


if __name__ == '__main__':
    s = Solution()
    # heights = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]
    # heights = [[2, 1], [1, 2]]
    heights = [[1, 2, 2, 3, 5], [3, 2, 3, 4, 4], [2, 4, 5, 3, 1], [6, 7, 1, 4, 5], [5, 1, 1, 2, 4]]
    res = s.pacificAtlantic(heights)
    print(res)
    # visited = [[[False] * 2 for _ in range(3)] for _ in range(5)]
    # for i in range(len(visited)):
    #     for j in range(len(visited[0])):
    #         print(visited[i][j][0])

994、腐烂的橘子

image-20240502204651657

image-20240502204701754

image-20240513194951920

类似于树的层次遍历，记录一共有多少层

这里是遍历总共进行几次BFS

这里需要注意：如果一开始有多个腐烂的橘子，需要将其全部添加到初试的队列中，同时这里还有一点需要注意，添加的时候除了其位置i和j，还需要添加一个当前发生的分钟数。这样我们在每次进行bfs的时候，在往queue中添加新的橘子的时候，queue.append((i,j,num+1))这样去添加，这样在同一层的所有的节点的分钟数都是一样的，只有下一层的才会进行num+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
from collections import deque
from typing import List


class Solution:
    def __init__(self):
        self.directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def bfs(self, grid, visited):
        res = 0
        m, n = len(grid), len(grid[0])
        queue = deque()
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j, 0))
        while queue:
            x, y, num = queue.popleft()
            res = max(res, num) # 更新最新的分钟数
            visited[x][y] = True
            for dx, dy in self.directions:
                nextx = x + dx
                nexty = y + dy
                if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:
                    continue
                if grid[nextx][nexty] == 1 and not visited[nextx][nexty]:
                    queue.append((nextx, nexty, num + 1))
                    visited[nextx][nexty] = True
                    grid[nextx][nexty] = 2
        return res

    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        res = self.bfs(grid, visited)
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    return -1
        return res


if __name__ == "__main__":
    grid = [[2, 1, 1], [1, 1, 0], [0, 1, 1]]
    print(Solution().orangesRotting(grid))

image-20240513183931600

方法二：

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
class Solution:
    def __init__(self):
        self.direction = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    def orangesRotting(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        queue = deque()
        fresh = 0
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 2:
                    queue.append((i, j))
                elif grid[i][j] == 1:
                    fresh += 1
        while queue and fresh:
            for _ in range(len(queue)):
                x, y = queue.popleft()
                for dx, dy in self.direction:
                    nextx, nexty = x + dx, y + dy
                    if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:
                        continue
                    if grid[nextx][nexty] == 1:
                        grid[nextx][nexty] = 2
                        queue.append((nextx, nexty))
                        fresh -= 1
            res += 1
        return res if fresh == 0 else -1

image-20240513202315555

827、最大人工岛

image-20240204194827930

【错误思路】本题思路就是将所有的岛屿进行编号并构建哈希表为{编号: 面积}，例如{1: [10, False]}

这里除了记录面积，还需要记录当前的独立的岛屿是否访问过，如果访问过也不能添加，同时每次遍历的过程中要清空访问记录重置一下

下面的代码不幸的超时了

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
from collections import deque, defaultdict

# 超时了一会
class Solution:
    def __init__(self):
        self.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.area = defaultdict(list)

    def largestIsland(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        tag = 2
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and not visited[i][j]:
                    tmp = self.bfs(grid, visited, i, j, tag)
                    self.area[tag].append(tmp)
                    self.area[tag].append(False)
                    tag += 1
        print(self.area)  # {2: 3, 3: 3}
        singleMaxArea = max(self.area[i][0] for i in self.area) if self.area else 0
        for g in grid:
            print(g)
        maxArea = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    for v in self.area.values():
                        v[1] = False
                    tmpArea = 1
                    for dx, dy in self.direction:
                        if i + dx < 0 or i + dx >= len(grid) or j + dy < 0 or j + dy >= len(grid[0]):
                            continue
                        if grid[i + dx][j + dy] in self.area and not self.area[grid[i + dx][j + dy]][1]:
                            tmpArea += self.area[grid[i + dx][j + dy]][0]
                            self.area[grid[i + dx][j + dy]][1] = True
                    # print(tmpArea)
                    maxArea = max(maxArea, tmpArea)
        return maxArea if maxArea != 0 else singleMaxArea

    def bfs(self, grid, visited, x, y, tag):
        tmp = 1
        queue = deque([(x, y)])
        visited[x][y] = True
        grid[x][y] = tag
        while queue:
            x, y = queue.popleft()
            for dx, dy in self.direction:
                nextx = x + dx
                nexty = y + dy
                if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                    continue
                if grid[nextx][nexty] == 1 and not visited[nextx][nexty]:
                    tmp += 1
                    visited[nextx][nexty] = True
                    grid[nextx][nexty] = tag
                    queue.append((nextx, nexty))
        return tmp


if __name__ == '__main__':
    s = Solution()
    # grid = [[1, 1, 0], [1, 0, 1], [0, 1, 1]]
    # grid = [[1, 1], [1, 1]]
    # grid = [[0, 0], [0, 0]]
    grid = [[0, 0, 0, 0, 0, 0, 0], [0, 1, 1, 1, 1, 0, 0], [0, 1, 0, 0, 1, 0, 0], [1, 0, 1, 0, 1, 0, 0],
            [0, 1, 0, 0, 1, 0, 0], [0, 1, 0, 0, 1, 0, 0], [0, 1, 1, 1, 1, 0, 0]]
    print(s.largestIsland(grid))

正确的思路：第一次遍历将所有的岛屿全部统计出来并使用哈希表进行记录，同时对各个岛屿从2开始进行编号，哈希表中的数据为：{2: 10, 3: 5}这样。然后遍历所有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
class Solution:
    def __init__(self):
        self.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]
        self.area = defaultdict(int)

    def largestIsland(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        visited = [[False] * n for _ in range(m)]
        tag = 2
        # 遍历矩阵，统计其中的岛屿面积
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1 and not visited[i][j]:
                    tmp = self.bfs(grid, visited, i, j, tag)
                    self.area[tag] = tmp
                    tag += 1
        # print(self.area)  # {2: [3,False], 3: [3,False]}
        # 同来解决全部是0的情况
        singleMaxArea = max(self.area[i] for i in self.area.keys()) if self.area else 0
        # for g in grid:
        #     print(g)
        maxArea = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 0:
                    # 每轮进行初始化
                    mset = set()
                    tmpArea = 1
                    for dx, dy in self.direction:
                        nextx = i + dx
                        nexty = j + dy
                        if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                            continue
                        mset.add(grid[nextx][nexty])
                    for m in mset:
                        tmpArea += self.area.get(m, 0)
                    maxArea = max(maxArea, tmpArea)

                    # print(tmpArea)
        return maxArea if maxArea != 0 else singleMaxArea

    def bfs(self, grid, visited, x, y, tag):
        tmp = 1
        queue = deque([(x, y)])
        visited[x][y] = True
        grid[x][y] = tag
        while queue:
            x, y = queue.popleft()
            for dx, dy in self.direction:
                nextx = x + dx
                nexty = y + dy
                if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]):
                    continue
                if grid[nextx][nexty] == 1 and not visited[nextx][nexty]:
                    tmp += 1
                    visited[nextx][nexty] = True
                    grid[nextx][nexty] = tag
                    queue.append((nextx, nexty))
        return tmp

463、岛屿的周长

image-20240204220535567

方法1：当碰到水域或者边界处则周长加1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def __init__(self):
        self.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def islandPerimeter(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:  # 岛屿
                    # 遍历四周是海洋还是岛屿
                    for dx, dy in self.direction:
                        nextx = i + dx
                        nexty = j + dy
                        if (
                            nextx < 0
                            or nextx >= m
                            or nexty < 0
                            or nexty >= n
                            or grid[nextx][nexty] == 0
                        ):
                            res += 1
        return res

本题无须进行BFS或者DFS遍历，直接扫描整个表即可

有下面几种情况：

  • nextx<0
  • nextx>=len(grid)
  • nexty<0
  • nexty>=len(grid[0])
  • grid[nextx][nexty]==0岛屿旁边为水域 需要将周长加1

image-20240504154904217

方法2：计算岛屿数量和相邻的岛屿数量

遍历整个图，碰到grid[i][j]==1，则将岛屿数量加1，然后再对该点上下左右四个区域分别进行校验是否是岛屿，进行累加计算出相邻的岛屿数量

最终岛屿数量*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
class Solution:
    def __init__(self):
        # self.direction = [(0, 1), (1, 0)]
        self.direction = [(0, 1), (1, 0), (0, -1), (-1, 0)]

    def islandPerimeter(self, grid) -> int:
        m, n = len(grid), len(grid[0])
        res = 0  # 记录岛屿的数量
        adj = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == 1:
                    res += 1
                    for dx, dy in self.direction:
                        nextx = i + dx
                        nexty = j + dy
                        if nextx < 0 or nextx >= m or nexty < 0 or nexty >= n:
                            continue
                        if grid[nextx][nexty] == 1:
                            adj += 1
        print(res, adj)
        return res * 4 - adj


if __name__ == '__main__':
    # grid = [[1]]
    grid = [[0, 1, 0, 0], [1, 1, 1, 0], [0, 1, 0, 0], [1, 1, 0, 0]]
    print(Solution().islandPerimeter(grid))

image-20240505195213775

127、单词接龙

image-20240513160357495

image-20240513160413580

主要需要解决两个问题：

  • 单词如何作为图连接起来

    • 首先转换为列表，然后通过遍历单词中的每一位字母，然后再进行单词的替换【for循环26次】

  • 起点和终点的最短路径长度

    • BFS如果遍历到终点就结束

哈希表myhash用来记录单词与其对应的变化的次数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    def ladderLength(self, beginWord: str, endWord: str, wordList) -> int:
        wordset = set(wordList)
        if endWord not in wordset:
            return 0
        myhash = {beginWord: 1}
        queue = deque([beginWord])
        while queue:
            word = queue.popleft()
            path = myhash[word]  # 记录当前的步数
            for i in range(len(word)):  # 遍历所有单词
                word_list = list(word)
                for j in range(26):
                    if word_list[i] == chr(ord("a") + j):
                        continue
                    word_list[i] = chr(ord("a") + j)  # 修改单词
                    new_word = "".join(word_list)
                    if new_word == endWord:
                        return path + 1
                    if new_word in wordset and new_word not in myhash:
                        myhash[new_word] = path + 1
                        queue.append(new_word)
        return 0

单词接龙

126、单词接龙II

本题和上一题的区别就在于需要找到所有的最短路径

841、钥匙和房间

image-20240513165027044

image-20240513165040085

采用dfs进行遍历，看所有的房间是否都可以被访问，使用visited数组来表示每个房间是否已经被访问通过，通过dfs遍历之后，只需要判断visited数组是否全部已经访问即可判断所有的房间是否能进入。

注意这里使用all()函数，all()函数的含义是判断传入的可迭代对象是否全部都是True，如果全部为True则返回Ture，否则返回False

这里处理的是当前节点，或者可以采用处理下一个结点的方法

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def dfs(self, rooms, key, visited):
        if visited[key]:
            return
        visited[key] = True
        keys = rooms[key]
        for key in keys:
            self.dfs(rooms, key, visited)

    def canVisitAllRooms(self, rooms) -> bool:
        visited = [False] * len(rooms)
        self.dfs(rooms, 0, visited)
        return all(visited)

处理下一个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def dfs(self, rooms, key, visited):
        keys = rooms[key]
        for key in keys:
            if not visited[key]:
                visited[key] = True
                self.dfs(rooms, key, visited)

    def canVisitAllRooms(self, rooms) -> bool:
        visited = [False] * len(rooms)
        visited[0] = True
        self.dfs(rooms, 0, visited)
        return all(visited)

image-20240513165058165

1971、寻找图中是否存在路径

image-20240513165127395

image-20240513165143136

image-20240513165157570

本题属于并查集的问题，需要判断起点和终点的根结点是否是同一个，本质上类似于并查集模板中isSame()函数所干的事情。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def validPath(self, n: int, edges: List[List[int]], source: int, destination: int) -> bool:
        graph = [i for i in range(n)]   # 初始化一个father数组

        def find(x):
            if graph[x] != x:
                graph[x] = find(graph[x])
            return graph[x]
        # 实现join方法
        for x, y in edges:
            graph[find(x)] = find(y)
        # 这里是isSame()方法
        return find(source) == find(destination)

寻找图中是否存在路径

684、冗余连接

image-20240513165241620

image-20240513165256804

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
    def findRedundantConnection(self, edges):
        n = len(edges)
        graph = [i for i in range(n + 1)]

        def find(x):
            if x != graph[x]:
                graph[x] = find(graph[x])
            return graph[x]

        for u, v in edges:
            if graph[find(u)] == find(v):
                return [u, v]
            graph[find(u)] = find(v)

685、冗余连接II

冗余连接II

image-20240514113128376

本题和冗余连接的区别在于从无向图转变为了有向图，本题中存在三种情况：

  • 所有节点入度均为2
    • img
  • 所有节点入度均为1，但是存在环结构
    • img

计算入度：

使用一个indegree列表，其长度为len(edges)+1【这是因为需要下标和节点进行对应，题目中没有0号节点】，只需要对edges列表进行遍历，对edges[i][1]所指向的节点值加1

做题整体思路：

  • 首先遍历所有的节点，记录入度
  • 将所有入度为2的顶点（对应的边的在edge中的下标）加入到vec列表中【题目说了如果一样的情况下优先输出后一条边，所以进行逆序遍历】
  • 判断vec长度是否超过0，如果超过0说明对应的是第一种入度为2的情况
    • 这个时候需要判断删除入度为2的这条边之后的情况【题目限制本题最多只有两条边对应入度为2】
    • 先判断删除第一条边之后是否还是树【调用方法isTreeAfterRemoveEdge()】，如果是则返回edges[vec[0]]，否则返回edges[vec[1]]
  • 否则对应的是入度为1的情况
    • 寻找树中的环路进行判断getRemovedEdge()，判断删除其中的边是否依旧是一棵树

这里在进行判断的时候isTreeAfterRemoveEdge()和getRemovedEdge()方法都是依赖于并查集的，需要在检查的过程中构建并查集即join()方法

其中isTreeAfterRemoveEdge()方法的实现如下：

遍历的过程中对非删除的边进行构造并查集，先去判断顶点之间是否存在相同的父节点，如果存在则直接返回False，否则将其添加到并查集中，如果循环结束依旧没有返回False则返回True

1
2
3
4
5
6
7
8
def isTreeAfterRemoveEdge(self, edges, index):
    for i in range(len(edges)):
        if i == index:
            continue
        if self.isSame(edges[i][0], edges[i][1]):
            return False
        self.join(edges[i][0], edges[i][1])
    return True

getRemovedEdge()方法的实现如下：

在遍历的过程中进行判断两个顶点是否已经存在于并查集中了，如果存在则直接返回这条边，否则将两个顶点添加到并查集中，如果循环结束依旧没有return，则直接返回空列表

1
2
3
4
5
6
def getRemovedEdge(self, edges):
    for i in range(len(edges)):
        if self.isSame(edges[i][0], edges[i][1]):
            return edges[i]
        self.join(edges[i][0], edges[i][1])
    return []

完整代码如下：

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
class Solution:
    def __init__(self):
        self.n = 1001
        self.father = [i for i in range(self.n)]

    def find(self, u):
        if self.father[u] != u:
            self.father[u] = self.find(self.father[u])
        return self.father[u]

    def join(self, u, v):
        u = self.find(u)
        v = self.find(v)
        if u == v:
            return
        self.father[v] = u

    def isSame(self, u, v):
        return self.find(u) == self.find(v)

    def findRedundantDirectedConnection(self, edges):
        n = len(edges)
        # 将所有入度为2的节点记录下来
        indgree = [0] * (n + 1)  # 因为节点编号是从1到n，所以0号下标忽略 列表长度为n+1
        for edge in edges:
            indgree[edge[1]] += 1
        # print(indgree)
        vec = []  # 存放的是边在edges列表中的下标
        for i in range(n - 1, -1, -1):
            if indgree[edges[i][1]] == 2:
                vec.append(i)
        # print(vec)
        if len(vec) > 0:
            # 说明存在入度为2的顶点 需要删除边进行判断了
            if self.isTreeAfterRemoveEdge(edges, vec[0]):
                return edges[vec[0]]
            else:
                return edges[vec[1]]

        # 剩余的情况：没有入度为2的顶点 一定存在环 需要删除环中的一条边
        return self.getRemovedEdge(edges)

    # 判断删除指定边之后是否仍然构成树结构
    def isTreeAfterRemoveEdge(self, edges, index):
        for i in range(len(edges)):
            if i == index:
                continue
            if self.isSame(edges[i][0], edges[i][1]):
                return False
            self.join(edges[i][0], edges[i][1])
        return True

    def getRemovedEdge(self, edges):
        for i in range(len(edges)):
            if self.isSame(edges[i][0], edges[i][1]):
                return edges[i]
            self.join(edges[i][0], edges[i][1])
        return []

image-20240515163954839

LCR 116. 省份数量

image-20240507162944560

image-20240507163127242

本题的含义就是去找整个图中的联通分量的个数，就看需要进行多少次DFS即可，或者采用BFS的方式也是一样的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution_BFS:

    def findCircleNum(self, isConnected) -> int:
        n = len(isConnected)
        visited = [False] * n
        res = 0
        queue = deque()
        for i in range(n):  # 用来防止出现单独的节点
            if not visited[i]:
                self.bfs(i, isConnected, n, queue, visited)
                res += 1
        return res

    def bfs(self, i, isConnected, n, queue, visited):
        queue.append(i)
        while queue:
            cur = queue.popleft()
            for j in range(n):
                if isConnected[cur][j] == 1 and not visited[j]:
                    queue.append(j)
                    visited[j] = True

DFS

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def dfs(self, i, visited, isConnected):
        for j in range(len(isConnected)):
            if isConnected[i][j] == 1 and not visited[j]:
                visited[i] = True
                self.dfs(j, visited, isConnected)

    def findCircleNum(self, isConnected) -> int:
        n = len(isConnected)
        visited = [False] * n
        res = 0
        for i in range(n):
            if not visited[i]:
                res += 1
                self.dfs(i, visited, isConnected)
        return res

课程表

本题是一个经典的拓扑排序问题，其中解决方法如下：

  • 如果满足拓扑排序，那么其经过的次数最终应该就是拓扑排序的次数【BFS】
  • 通过dfs判断有向图中是否存在环路【DFS】

方法一：

  1. 首先生成一个入度表indegrees
  2. 使用一个队列queue，将所有入度为0的节点入队
  3. 当queue不为空时，依次将堆首节点出队，在课程安排图中删除此节点pre
    • 并不是真正从邻接表中删除此节点，而是将此节点对应的入度-1。
  4. 在每次pre出队时，执行numCourses--

拓扑排序的次数等于课程个数，最后只需要判断numCourses==0即可判断是否成功安排课程表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        indegrees = [0 for _ in range(numCourses)]
        adjacency = [[] for _ in range(numCourses)]
        queue = deque()
        for cur, pre in prerequisites:
            indegrees[cur] += 1
            adjacency[pre].append(cur)
        for i in range(len(indegrees)):
            if not indegrees[i]:
                queue.append(i)
        while queue:
            pre = queue.popleft()
            numCourses -= 1
            for cur in adjacency[pre]:
                indegrees[cur] -= 1
                if not indegrees[cur]: # 入度也为0的 加入
                    queue.append(cur)
        return numCourses == 0