代码随想录算法训练营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=[] # DFSdef dfs(x,y,ocean):ocean[x][y]=1for 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=[] # BFSdef bfs(x,y,ocean):q=collections.deque()q.append((x,y))ocean[x][y]=1while 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]=1q.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_numdfs(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=0for 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_numsize += 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=0for 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，统计其上下左右四个相邻格子所属岛屿的编号，去重后，累加这些岛的面积，更新答案的最大值。'''# BFSdef 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_numq.append((nextx,nexty))size += 1return sizeisland_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) # 法1area[island_num]=bfs(i,j,island_num) ans=0for 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^2127. 单词接龙
题目链接
一、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 0q = collections.deque()q.append(beginWord)visited=set(beginWord)step=1while 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+1if new_word not in visited:q.append(new_word)visited.add(new_word)word_list[i]=origin_charstep +=1return 0
