# 【经典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

## 并查集

### 岛屿问题

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天前
|

17 3
|
1月前
|

[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
26 2
|
1月前
|

[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
21 2
|
1月前
|

23 3
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-2
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
30 2
|
1月前
|

【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题-1
【数据结构与算法】：关于时间复杂度与空间复杂度的计算（C/C++篇）——含Leetcode刷题
36 2
|
26天前
|

10 0
|
29天前
|

【数据结构与算法 经典例题】括号匹配问题
【数据结构与算法 经典例题】括号匹配问题
26 0
|
1月前
|

21 0
|
1月前
|

【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成
【经典LeetCode算法题目专栏分类】【第11期】递归问题：字母大小写全排列、括号生成
16 0