【力扣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 dequedir = [(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 = len(grid) 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