【力扣hot100】刷题笔记Day15

前言

今天要刷的是图论，还没学过，先看看《代码随想录》这部分的基础

深搜DFS理论基础

深搜三部曲
- 确认递归函数、参数
- 确认终止条件
- 处理目前搜索节点出发的路径

代码框架

void dfs(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

    for (选择：本节点所连接的其他节点) {
        处理节点;
        dfs(图，选择的节点); // 递归
        回溯，撤销处理结果
    }
}

797. 所有可能的路径 - 力扣（LeetCode）

DFS

class Solution:
    def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]:
        res = []   # 存放结果
        path = [0]  # 当前路径
        
        def dfs(root: int):
            if root == len(graph) - 1:  # 如果到达最后节点存入结果，
                res.append(path[:])  # path[:]避免使用引用，deep copy
                return
            for node in graph[root]:  # 遍历root所有节点
                path.append(node)     # path加上当前遍历节点
                dfs(node)             # 下一层继续搜索
                path.pop()            # 回溯，撤销节点
        
        dfs(0)
        return res

广搜BFS理论基础

适用于解决两个点之间的最短路径问题

from collections import deque
dir = [(0, 1), (1, 0), (-1, 0), (0, -1)] # 创建方向元素

def bfs(grid, visited, x, y):
  queue = deque() # 初始化队列
  queue.append((x, y)) # 放入第一个元素/起点
  visited[x][y] = True # 标记为访问过的节点

  while queue: # 遍历队列里的元素
    curx, cury = queue.popleft() # 取出第一个元素
    for dx, dy in dir: # 遍历四个方向
      nextx, nexty = curx + dx, cury + dy
      if nextx < 0 or nextx >= len(grid) or nexty < 0 or nexty >= len(grid[0]): 
        continue  # 越界了，直接跳过
      if not visited[nextx][nexty]: # 如果节点没被访问过  
        queue.append((nextx, nexty)) # 加入队列
        visited[nextx][nexty] = True # 标记为访问过的节点

200. 岛屿数量 - 力扣（LeetCode）

DFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        # visited = [[False] * n for _ in range(m)]  # 如果不能修改用标记grid
        # 深搜当前陆地部分
        def dfs(x, y):  # x表示行，y表示列
            grid[x][y] = "0"  # 遍历到的节点就置为0以防重复，用visited则删除此句
            for nx, ny in [(x-1,y), (x+1,y), (x,y-1), (x,y+1)]:
                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":
                # if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1" and not visited[nx][ny]:
                    # visited[nx][ny] = True
                    dfs(nx,ny)
        # 依次遍历每个节点搜索大陆
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                # if not visited[i][j] and grid[i][j] == '1':
                    # visited[i][j] = True
                    res += 1  # 遇到没访问过的陆地，+1
                    dfs(i, j)
        # 返回总陆地数
        return res

BFS

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        m, n = len(grid), len(grid[0])
        # visited = [[False] * n for _ in range(m)]  # 如果不能修改用visited标记grid中已访问节点
        # 广搜当前陆地部分
        def bfs(x, y):  # x表示行，y表示列
            q = deque()
            q.append((x,y))
            grid[x][y] = "0"  # 遍历到的节点就置为0以防重复，用visited则删除此句
            # visited[x][y] = True  # 用visited
            while q:
                x0, y0 = q.popleft()  # 当前遍历节点加入队列
                for nx, ny in [(x0-1,y0), (x0+1,y0), (x0,y0-1), (x0,y0+1)]:
                    if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1":   # 用visited则删除此句
                    # if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == "1" and not visited[nx][ny]:
                        q.append((nx, ny))
                        grid[nx][ny] = "0"  # 加入列表就标记为访问过，用visited则删除此句
                        # visited[nx][ny] = True  # 用visited                        
        # 依次遍历每个节点搜索大陆
        res = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1":
                # if not visited[i][j] and grid[i][j] == '1':
                    res += 1  # 遇到没访问过的陆地，+1
                    bfs(i, j)
        # 返回总陆地数
        return res

并查集

没接触过并查集，依据这道题在B站大学找了相关视频和文章学习一下

## 解法三：UnionFind 并查集经典解法
class UnionFind: ## 定义为一个类。后面类似的题目，也可以直接搬去使用
    def __init__(self, grid): ## 初始化
        m, n = len(grid), len(grid[0])
        self.count = 0 ## count 是最终结果，初始化为0
        self.parent = [-1] * (m * n)  ## 初始化 parent 数组取值全部为 -1

        ## rank 秩，表示树的高度，在连接的时候要规定秩小的指向秩大的元素
        self.rank = [0] * (m * n) ## rank 用来实现上下左右的合并；初始化全部为 0 
        
        ## 计算陆地的总数 count；修改 parent 数组陆地元素的取值
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1": ## 对于陆地元素，把它的parent初始化为它的一维化的位置
                    self.parent[i * n + j] = i * n + j ## parent初始化为元素本身的一维化的（位置）索引
                    self.count += 1  ## 陆地总数
    
    ## find 方法给union 方法调用
    def find(self, i):
        if self.parent[i] != i: ## 对于索引不等于自身的元素
            self.parent[i] = self.find(self.parent[i]) ## 路径优化。把所有链式关系，简化为一层的父子关系
        return self.parent[i] ## 返回父亲的索引（也等于该索引对应的取值）
    
    ## 最关键是 union 方法，用来处理目标元素并计算岛屿数量
    def union(self, x, y):
        rootx = self.find(x) ## 找到自己的 root 索引
        rooty = self.find(y) ## 找到自己的 root 索引
        if rootx != rooty:  ## 如果不等，则进行合并
            if self.rank[rootx] <= self.rank[rooty]: ## 如果 rank 更小
                self.parent[rootx] = rooty  ## 秩小的指向秩大的元素
            else:
                self.parent[rooty] = rootx  ## 秩小的指向秩大的元素

            if self.rank[rootx] == self.rank[rooty]: ## 如果秩相等
                self.rank[rootx] += 1 ## 如果深度相同，新节点的 rank + 1
            self.count -= 1 ## 合并一次，则陆地数量减一（岛屿数量=陆地数量-总的合并次数）

## 主类 + 主函数
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int: ## 主函数
        nr = len(grid) ## number of row
        if nr == 0:
            return 0
        nc = len(grid[0]) ## number of column

        uf = UnionFind(grid) ## 调用并查集函数

        ## 遍历每一个位置
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == "1": ## 碰到陆地 1
                    grid[r][c] = "0"  ## 先修改为 0
                    for x, y in [(r - 1, c), (r + 1, c), (r, c - 1), (r, c + 1)]: ## 遍历上下左右
                        if 0 <= x < nr and 0 <= y < nc and grid[x][y] == "1": ## 碰到新的 1
                            uf.union(r * nc + c, x * nc + y) ## 调用并查集函数
        
        return uf.count