当前位置： 移动技术网 > IT编程>脚本编程>Python > 【LeetCode】200. 岛屿数量（高频题！！！经典 DFS 和 BFS 高频题 商汤、字节面试题）

【LeetCode】200. 岛屿数量（高频题！！！经典 DFS 和 BFS 高频题 商汤、字节面试题）

2020年07月05日  | 移动技术网IT编程  | 我要评论

1. 题目描述

给你一个由 ‘1’（陆地）和 ‘0’（水）组成的的二维网格，请你计算网格中岛屿的数量。岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。此外，你可以假设该网格的四条边均被水包围。
示例 1:

输入:

[
['1','1','1','1','0'],
['1','1','0','1','0'],
['1','1','0','0','0'],
['0','0','0','0','0']
]
输出: 1
示例 2:

输入:
[
['1','1','0','0','0'],
['1','1','0','0','0'],
['0','0','1','0','0'],
['0','0','0','1','1']
]
输出: 3
解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。

2. 解题思路 & 代码

2.1. DFS 深度优先遍历

递归转化为迭代的话可以用栈，后进先出

  1. 我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。
  2. 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索。
  3. 在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0，这样可以避免两个 for 循环重复搜索。

最终岛屿的数量就是我们进行深度优先搜索的次数。

# 在开头加上
# import sys # python 默认递归深度不超过1000，做dfs会比C吃亏
# sys.setrecursionlimit(10000000)# 手动修改深度

class Solution:
    def dfs(self, grid, r, c):
        grid[r][c] = '0'   # 每次某个岛屿计数以后，把该岛屿所有 1 都归 0，这样两个 for 循环 就不会重复遍历了
        nr = len(grid)
        nc = len(grid[0])
        for new_r, new_c in [[r-1,c],[r+1,c],[r, c-1],[r, c+1]]:
            if 0 <= new_r < nr and 0 <= new_c <nc and grid[new_r][new_c] == '1':
                self.dfs(grid, new_r, new_c)
   
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid) # 行数
        if nr == 0:
            return 0
        nc = len(grid[0]) # 列数
        num_land = 0
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    num_land += 1
                    self.dfs(grid, r, c)
        
        return num_land

复杂度分析

时间复杂度：O(MN)O(MN)，其中 MM 和 NN 分别为行数和列数。

空间复杂度：O(MN)O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MNMN。

2.2. BFS 广度优先遍历

广度优先用队列，先进先出

同样地，我们也可以使用广度优先搜索代替深度优先搜索。

  1. 为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则将其加入队列，开始进行广度优先搜索。
  2. 在广度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0。直到队列为空，搜索结束。
  3. 最终岛屿的数量就是我们进行广度优先搜索的次数。
class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        nr = len(grid)
        if nr == 0:
            return 0
        nc = len(grid[0])
        num_land = 0
        queue = []              # 队列，可用列表表示
        for r in range(nr):
            for c in range(nc):
                if grid[r][c] == '1':
                    num_land += 1
                    queue.append([r, c])  # 入队
                    # grid[r][c] = '0'    # 这里标记已访问可有可无
                    while queue:
                        row, col = queue.pop(0)  #左边出队（先进先出）
                        for i, j in [[row-1, col],[row+1, col],[row, col-1],[row, col+1]]:
                            if 0 <= i < nr and  0 <= j < nc and grid[i][j] == '1':
                                queue.append([i, j])  # 入队
                                grid[i][j] = '0'      # 放入队列以后马上标记为已访问，即置零
        return num_land

复杂度分析

时间复杂度：O(MN)O(MN)，其中 MM 和 NN 分别为行数和列数。

空间复杂度：O(min(M,N))O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)min(M,N)。

参考：

  1. LeetCode题解.

本文地址：https://blog.csdn.net/weixin_41888257/article/details/107128917

您可能感兴趣的文章:

如对本文有疑问， 点击进行留言回复！！

相关文章:

验证码：
最近更新的文章
大家感兴趣的文章
移动技术网