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

文章目录

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

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

题目链接

一、DFS

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

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