LeetCode：200. Number of Islands（查找岛屿的个数）

布满荆棘的人生 2022-04-05 08:55 197阅读 0赞

> **文章最前**： 我是Octopus，这个名字来源于我的中文名--章鱼；我热爱编程、热爱算法、热爱开源。所有源码在我的个人[github][] ；这博客是记录我学习的点点滴滴，如果您对 Python、Java、AI、算法有兴趣，可以关注我的动态，一起学习，共同进步。

**相关文章：**

1.  **[LeetCode：55. Jump Game（跳远比赛）][LeetCode_55. Jump Game]**
2.  **[Leetcode：300. Longest Increasing Subsequence（最大增长序列）][Leetcode_300. Longest Increasing Subsequence]**
3.  **[LeetCode：560. Subarray Sum Equals K（找出数组中连续子串和等于k][LeetCode_560. Subarray Sum Equals K_k]）**

--------------------

**文章目录:**

题目描述：

深度优先搜索

java实现方法1：

python实现方式1:

源码github地址：

--------------------

### 题目描述： ###

给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。

示例 1:

输入:
    11110
    11010
    11000
    00000
    
    输出: 1

示例 2:

输入:
    11000
    11000
    00100
    00011
    
    输出: 3

来源：力扣（LeetCode）

--------------------

### 方法1：深度优先搜索 ###

我们可以将二维网格看成一个无向图，竖直或水平相邻的 1 之间有边相连。

为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 1，则以其为起始节点开始进行深度优先搜索，在深度优先搜索的过程中，每个搜索到的 1 都会被重新标记为 0，最终岛屿的数量就是我们进行深度优先搜索的次数。

下面的画展示了整个算法：

### ![format_png][]![format_png 1][] ###

### ![format_png 2][]![format_png 3][] ###

### ![format_png 4][]![format_png 5][] ###

### ![format_png 6][]![format_png 7][] ###

--------------------

### java实现方法： ###

/**
         * 计算岛屿的个数
         *
         * @param grid 二维数组
         * @return 岛屿个数
         */
        public int numIslands(char[][] grid) {
            if (grid.length == 0 || grid[0].length == 0) {
                return 0;
            }
            int res = 0;
            int row = grid.length;
            int col = grid[0].length;
            boolean[][] visited = new boolean[row][col];
            for (int i = 0; i < row; i++) {
                for (int j = 0; j < col; j++) {
                    if (grid[i][j] == '1' && !visited[i][j]) {
                        helper(grid, visited, i, j);
                        res++;
                    }
                }
            }
            return res;
        }
    
        /**
         * 递归每个元素
         *
         * @param grid    二维数组
         * @param visited 是否访问过
         * @param x       x坐标
         * @param y       y坐标
         */
        private void helper(char[][] grid, boolean[][] visited, int x, int y) {
            if (x < 0 || x >= grid.length) {
                return;
            }
            if (y < 0 || y >= grid[0].length) {
                return;
            }
            if (grid[x][y] != '1' || visited[x][y]) {
                return;
            }
            visited[x][y] = true;
            helper(grid, visited, x - 1, y);
            helper(grid, visited, x + 1, y);
            helper(grid, visited, x, y - 1);
            helper(grid, visited, x, y + 1);
        }

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

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

--------------------

### python实现方式: ###

from typing import List
    
    
    def num_islands(grid: List[List[str]]) -> int:
        '''
             计算岛屿个数
        Args:
            grid: 二维数组
        Returns:
            岛屿个数
    
        '''
        if len(grid) < 1 or len(grid[0]) < 1:
            return 0
        result = 0
        row, col = len(grid), len(grid[0])
        visited = [[False] * col for x in range(row)]
        for i in range(row):
            for j in range(col):
                if grid[i][j] == '1' and not visited[i][j]:
                    helper(grid, visited, i, j)
                    result += 1
        return result
    
    
    def helper(grid: List[List[int]], visited: List[List[int]], x: int, y: int) -> None:
        '''
            帮助类函数
        Args:
            grid: 二维数组
            visited: 访问数组
            x: 位置x
            y: 位置y
        '''
        if x < 0 or x >= len(grid):
            return
        if y < 0 or y >= len(grid[0]):
            return
        if grid[x][y] != '1' or visited[x][y]:
            return
        visited[x][y] = True
        helper(grid, visited, x - 1, y)
        helper(grid, visited, x + 1, y)
        helper(grid, visited, x, y - 1)
        helper(grid, visited, x, y + 1)

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

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

--------------------

### 源码github地址： ###

[https://github.com/zhangyu345293721/leetcode][https_github.com_zhangyu345293721_leetcode]

[github]: https://github.com/zhangyu345293721
[LeetCode_55. Jump Game]: https://blog.csdn.net/zy345293721/article/details/84991870
[Leetcode_300. Longest Increasing Subsequence]: https://blog.csdn.net/zy345293721/article/details/84984249
[LeetCode_560. Subarray Sum Equals K_k]: https://blog.csdn.net/zy345293721/article/details/84952201
[format_png]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzVkYWUwZGUyYTA2ZjRlYWU1MTEzZjljYWRmYTVjNTFiYmNmMGI5MzQ3YzU4NjFhYTczYzkzZDdiYzFkNTBiMzQtaW1hZ2UucG5n?x-oss-process=image/format,png
[format_png 1]: /images/20220405/0819d0d03d6b45efabae4da0e249593b.png
[format_png 2]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzZkMDYwZjI3NTU2MWRjMzkwODQxZjc4ZDg1MTI0ZmQxOTNlZmIwODAxZWEyZGM4NjViMjc2N2YxMDkzZTRmM2EtaW1hZ2UucG5n?x-oss-process=image/format,png
[format_png 3]: /images/20220405/872ca2b6b10d4a76a319247e0c6f2e2e.png
[format_png 4]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tL2JmMDU1YzNkNWY2YjMxMGY2YTExMGFkYTY1ZDUwM2RlNmQ3NzkzMjc2ZjU2Mzg3MzFjODFjNTNiNDI3NmI4MzUtaW1hZ2UucG5n?x-oss-process=image/format,png
[format_png 5]: /images/20220405/765b1848c3b34db19d0e084684c0dec1.png
[format_png 6]: https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tL2MyMWE4OGJkZTk0NTBhZDgzZDYxNjRjMmRmNDY3N2IxNjE1NGZhNTk5MDQwODQ1OWEyYTQ1OTgyYjljZDcwZmQtaW1hZ2UucG5n?x-oss-process=image/format,png
[format_png 7]: /images/20220405/b020c143de5140629021a36f493a6348.png
[https_github.com_zhangyu345293721_leetcode]: https://github.com/zhangyu345293721/leetcode