【深度优先搜索】力扣695:岛屿的最大面积
2022/4/4 23:19:08
本文主要是介绍【深度优先搜索】力扣695:岛屿的最大面积,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
给你一个大小为 m x n 的二进制矩阵 grid 。
岛屿 是由一些相邻的 1 (代表土地) 构成的组合,这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0(代表水)包围着。
岛屿的面积是岛上值为 1 的单元格的数目。
计算并返回 grid 中最大的岛屿面积。如果没有岛屿,则返回面积为 0 。
示例:
输入:grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出:6
解释:答案不应该是 11 ,因为岛屿只能包含水平或垂直这四个方向上的 1 。
- 深度优先搜索
- 我们想知道网格中每个连通形状的面积,然后取最大值。
- 如果我们在一个土地上,以 4 个方向探索与之相连的每一个土地(以及与这些土地相连的土地),那么探索过的土地总数将是该连通形状的面积。
- 为了确保每个土地访问不超过一次,我们每次经过一块土地时,将这块土地的值置为 0。这样我们就不会多次访问同一土地。
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: def dfs(grid, x, y): # 遇到边界或者遇到0了,就停止 if not 0 <= x < len(grid) or not 0 <= y < len(grid[0]) or not grid[x][y]: return # 统计过这个点了,就把它标记成0,下次就不会重复过来了 grid[x][y] = 0 # 用一个变量存当前面积 self.result += 1 # 上下左右继续遍历 dfs(grid, x, y + 1) dfs(grid, x - 1, y) dfs(grid, x, y - 1) dfs(grid, x + 1, y) # 全都找完了,输出最大面积 return self.result maximum = 0 # 找第一个陆地的开始 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 1: # 每个岛单独统计 self.result = 0 # 保留最大值,此时找过的岛全被标注为0了 maximum = max(maximum, dfs(grid, i, j)) return maximum 作者:yangyb25 链接:https://leetcode-cn.com/problems/max-area-of-island/solution/python-bfs-dfs-xiang-xi-zhu-shi-by-yangy-kh6i/
时间复杂度:O(R×C)。其中 R 是给定网格中的行数,C 是列数。我们访问每个网格最多一次。
空间复杂度:O(R×C),递归的深度最大可能是整个网格的大小,因此最大可能使用 O(R×C) 的栈空间。
- 深度优先搜索 + 栈
这种方法本质与方法1相同,区别是:
- 方法1通过函数的调用来表示接下来想要遍历哪些土地,让下一层函数来访问这些土地。而方法二把接下来想要遍历的土地放在栈里,然后在取出这些土地的时候访问它们。
- 访问每一片土地时,我们将对围绕它四个方向进行探索,找到还未访问的土地,加入到栈 stack 中;
- 另外,只要栈 stack 不为空,就说明我们还有土地待访问,那么就从栈中取出一个元素并访问。
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: ans = 0 for i, l in enumerate(grid): for j, n in enumerate(l): cur = 0 stack = [(i, j)] while stack: cur_i, cur_j = stack.pop() if cur_i < 0 or cur_j < 0 or cur_i == len(grid) or cur_j == len(grid[0]) or grid[cur_i][cur_j] != 1: continue cur += 1 grid[cur_i][cur_j] = 0 for di, dj in [[0, 1], [0, -1], [1, 0], [-1, 0]]: next_i, next_j = cur_i + di, cur_j + dj stack.append((next_i, next_j)) ans = max(ans, cur) return ans 作者:LeetCode-Solution 链接:https://leetcode-cn.com/problems/max-area-of-island/solution/dao-yu-de-zui-da-mian-ji-by-leetcode-solution/
时间复杂度:O(R×C)。其中 R 是给定网格中的行数,C 是列数。我们访问每个网格最多一次。
空间复杂度:O(R×C)。栈中最多会存放所有的土地,土地的数量最多为 R×C 块,因此使用的空间为O(R×C)。
- 广度优先搜索
把方法2中的栈改为队列,每次从队首取出土地,并将接下来想要遍历的土地放在队尾,就实现了广度优先搜索算法。
class Solution: def maxAreaOfIsland(self, grid: List[List[int]]) -> int: def bfs(grid, x, y): # 第一个点加入队列 queue = [[x, y]] # 只要队列里面有东西就继续 while queue: # 考虑当前最先进去的点 [x, y] = queue.pop(0) # 满足条件不超界,不是0 if 0 <= x < len(grid) and 0 <= y < len(grid[0]) and grid[x][y]: # 标记已经遍历过的 grid[x][y] = 0 # 记录当前面积 self.result += 1 ''' bfs,下一次优先考虑每个点扩散开的. 此处可能会加入不满足条件的点,但是这些在下一轮不会被考虑 ''' queue += [[x - 1, y], [x, y - 1], [x + 1, y], [x, y + 1]] return self.result maximum = 0 # 找第一个陆地的开始 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == 1: # 每个岛单独统计 self.result = 0 # 保留最大值,此时找过的岛全被标注为0了 maximum = max(maximum, bfs(grid, i, j)) return maximum 作者:yangyb25 链接:https://leetcode-cn.com/problems/max-area-of-island/solution/python-bfs-dfs-xiang-xi-zhu-shi-by-yangy-kh6i/
时间复杂度:O(R×C)。其中 R 是给定网格中的行数,C 是列数。我们访问每个网格最多一次。
空间复杂度:O(R×C),队列中最多会存放所有的土地,土地的数量最多为 R×C 块,因此使用的空间为 O(R×C)。
一套模板,解决五个岛屿问题
这篇关于【深度优先搜索】力扣695:岛屿的最大面积的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?