团购做的好的网站,情感式软文广告,传奇网页游戏开服,网络营销服务代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙 文章目录 代码随想录算法训练营Day 63| 图论 part03 | 417.太平洋大西洋水流问题、827.最大人工岛、127. 单词接龙17.太平洋大西洋水流问题一、DFS二、BFS三、本题总结 82…代码随想录算法训练营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,nlen(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,nextyxd[0],yd[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,nlen(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):qcollections.deque()q.append((x,y))ocean[x][y]1while q:x,y q.popleft()for d in dirs:nextx,nextyxd[0],yd[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,nextyxd[0],yd[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) ans0for i in range(m):for j in range(n):sset() # 去重if grid[i][j]0:for d in dirs:nexti,nextjid[0],jd[1]if 0 nexti m and 0 nextj n and grid[nexti][nextj]!0:s.add(grid[nexti][nextj])ans max(ans,1sum(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 size1# area[island_num] 1 # 更新岛屿面积for d in dirs:nextx,nextyxd[0],yd[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) ans0for i in range(m):for j in range(n):sset() # 去重if grid[i][j]0:for d in dirs:nexti,nextjid[0],jd[1]if 0 nexti m and 0 nextj n and grid[nexti][nextj]!0:s.add(grid[nexti][nextj])ans max(ans,1sum(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 size1# area[island_num] 1 # 更新岛屿面积qcollections.deque()q.append((x,y))while q:x,yq.popleft()for d in dirs:nextx,nextyxd[0],yd[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) ans0for i in range(m):for j in range(n):sset() # 去重if grid[i][j]0:for d in dirs:nexti,nextjid[0],jd[1]if 0 nexti m and 0 nextj n and grid[nexti][nextj]!0:s.add(grid[nexti][nextj])ans max(ans,1sum(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: intwordset set(wordList)if len(wordList)0 or endWord not in wordset :return 0q collections.deque()q.append(beginWord)visitedset(beginWord)step1while q:level len(q)for l in range(level):word q.popleft()word_list list(word)for i in range(len(word_list)):origin_charword_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 step1if new_word not in visited:q.append(new_word)visited.add(new_word)word_list[i]origin_charstep 1return 0
