admin 管理员组

文章数量: 887006

LeetCode 200. 岛屿数量

文章目录

      • 200. 岛屿数量
        • 题目
        • 解题思路
          • 方法一：深度优先搜索
          • 方法二：广度优先搜索
        • 代码实现
          • 方法一: 深度优先搜索 | 代码实现
          • 方法二: 广度优先搜索 | 代码实现
        • 实现结果
          • 方法一: 深度优先搜索 | 实现结果
          • 方法二: 广度优先搜索 | 实现结果

200. 岛屿数量

题目来源：/

题目

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。

岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。

此外，你可以假设该网格的四条边均被水包围。

示例 1:

输入:
11110
11010
11000
00000
输出: 1

示例 2:

输入:
11000
11000
00100
00011
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
解题思路
方法一：深度优先搜索

当要求出岛屿的数量时，我们可以扫描题目给出的二维网格。如果遍历的元素为 1，则以这个位置为起点进行深度优先搜索。

这里需要注意的是：深度优先搜索的过程中，已经搜索到的 1 要标记为 0，表示已经访问过。

那么进行深度优先搜索的次数就是要求的岛屿的数量。

详细部分见代码注释。

方法二：广度优先搜索

同样的，这道题也可以使用广度优先搜索进行替换解答。不过，这里需要增加一个辅助队列。

同样的，求岛屿的数量，先扫描遍历二维网格，如果遍历的位置元素为 1，要将其加入队列，同时标记为访问过，这里同样避免重复被加入队列中，导致代码运行超时。（如果遇到超时的情况，可检查队列中的变化是否有重复添加的现象。）直到队列为空时，搜索结束。

同样进行广度优先搜索的次数就是要求的岛屿数量。

文字表述比较繁琐难懂，可以结合代码了解思想。

具体的代码实现如下。

代码实现
方法一: 深度优先搜索 | 代码实现
class Solution:def numIslands(self, grid: List[List[str]]) -> int:m = len(grid)if m == 0:return 0n = len(grid[0])# 四个方位directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]def _dfs(grid, x, y):# 进行深度优化搜索，标记已访问grid[x][y] = '0'for dx, dy in directions:nx = x + dxny = y + dyif 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':_dfs(grid, nx, ny)ans = 0for x in range(m):for y in range(n):# 遍历，当为陆地时，进行深度优化搜索if grid[x][y] == '1':ans += 1_dfs(grid, x, y)return ans
方法二: 广度优先搜索 | 代码实现
class Solution:def numIslands(self, grid: List[List[str]]) -> int:from collections import dequem = len(grid)if m == 0:return 0n = len(grid[0])ans = 0directions = [(0, 1), (1, 0), (0, -1), (-1, 0)]for row in range(m):for col in range(n):# 扫描遍历，# 当为陆地，进行广度优化搜索if grid[row][col] == '1':ans += 1# 标记已经访问grid[row][col] = '0'# 创建辅助队列，同时防止重复搜索queue = deque([(row, col)])# 队列不为空的情况下，继续进行搜索while queue:x, y = queue.popleft()for dx, dy in directions:nx = x + dxny = y + dyif 0 <= nx < m and 0 <= ny < n and grid[nx][ny] == '1':# 入队列，防止重复queue.append((nx, ny))# 标记已访问grid[nx][ny] = '0'return ans
实现结果
方法一: 深度优先搜索 | 实现结果

方法二: 广度优先搜索 | 实现结果

以上就是使用深度优先搜索或广度优先搜索的思想，解决《200. 岛屿数量》问题的主要内容。主要需要注意的地方是：当已经搜索的地方，需要及时标记，避免重复搜索。

欢迎关注微信公众号《书所集录》

本文标签： LeetCode 200 岛屿数量

版权声明：本文标题：LeetCode 200. 岛屿数量 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1732352869h1533587.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。