【经典LeetCode算法题目专栏分类】【第9期】深度优先搜索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