给你一个由 '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'
思路:
- 初始化计数器:使用变量 count 来存储岛屿的数量。
- 遍历网格:使用两层嵌套循环遍历整个网格。
- 寻找陆地:在遍历过程中,如果发现陆地(即值为 '1' 的单元格),则增加计数器 count。
- 深度优先搜索(DFS):对于每个发现的陆地,使用 turnZero 函数进行深度优先搜索,将其以及所有相邻的陆地(上、下、左、右)都标记为水(即将值改为 '0')。
- 返回结果:遍历完成后,返回计数器 count 的值,即为岛屿的总数。
时间复杂度:O(m _ n),其中 m 和 n 分别是网格的行数和列数。在最坏的情况下,需要遍历整个网格中的每个单元格。 空间复杂度:O(m _ n),在最坏的情况下,递归栈的深度可以达到网格中所有单元格的数量,即岛屿的最大数量。
const numIslands = (grid) => {
let count = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[0].length; j++) {
//循环网格
if (grid[i][j] === '1') {
//如果为陆地,count++,
count++;
turnZero(i, j, grid);
}
}
}
return count;
};
function turnZero(i, j, grid) {
//沉没四周的陆地
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === '0') return;
//检查坐标的合法性
grid[i][j] = '0';
//让四周的陆地变为海水
turnZero(i, j + 1, grid);
turnZero(i, j - 1, grid);
turnZero(i + 1, j, grid);
turnZero(i - 1, j, grid);
}