岛屿数量

题目要求

你需要编写一个算法来统计一个二维网格中的岛屿数量。这个网格由字符 '1'（代表陆地）和 '0'（代表水）组成。一个岛屿由上下左右相连的 '1' 形成，并且假设网格的四周都被 '0' 包围，即网格的边界之外全是水。

解题思路

解决这个问题的一个有效方法是使用深度优先搜索（DFS）。以下是解题的步骤：

遍历网格中的每一个单元格。
当你遇到一个值为 '1' 的单元格时，将其视为岛屿的一部分。
从这个单元格开始，使用深度优先搜索遍历所有相邻的、值为 '1' 的单元格，并将它们标记为已访问，以避免重复计算。这可以通过将单元格的值从 '1' 改为 '0' 或者其他非 '1' 的值来实现。
继续步骤 1 和步骤 2，直到网格中的所有单元格都被访问过。
每次启动一个新的深度优先搜索时，岛屿的数量加一。

这种方法的关键在于，每次通过深度优先搜索将一个岛屿的所有部分都标记为已访问后，就可以确保不会重复计算岛屿的数量。当遍历完整个网格后，就可以得到岛屿的总数。

Golang 版本

func numIslands(grid [][]byte) int {
    if len(grid) == 0 || len(grid[0]) == 0 {
        return 0
    }

    islandCount := 0
    for i := 0; i < len(grid); i++ {
        for j := 0; j < len(grid[i]); j++ {
            if grid[i][j] == '1' {
                dfs(grid, i, j)
                islandCount++
            }
        }
    }

    return islandCount
}

func dfs(grid [][]byte, i, j int) {
    if i < 0 || j < 0 || i >= len(grid) || j >= len(grid[i]) || grid[i][j] == '0' {
        return
    }

    grid[i][j] = '0'
    dfs(grid, i+1, j)
    dfs(grid, i-1, j)
    dfs(grid, i, j+1)
    dfs(grid, i, j-1)
}

这段代码定义了一个名为numIslands的函数，它接受一个二维字节切片grid作为参数，并返回一个整数表示岛屿的数量。它还使用了一个辅助函数dfs来执行深度优先搜索并标记访问过的岛屿部分。在numIslands函数中，通过双层循环遍历网格中的每个单元格，当遇到值为'1'的单元格时，调用dfs函数，并将岛屿计数器加一。dfs函数负责将访问过的陆地部分标记为'0'，并递归地对上下左右的单元格进行相同的操作。

C++版本

#include <vector>

class Solution {
public:
    int numIslands(std::vector<std::vector<char>>& grid) {
        int islandCount = 0;
        for (int i = 0; i < grid.size(); ++i) {
            for (int j = 0; j < grid[i].size(); ++j) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    ++islandCount;
                }
            }
        }
        return islandCount;
    }

private:
    void dfs(std::vector<std::vector<char>>& grid, int i, int j) {
        if (i < 0 || i >= grid.size() || j < 0 || j >= grid[i].size() || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
};

这段 C++代码定义了一个名为Solution的类，其中包含了两个方法：numIslands和dfs。numIslands方法用于计算二维网格中岛屿的数量，它接受一个二维字符向量grid作为参数。dfs方法是一个私有辅助方法，用于执行深度优先搜索并将访问过的岛屿部分标记为'0'。在numIslands方法中，通过嵌套循环遍历网格中的每个单元格，当遇到值为'1'的单元格时，调用dfs方法，并将岛屿计数器加一。dfs方法递归地对相邻的单元格进行搜索，直到所有相连的陆地都被访问和标记。

Python 版本

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '0'
        self.dfs(grid, i + 1, j)
        self.dfs(grid, i - 1, j)
        self.dfs(grid, i, j + 1)
        self.dfs(grid, i, j - 1)

# Example usage:
# grid = [
#   ["1","1","1","0","0"],
#   ["1","1","0","0","0"],
#   ["0","0","1","0","0"],
#   ["0","0","0","1","1"]
# ]
# sol = Solution()
# print(sol.numIslands(grid))  # Output: 3

这段 Python 代码定义了一个名为Solution的类，其中包含了两个方法：numIslands和dfs。numIslands方法用于计算二维网格中岛屿的数量，它接受一个二维字符列表grid作为参数。dfs方法是一个辅助方法，用于执行深度优先搜索并将访问过的岛屿部分标记为'0'。在numIslands方法中，通过嵌套循环遍历网格中的每个单元格，当遇到值为'1'的单元格时，调用dfs方法，并将岛屿计数器加一。dfs方法递归地对相邻的单元格进行搜索，直到所有相连的陆地都被访问和标记。

Java 版本

public class Solution {
    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int numIslands = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[i].length; j++) {
                if (grid[i][j] == '1') {
                    dfs(grid, i, j);
                    numIslands++;
                }
            }
        }

        return numIslands;
    }

    private void dfs(char[][] grid, int i, int j) {
        if (i < 0 || i >= grid.length || j < 0 || j >= grid[i].length || grid[i][j] == '0') {
            return;
        }

        grid[i][j] = '0';
        dfs(grid, i + 1, j);
        dfs(grid, i - 1, j);
        dfs(grid, i, j + 1);
        dfs(grid, i, j - 1);
    }
}

这段 Java 代码定义了一个名为Solution的类，其中包含了两个方法：numIslands和dfs。numIslands方法用于计算二维字符数组中岛屿的数量。dfs方法是一个私有辅助方法，用于执行深度优先搜索并将访问过的岛屿部分标记为'0'。在numIslands方法中，通过嵌套循环遍历数组中的每个元素，当遇到值为'1'的元素时，调用dfs方法，并将岛屿计数器加一。dfs方法递归地对相邻的元素进行搜索，直到所有相连的陆地都被访问和标记。

Rust 版本

#![allow(unused)]
fn main() {
pub struct Solution;

impl Solution {
    pub fn num_islands(grid: Vec<Vec<char>>) -> i32 {
        let mut grid = grid;
        let mut count = 0;
        for i in 0..grid.len() {
            for j in 0..grid[i].len() {
                if grid[i][j] == '1' {
                    Self::dfs(&mut grid, i, j);
                    count += 1;
                }
            }
        }
        count
    }

    fn dfs(grid: &mut Vec<Vec<char>>, i: usize, j: usize) {
        if i >= grid.len() || j >= grid[i].len() || grid[i][j] == '0' {
            return;
        }
        grid[i][j] = '0';
        if i > 0 { Self::dfs(grid, i - 1, j); }
        if j > 0 { Self::dfs(grid, i, j - 1); }
        if i + 1 < grid.len() { Self::dfs(grid, i + 1, j); }
        if j + 1 < grid[i].len() { Self::dfs(grid, i, j + 1); }
    }
}

// Example usage:
// let grid = vec![
//     vec!['1', '1', '1', '0', '0'],
//     vec!['1', '1', '0', '0', '0'],
//     vec!['0', '0', '1', '0', '0'],
//     vec!['0', '0', '0', '1', '1'],
// ];
// println!("{}", Solution::num_islands(grid)); // Output: 3
}

这段 Rust 代码定义了一个名为Solution的结构体和两个关联函数：num_islands和dfs。num_islands函数用于计算二维字符向量中岛屿的数量。dfs函数是一个私有辅助函数，用于执行深度优先搜索并将访问过的岛屿部分标记为'0'。在num_islands函数中，通过嵌套循环遍历向量中的每个元素，当遇到值为'1'的元素时，调用dfs函数，并将岛屿计数器加一。dfs函数递归地对相邻的元素进行搜索，直到所有相连的陆地都被访问和标记。

总结

上述代码展示了如何在不同编程语言中实现岛屿数量的计算。核心算法是基于深度优先搜索（DFS）的。以下是算法的步骤总结：

遍历给定的二维网格。
当遇到一个值为'1'的单元格时，将其视为岛屿的一部分，并开始从该单元格进行深度优先搜索。
在 DFS 过程中，将访问过的'1'标记为'0'，以避免重复计算。
对当前单元格的上下左右四个方向进行递归搜索，直到所有相连的'1'都被访问并标记为'0'。
每完成一次 DFS，岛屿计数器加一。
继续遍历直到网格中的所有单元格都被检查过。
返回岛屿计数器的值，即为岛屿的总数。

这种方法的时间复杂度通常是 O(MN)，其中 M 是网格的行数，N 是网格的列数，因为它需要访问网格中的每个单元格。空间复杂度主要取决于递归调用栈的深度，最坏情况下可能达到 O(MN)。

在不同的编程语言中，尽管语法不同，但算法的核心逻辑保持一致。例如，在 Rust 中使用usize来索引向量，而在 Java 和 C++中则使用int类型。此外，Rust 的所有权和借用机制要求在递归调用时显式地传递可变引用。尽管这些细节上的差异存在，但整体算法框架和解决问题的思路是相同的。

hot-100