河北提供网站制作公司哪家好,wordpress 批量文章,西安市未央区最新消息,wordpress主题域名怎么修改695. 岛屿的最大面积
先上最经典的题目#xff0c;详细思路看这题的官方题解#xff0c;简单来说的岛屿问题就是遍历二维数组#xff0c;一般都是从一块陆地开始#xff0c;进行深度优先或者广度优先搜索#xff0c;每次上下左右四个方向选其一然后寻找下一块陆地#x…695. 岛屿的最大面积
先上最经典的题目详细思路看这题的官方题解简单来说的岛屿问题就是遍历二维数组一般都是从一块陆地开始进行深度优先或者广度优先搜索每次上下左右四个方向选其一然后寻找下一块陆地最后找到一整个岛屿一片陆地。
广度优先搜索
class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:queue collections.deque([(r, c)]) # 队列grid[r][c] 2cur 1while queue:row, col queue.popleft() # 先进先出for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:cur 1queue.append((x, y))grid[x][y] 2ans max(ans, cur)return ansnr是行的长度nc是列的长度遍历整个二维数组如果遇到陆地if grid[r][c] 1就开始找岛屿。广度优先搜索用的是队列记录的是二维坐标。grid[r][c] 2的目的是防止重复遍历。cur是当前岛屿的面积。从一块陆地出发如果它的四个方向[(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]的下一个坐标x, y在范围内并且为陆地的话就把它加入队列中同时标记已遍历cur也加1。ans记录最大的岛屿面积。
深度优先搜索
class Solution:def maxAreaOfIsland(self, grid: List[List[int]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:stack [(r, c)] # 栈grid[r][c] 2cur 1while stack:row, col stack.pop() # 先进后出for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:cur 1stack.append((x, y))grid[x][y] 2ans max(ans, cur)return ans深度优先搜索和广度优先搜索基本一样只是改用栈来实现每次弹出的位置就是刚刚加入的即一条路走到底再往回走深度广度优先则按顺序弹出一定把最初的位置遍历完之后再遍历新的如同石头落入水中产生涟漪广度。
广度优先与深度优先切换只需要改一条初始化语句一个pop函数几个变量名就行了。
200. 岛屿数量
广度优先搜索
class Solution:def numIslands(self, grid: List[List[str]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:queue collections.deque([(r, c)])grid[r][c] 2ans 1while queue:row, col queue.popleft()for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:queue.append((x, y))grid[x][y] 2return ans深度优先搜索
class Solution:def numIslands(self, grid: List[List[str]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:stack [(r, c)]grid[r][c] 2ans 1while stack:row, col stack.pop()for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:stack.append((x, y))grid[x][y] 2return ans代码框架基本相同区别这题的数字用字符来表示是“1”而不是1不需要记录当前岛屿的面积只需要在进入一块新陆地找岛屿时ans加1即可实际上比上一题简单。
694. 不同岛屿的数量
广度优先搜索
class Solution:def numDistinctIslands(self, grid: List[List[int]]) - int:ans set()nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:queue collections.deque([(r, c)])grid[r][c] 2path awhile queue:row, col queue.popleft()nxt [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]for i in range(4): # 为了记录方向x, y nxt[i]if 0 x nr and 0 y nc and grid[x][y] 1:path str(i)queue.append((x, y))grid[x][y] 2path aans.add(path)return len(ans)深度优先搜索
class Solution:def numDistinctIslands(self, grid: List[List[int]]) - int:ans set()nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:stack [(r, c)]grid[r][c] 2path awhile stack:row, col stack.pop()nxt [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]for i in range(4): # 为了记录方向x, y nxt[i]if 0 x nr and 0 y nc and grid[x][y] 1:path str(i)stack.append((x, y))grid[x][y] 2path aans.add(path)return len(ans)这题找的是不同岛屿的数量如何定义岛屿是否相同模式呢题目说明两个岛屿被认为是相同的当且仅当一个岛屿可以通过平移变换不可以旋转、翻转和另一个岛屿重合。由于我们找陆地时是从左上向右下找的所以进入某种形状岛屿的位置是确定的因此可以用探索岛屿的路径方向组合来表示这个岛屿类似动作游戏的上下左右组合技能。
具体方法就是用字符串记录这个方向的组合同时要避免不同形状的岛屿出现相同路径的情况在每次遍历时加入标记 path a保证路径的唯一性。
463. 岛屿的周长
广度优先搜索
class Solution:def islandPerimeter(self, grid: List[List[int]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:stack [(r, c)]grid[r][c] 2while stack:row, col stack.pop()for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if (x 0 or x nr or y 0 or y nc) or (0 x nr and 0 y nc and grid[x][y] 0):ans 1if 0 x nr and 0 y nc and grid[x][y] 1:stack.append((x, y))grid[x][y] 2return ans深度优先搜索
class Solution:def islandPerimeter(self, grid: List[List[int]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])for r in range(nr):for c in range(nc):if grid[r][c] 1:stack [(r, c)]grid[r][c] 2while stack:row, col stack.pop()for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if (x 0 or x nr or y 0 or y nc) or (0 x nr and 0 y nc and grid[x][y] 0):ans 1if 0 x nr and 0 y nc and grid[x][y] 1:stack.append((x, y))grid[x][y] 2return ans本题中只有一个岛屿注意周长即岛屿的边界只会出现在陆地与大边界或者海洋的交界处即指向四个方向的下一个坐标xy有 if (x 0 or x nr or y 0 or y nc) or (0 x nr and 0 y nc and grid[x][y] 0):越界或者是海洋。
827. 最大人工岛
广度优先搜索
class Solution:def largestIsland(self, grid: List[List[int]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])area {}index 2for r in range(nr):for c in range(nc):if grid[r][c] 1:queue collections.deque([(r, c)]) # 队列grid[r][c] indexcur 1while queue:row, col queue.popleft() # 先进先出for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:cur 1queue.append((x, y))grid[x][y] indexarea[index] curindex 1ans max(area.values() or [0])for r in range(nr):for c in range(nc):if grid[r][c] 0:seen set()for x, y in [(r - 1, c), (r 1, c), (r, c - 1), (r, c 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:seen.add(grid[x][y])ans max(ans, 1 sum(area[i] for i in seen))return ans深度优先搜索
class Solution:def largestIsland(self, grid: List[List[int]]) - int:ans 0nr len(grid)if nr 0:return 0nc len(grid[0])area {}index 2for r in range(nr):for c in range(nc):if grid[r][c] 1:stack [(r, c)] # 队列grid[r][c] indexcur 1while stack:row, col stack.pop() # 先进先出for x, y in [(row - 1, col), (row 1, col), (row, col - 1), (row, col 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:cur 1stack.append((x, y))grid[x][y] indexarea[index] curindex 1ans max(area.values() or [0]) # 防止全1的情况for r in range(nr):for c in range(nc):if grid[r][c] 0:seen set()for x, y in [(r - 1, c), (r 1, c), (r, c - 1), (r, c 1)]:if 0 x nr and 0 y nc and grid[x][y] 1:seen.add(grid[x][y])ans max(ans, 1 sum(area[i] for i in seen))return ans一道困难题基本思路是将现有的岛屿遍历一次用字典标记不同的岛屿和岛屿面积然后再遍历所有的海洋格子填充该格子后的大岛屿面积就是这个格子四个方向的任两个岛屿面积之和加1找出最大值即可。
1034. 边界着色
递归法
class Solution:def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) - List[List[int]]:m, n len(grid), len(grid[0])explored set()def dfs(r, c):# 当前是遍历过的连通分量if (r, c) in explored:return False# 当前越界了说明上一次的在网格的边界上if r 0 or c 0 or r m or c n:return True# 当前不是连通分量说明上一次的与不在分量中的网格相邻if grid[r][c] ! grid[row][col]:return True# 当前的是范围内的没遍历过的连通分量explored.add((r,c))isBorder Falsefor dx, dy in (0,1),(1,0),(0,-1),(-1,0):if dfs(rdx, cdy):isBorder Trueif isBorder:grid[r][c] colorreturn Falsedfs(row, col)return grid迭代法
class Solution:def colorBorder(self, grid: List[List[int]], row: int, col: int, color: int) - List[List[int]]:m, n len(grid), len(grid[0])explored set()original_color grid[row][col]stack [(row, col)]while stack:r, c stack.pop()explored.add((r,c))for dx, dy in (0,1),(1,0),(0,-1),(-1,0):# 下一步越界了说明(r,c)在网格的边界上if rdx 0 or cdy 0 or rdx m or cdy n:grid[r][c] color# 遍历过的连通分量跳过elif (rdx, cdy) in explored:continue# 下一步不是连通分量说明(r,c)与不在分量中的网格相邻elif grid[rdx][cdy] ! original_color:grid[r][c] colorelse:stack.append((rdx, cdy))return grid这题指定了遍历的起点 (row, col)所以迭代法实现中就不能用 for 循环而要用 while 循环。从起点出发记录下遍历过的节点然后考察其四个方向的下一个节点如果下一个的节点越界了说明当前节点在边界上则需要着色如果下一个节点是遍历过的连通分量则跳过如果下一个节点不是连通分量则需要着色剩下的情况就是下一个节点是在边界内的、为遍历过的连通分量则加入栈。
1765. 地图中的最高点
class Solution:def highestPeak(self, isWater: List[List[int]]) - List[List[int]]:m, n len(isWater), len(isWater[0])ans [[water-1 for water in row] for row in isWater]q collections.deque((i, j) for i, row in enumerate(isWater) for j, _ in enumerate(row) if ans[i][j] 0)while q:i, j q.popleft()for x, y in ((i1, j), (i-1, j), (i, j1), (i, j-1)):if 0 x m and 0 y n and ans[x][y] -1:ans[x][y] ans[i][j] 1q.append((x, y))return ans广度优先遍历先把所有的 water 方格坐标加入队列作为起始点然后遍历它们上下左右的格子如果是还没被遍历过的就在 ans 中高度加 1 并且加入队列直到没有格子为止。
