绵阳网站建设培训,网站规划和建设,网页设计自己做网页素材,h5模板在线设计《博主简介》 小伙伴们好#xff0c;我是阿旭。专注于人工智能AI、python、计算机视觉相关分享研究。 ✌更多学习资源#xff0c;可关注公-仲-hao:【阿旭算法与机器学习】#xff0c;共同学习交流~ #x1f44d;感谢小伙伴们点赞、关注#xff01; 《------往期经典推荐--… 《博主简介》 小伙伴们好我是阿旭。专注于人工智能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(left1,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),(i1,j),(i,j-1),(i,j1)]: if 0niself.m and 0njself.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阿旭算法与机器学习共同学习交流~
