代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙

文章目录

代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙17.太平洋大西洋水流问题一、DFS二、BFS三、本题总结

827.最大人工岛一、DFS 用全局变量得到area二、DFS 用局部变量三、BFS

127. 单词接龙一、BFS

17.太平洋大西洋水流问题

题目链接

一、DFS

<code>class Solution(object):

def pacificAtlantic(self, heights):

"""

:type heights: List[List[int]]

:rtype: List[List[int]]

"""

m,n=len(heights),len(heights[0])

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

pacific=[[0]*n for _ in range(m)]

atlantic=[[0]*n for _ in range(m)]

result=[]

# DFS

def dfs(x,y,ocean):

ocean[x][y]=1

for d in dirs:

nextx,nexty=x+d[0],y+d[1]

if 0 <= nextx < m and 0 <= nexty < n and heights[nextx][nexty] >=heights[x][y] and ocean[nextx][nexty]==0:

dfs(nextx,nexty,ocean)

for i in range(m):

dfs(i,0,pacific)

dfs(i,n-1,atlantic)

for j in range(n):

dfs(0,j,pacific)

dfs(m-1,j,atlantic)

for i in range(m):

for j in range(n):

if pacific[i][j]==1 and atlantic[i][j]==1:

result.append([i,j])

return result

二、BFS

class Solution(object):

def pacificAtlantic(self, heights):

"""

:type heights: List[List[int]]

:rtype: List[List[int]]

"""

m,n=len(heights),len(heights[0])

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

pacific=[[0]*n for _ in range(m)]

atlantic=[[0]*n for _ in range(m)]

result=[]

# BFS

def bfs(x,y,ocean):

q=collections.deque()

q.append((x,y))

ocean[x][y]=1

while q:

x,y = q.popleft()

for d in dirs:

nextx,nexty=x+d[0],y+d[1]

if 0 <= nextx < m and 0 <= nexty < n and heights[nextx][nexty] >=heights[x][y] and ocean[nextx][nexty]==0:

ocean[nextx][nexty]=1

q.append((nextx,nexty))

for i in range(m):

bfs(i,0,pacific)

bfs(i,n-1,atlantic)

for j in range(n):

bfs(0,j,pacific)

bfs(m-1,j,atlantic)

for i in range(m):

for j in range(n):

if pacific[i][j]==1 and atlantic[i][j]==1:

result.append([i,j])

return result

三、本题总结

用两个visited来表示

827.最大人工岛

题目链接

一、DFS 用全局变量得到area

class Solution(object):

def largestIsland(self, grid):

"""

:type grid: List[List[int]]

:rtype: int

"""

'''

总体思路

利用 DFS 计算出各个岛屿的面积，并标记每个 1（陆地格子）属于哪个岛。

遍历每个 0，统计其上下左右四个相邻格子所属岛屿的编号，去重后，累加这些岛的面积，更新答案的最大值。

'''

m,n = len(grid),len(grid[0])

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

area = collections.defaultdict(int) # 用于储存岛屿面积

def dfs(x,y,island_num): # 输入岛屿编号

grid[x][y]=island_num

area[island_num] += 1 # 更新岛屿面积

for d in dirs:

nextx,nexty=x+d[0],y+d[1]

if 0 <= nextx < m and 0 <= nexty < n and grid[nextx][nexty]==1:

grid[nextx][nexty]=island_num

dfs(nextx,nexty,island_num)

island_num = 1

for i in range(m):

for j in range(n):

if grid[i][j]==1: # 遇到新岛屿

island_num += 1 # 岛屿编号从2开始

dfs(i,j,island_num)

ans=0

for i in range(m):

for j in range(n):

s=set() # 去重

if grid[i][j]==0:

for d in dirs:

nexti,nextj=i+d[0],j+d[1]

if 0 <= nexti < m and 0 <= nextj < n and grid[nexti][nextj]!=0:

s.add(grid[nexti][nextj])

ans = max(ans,1+sum(area[idx] for idx in s))

return ans if ans else n*n # 如果最后 ans 仍然为 0，说明所有格子都是 1，返回 n^2

二、DFS 用局部变量

class Solution(object):

def largestIsland(self, grid):

"""

:type grid: List[List[int]]

:rtype: int

"""

'''

总体思路

利用 DFS 计算出各个岛屿的面积，并标记每个 1（陆地格子）属于哪个岛。

遍历每个 0，统计其上下左右四个相邻格子所属岛屿的编号，去重后，累加这些岛的面积，更新答案的最大值。

'''

m,n = len(grid),len(grid[0])

dirs = [(-1,0),(0,1),(1,0),(0,-1)]

area = collections.defaultdict(int) # 用于储存岛屿面积

def dfs(x,y,island_num): # 输入岛屿编号

grid[x][y]=island_num

size=1

# area[island_num] += 1 # 更新岛屿面积

for d in dirs:

nextx,nexty=x+d[0],y+d[1]

if 0 <= nextx < m and 0 <= nexty < n and grid[nextx][nexty]==1:

grid[nextx][nexty]=island_num

size += dfs(nextx,nexty,island_num)

return size # 得到岛屿的面积

island_num = 1

for i in range(m):

for j in range(n):

if grid[i][j]==1: # 遇到新岛屿

island_num += 1 # 岛屿编号从2开始

area[island_num]=dfs(i,j,island_num)

ans=0

for i in range(m):

for j in range(n):

s=set() # 去重

if grid[i][j]==0:

for d in dirs:

nexti,nextj=i+d[0],j+d[1]

if 0 <= nexti < m and 0 <= nextj < n and grid[nexti][nextj]!=0:

s.add(grid[nexti][nextj])

ans = max(ans,1+sum(area[idx] for idx in s))

return ans if ans else n*n # 如果最后 ans 仍然为 0，说明所有格子都是 1，返回 n^2

三、BFS

class Solution(object):

def largestIsland(self, grid):

"""

:type grid: List[List[int]]

:rtype: int

"""

'''

总体思路

利用 DFS 计算出各个岛屿的面积，并标记每个 1（陆地格子）属于哪个岛。

遍历每个 0，统计其上下左右四个相邻格子所属岛屿的编号，去重后，累加这些岛的面积，更新答案的最大值。

'''

# BFS

def bfs(x,y,island_num): # 输入岛屿编号

grid[x][y]=island_num

size=1

# area[island_num] += 1 # 更新岛屿面积

q=collections.deque()

q.append((x,y))

while q:

x,y=q.popleft()

for d in dirs:

nextx,nexty=x+d[0],y+d[1]

if 0 <= nextx < m and 0 <= nexty < n and grid[nextx][nexty]==1:

grid[nextx][nexty]=island_num

q.append((nextx,nexty))

size += 1

return size

island_num = 1

for i in range(m):

for j in range(n):

if grid[i][j]==1: # 遇到新岛屿

island_num += 1 # 岛屿编号从2开始

# dfs(i,j,island_num) # 法1

area[island_num]=bfs(i,j,island_num)

ans=0

for i in range(m):

for j in range(n):

s=set() # 去重

if grid[i][j]==0:

for d in dirs:

nexti,nextj=i+d[0],j+d[1]

if 0 <= nexti < m and 0 <= nextj < n and grid[nexti][nextj]!=0:

s.add(grid[nexti][nextj])

ans = max(ans,1+sum(area[idx] for idx in s))

return ans if ans else n*n # 如果最后 ans 仍然为 0，说明所有格子都是 1，返回 n^2

127. 单词接龙

题目链接

一、BFS

<code>class Solution(object):

def ladderLength(self, beginWord, endWord, wordList):

"""

:type beginWord: str

:type endWord: str

:type wordList: List[str]

:rtype: int

"""

wordset = set(wordList)

if len(wordList)==0 or endWord not in wordset :

return 0

q = collections.deque()

q.append(beginWord)

visited=set(beginWord)

step=1

while q:

level = len(q)

for l in range(level):

word = q.popleft()

word_list = list(word)

for i in range(len(word_list)):

origin_char=word_list[i]

for j in range(26):

word_list[i] = chr(ord('a')+j)

new_word = ''.join(word_list)

if new_word in wordset:

if new_word == endWord:

return step+1

if new_word not in visited:

q.append(new_word)

visited.add(new_word)

word_list[i]=origin_char

step +=1

return 0