【力扣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
    

后言

• 并查集这个学得我好累，这就是缺乏基础吧，路漫漫啊