【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集：括号生成、岛屿问题、扫雷游戏
《博主简介》
小伙伴们好，我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。
✌更多学习资源，可关注公-仲-hao:【阿旭算法与机器学习】，共同学习交流~
👍感谢小伙伴们点赞、关注！
《------往期经典推荐------》
一、AI应用软件开发实战专栏【链接】
二、机器学习实战专栏【链接】，已更新31期，欢迎关注，持续更新中~~
三、深度学习【Pytorch】专栏【链接】
四、【Stable Diffusion绘画系列】专栏【链接】
DFS
括号生成
| DFS class Solution: def generateParenthesis(self, n: int) -> List[str]: def DFS(left, right, s): if left == n and right == n: res.append(s) return if left < n: DFS(left+1,right,s+'(') if right < left: DFS(left,right + 1,s+')') res = [] DFS(0,0,'') return res BFS class Node: def __init__(self, left, right, s): self.left = left self.right = right self.s = s class Solution: def generateParenthesis(self, n: int) -> List[str]: # BFS写法 res = [] if n == 0: return res queue = [Node(n,n,'')] while queue: node = queue.pop(0) if node.left == 0 and node.right == 0: res.append(node.s) if node.left > 0: queue.append(Node(node.left-1, node.right, node.s+'(')) if node.right > 0 and node.right > node.left: queue.append(Node(node.left, node.right-1, node.s+')')) return res # 写法2： class Solution: def generateParenthesis(self, n: int) -> List[str]: # BFS写法 res = [] if n == 0: return res queue = [(n,n,'')] while queue: node = queue.pop(0) if node[0] == 0 and node[1] == 0: res.append(node[2]) if node[0] > 0: queue.append((node[0]-1, node[1], node[2]+'(')) if node[1] > 0 and node[1] > node[0]: queue.append((node[0], node[1]-1, node[2]+')')) return res |
通常搜索几乎都是用深度优先遍历（回溯算法）。
广度优先遍历，得自己编写结点类，显示使用队列这个数据结构。深度优先遍历的时候，就可以直接使用系统栈，在递归方法执行完成的时候，系统栈顶就把我们所需要的状态信息直接弹出，而无须编写结点类和显示使用栈。
将BFS写法中的pop(0)改为pop()即为深度优先的迭代形式。
对比迭代的BFS写法与递归的DFS写法，可以看到，BFS其实是将DFS的参数当做队列中的一个元素来进行处理罢了，其他的与DFS没有什么区别。
并查集
岛屿问题
| class Solution: def numIslands(self, grid: List[List[str]]) -> int: self.m = len(grid) self.n = len(grid[0]) res = 0 for i in range(self.m): for j in range(self.n): if grid[i][j] == '1': self.sink(i,j,grid) res += 1 return res
def sink(self, i, j, grid): grid[i][j] = '0' for ni,nj in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]: if 0<=ni<self.m and 0<=nj<self.n and grid[ni][nj] == '1': self.sink(ni,nj,grid) |
扫雷游戏
| # DFS class Solution: def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: # DFS i, j = click row, col = len(board), len(board[0]) if board[i][j] == "M": board[i][j] = "X" return board # 计算空白快周围的雷数量 def cal(i, j): res = 0 for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1 return res def dfs(i, j): num = cal(i, j) if num > 0: board[i][j] = str(num) return board[i][j] = "B" for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue nxt_i, nxt_j = i + x, j + y if 0 <= nxt_i < row and 0 <= nxt_j < col and board[nxt_i][nxt_j] == "E": dfs(nxt_i, nxt_j) dfs(i, j) return board # BFS class Solution: def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: i, j = click row, col = len(board), len(board[0]) if board[i][j] == "M": board[i][j] = "X" return board # 计算空白块周围的雷数目 def cal(i, j): res = 0 for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue if 0 <= i + x < row and 0 <= j + y < col and board[i + x][j + y] == "M": res += 1 return res def bfs(i, j): queue = [(i,j)] while queue: i, j = queue.pop(0) num = cal(i, j) if num > 0: board[i][j] = str(num) continue board[i][j] = "B" for x in [1, -1, 0]: for y in [1, -1, 0]: if x == 0 and y == 0: continue nxt_i, nxt_j = i + x, j + y if nxt_i < 0 or nxt_i >= row or nxt_j < 0 or nxt_j >= col: continue if board[nxt_i][nxt_j] == "E": queue.append((nxt_i, nxt_j)) board[nxt_i][nxt_j] = "B" # 主要是用于标识该点已经被访问过，防止后续重复的添加相同的‘E’点 bfs(i, j) return board |
关于本篇文章大家有任何建议或意见，欢迎在评论区留言交流！
觉得不错的小伙伴，感谢点赞、关注加收藏哦！
欢迎关注下方GZH：阿旭算法与机器学习，共同学习交流~