当前位置：首页 > article >正文

LeetCode岛屿数量

article 2024/12/27 0:28:51

题目描述

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

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

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

示例 1：

输入：

grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]

输出：1

示例 2：

输入：

grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]

输出：3

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 300
grid[i][j] 的值为 '0' 或 '1'

解题思路

岛屿问题是网格 DFS 问题的典型代表，我们所熟悉的 DFS（深度优先搜索）问题通常是在树或者图结构上进行的。而岛屿 DFS 问题，是在一种「网格」结构中进行的。

我们首先明确一下岛屿问题中的网格结构是如何定义的，以方便我们后面的讨论。

网格问题是由 m×n 个小方格组成一个网格，每个小方格与其上下左右四个方格认为是相邻的，要在这样的网格上进行某种搜索。

岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子，数字为 1 的格子看成陆地格子，这样相邻的陆地格子就连接成一个岛屿。
在这里插入图片描述

网格结构中的格子有多少相邻结点？答案是上下左右四个。对于格子 (r, c) 来说（r 和 c 分别代表行坐标和列坐标），四个相邻的格子分别是 (r-1, c)、(r+1, c)、(r, c-1)、(r, c+1)。换句话说，网格结构是「四叉」的。
在这里插入图片描述

代码

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    //深度优先
    let count = 0;
    let m = grid.length;
    let n = grid[0].length;
    const dfs = (i, j) => {
        if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return;//下标越界或不是陆地，返回
        grid[i][j] = '0';//将陆地置为水，避免后续访问重复计算这个位置
        //检验它的上下左右方向有没有陆地
        dfs(i + 1, j);
        dfs(i - 1, j);
        dfs(i, j + 1);
        dfs(i, j - 1);
    }
    for(let i = 0; i < m; i++) {
        for(let j = 0; j < n; j++) {
            if(grid[i][j] === '1') {//找到陆地
                dfs(i, j);//找到这个陆地所属的一整块岛屿，整个岛屿原本的的'1'都被置为'0'
                count++;//岛屿数量增加
            }
        }
    }
    return count;
};

代码分析

var numIslands = function(grid) {
定义了一个名为 numIslands 的函数，它接受一个二维数组 grid 作为参数。
let count = 0;
声明一个变量 count 用来计数岛屿的数量，初始值为 0。
let m = grid.length;
获取网格的行数。
let n = grid[0].length;
获取网格的列数。
const dfs = (i, j) => {
定义一个名为 dfs 的函数，它接受两个参数 i 和 j，分别代表当前要访问的网格的行和列的索引。
if(i < 0 || j < 0 || i >= m || j >= n || grid[i][j] === '0') return;
这是一个边界检查，确保不会访问网格外的元素，并且只有当当前位置是陆地（即 grid[i][j] 的值为 ‘1’）时，才会继续执行。
grid[i][j] = '0';
将当前位置标记为已访问，通过将其值改为 '0'。
dfs(i + 1, j);
递归调用 dfs 函数，检查当前位置的下方是否有陆地。
dfs(i - 1, j);
递归调用 dfs 函数，检查当前位置的上方是否有陆地。
dfs(i, j + 1);
递归调用 dfs 函数，检查当前位置的右侧是否有陆地。
dfs(i, j - 1);
递归调用 dfs 函数，检查当前位置的左侧是否有陆地。
for(let i = 0; i < m; i++) {
开始一个外层循环，遍历每一行。
for(let j = 0; j < n; j++) {
开始一个内层循环，遍历每一列。
if(grid[i][j] === '1') {
检查当前位置是否是陆地。
dfs(i, j);
如果是陆地，调用 dfs 函数，从这个位置开始进行深度优先搜索，将整个岛屿标记为已访问。

这里每一块陆地通过这个函数都会变为海洋，不会影响其他陆地的搜索，下面直接统计数量

count++;
每找到一个岛屿，岛屿计数器 count 增加 1。
return count;
返回岛屿的总数。

这段代码的总体思路是使用深度优先搜索（DFS）来遍历整个网格。对于每个未被访问的陆地单元格，它都会递归地标记所有相邻的陆地单元格，直到没有更多的陆地可以访问。每完成一次这样的搜索，就意味着找到了一个岛屿，因此增加岛屿的计数。这个过程会一直重复，直到所有的陆地都被访问过。最后，函数返回找到的岛屿总数。

查看全文

http://www.kler.cn/a/354916.html