【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏

简介: 【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索DFS与并查集:括号生成、岛屿问题、扫雷游戏

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


相关文章
|
19天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
17 3
|
1月前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
26 2
|
1月前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
21 2
|
1月前
|
存储 算法 调度
力扣中级算法(Python)
力扣中级算法(Python)
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1月前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-1
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
26天前
|
算法
力扣经典150题第三十八题:生命游戏
力扣经典150题第三十八题:生命游戏
10 0
|
29天前
|
算法 C语言 计算机视觉
【数据结构与算法 经典例题】括号匹配问题
【数据结构与算法 经典例题】括号匹配问题
|
1月前
|
人工智能 算法 搜索推荐
蓝桥杯宝藏排序题目算法(冒泡、选择、插入)
以下是内容的摘要: 本文介绍了三种排序算法:冒泡排序、选择排序和插入排序。冒泡排序通过不断交换相邻的逆序元素逐步排序,最坏情况下需要 O(n^2) 次比较。选择排序在每轮中找到剩余部分的最小元素并放到已排序序列的末尾,同样具有 O(n^2) 时间复杂度。插入排序则是将每个元素插入到已排序序列的正确位置,时间复杂度也是 O(n^2),但空间复杂度为 O(1)。
|
1月前
|
算法
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题:字母大小写全排列、括号生成