阅读量:0
代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙
文章目录
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 