银川 网站建设,北京seo服务商找行者seo,青岛工程有限公司,如何添加网站logo前言
今天要刷的是图论#xff0c;还没学过#xff0c;先看看《代码随想录》这部分的基础
深搜DFS理论基础 深搜三部曲 确认递归函数、参数确认终止条件处理目前搜索节点出发的路径 代码框架 void dfs(参数) {if (终止条件) {存放结果;return;}for (选择#xff1a;本节点…前言
今天要刷的是图论还没学过先看看《代码随想录》这部分的基础
深搜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 copyreturnfor 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 dyif 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), (x1,y), (x,y-1), (x,y1)]: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] Truedfs(nx,ny)# 依次遍历每个节点搜索大陆res 0for 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] Trueres 1 # 遇到没访问过的陆地1dfs(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 # 用visitedwhile q:x0, y0 q.popleft() # 当前遍历节点加入队列for nx, ny in [(x0-1,y0), (x01,y0), (x0,y0-1), (x0,y01)]: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 0for 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 # 遇到没访问过的陆地1bfs(i, j)# 返回总陆地数return res 并查集 没接触过并查集依据这道题在B站大学找了相关视频和文章学习一下 ## 解法三UnionFind 并查集经典解法
class UnionFind: ## 定义为一个类。后面类似的题目也可以直接搬去使用def __init__(self, grid): ## 初始化m, n len(grid), len(grid[0])self.count 0 ## count 是最终结果初始化为0self.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 1self.count - 1 ## 合并一次则陆地数量减一岛屿数量陆地数量-总的合并次数## 主类 主函数
class Solution:def numIslands(self, grid: List[List[str]]) - int: ## 主函数nr len(grid) ## number of rowif nr 0:return 0nc len(grid[0]) ## number of columnuf UnionFind(grid) ## 调用并查集函数## 遍历每一个位置for r in range(nr):for c in range(nc):if grid[r][c] 1: ## 碰到陆地 1grid[r][c] 0 ## 先修改为 0for 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: ## 碰到新的 1uf.union(r * nc c, x * nc y) ## 调用并查集函数return uf.count
后言
并查集这个学得我好累这就是缺乏基础吧路漫漫啊
