岛屿题库
岛屿数量
给你一个由 '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
方案A 深度优先遍历-递归
:::details 点击查看代码
function dfs(grid,r,c){
let nr=grid.length;
let nc=grid[0].length;
if(r<0||c<0||r>=nr||c>=nc||grid[r][c]=='0'){
return
}
grid[r][c]='0';
dfs(grid,r-1,c);
dfs(grid,r+1,c);
dfs(grid,r,c-1);
dfs(grid,r,c+1);
}
function numIslands(grid){
if(!grid||!grid.length){
return 0;
}
let nr=grid.length;
let nc=grid[0].length;
let num_islands=0;
for(let r=0;r<nr;r++){
for(let c=0;c<nc;c++){
if(grid[r][c]=='1'){
num_islands++;
dfs(grid,r,c);
}
}
}
return num_islands;
}
:::
性能分析:
-
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
-
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。
方案B 深度优先遍历-迭代
:::details 点击查看代码
function numsIslands(grid){
let flag=new Array(grid.length).fill(0).map(value=>new Array(grid[0].length).fill(0));
let result=0;
let stack=[];
for(let i=0;i<grid.length;i++){
for(let j=0;j<grid[i].length;j++){
if(grid[i][j]=='1'&&flag[i][j]==false){
stack.push(i+'/'+j);
while(stack.length){
let strs=stack.pop().split('/');
let tempi=Number(strs[0]);
let tempj=Number(strs[1]);
flag[tempi][tempj]=true;
if((tempj-1)>=0&&(grid[tempi][tempj-1]=='1')&&(flag[tempi][tempj-1]==false)){
stack.push(tempi+'/'+(tempj-1));
}
if(((tempj+1)<grid[0].length)&&(grid[tempi][tempj+1]=='1')&&(flag[tempi][tempj+1]==false)){
stack.push(tempi+'/'+(tempj+1));
}
if((tempi-1)>=0&&(grid[tempi-1][tempj]=='1')&&(flag[tempi-1][tempj]==false)){
stack.push((tempi-1)+'/'+tempj);
}
if((tempi+1)<grid.length&&(grid[tempi+1][tempj]=='1')&&(flag[tempi+1][tempj])==false){
stack.push((tempi+1)+'/'+tempj);
}
}
result++;
}
}
}
return result;
}
:::
性能分析:
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(MN)，在最坏情况下，整个网格均为陆地，深度优先搜索的深度达到 MN。
方案C 广度优先遍历
思路:为了求出岛屿的数量，我们可以扫描整个二维网格。如果一个位置为 11，则将其加入队列，开始进行广度优先搜索。在广度优先搜索的过程中，每个搜索到的 11 都会被重新标记为 00。直到队列为空，搜索结束。最终岛屿的数量就是我们进行广度优先搜索的次数。
:::details 点击查看代码
function 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'){
bfs(grid,i,j);
count++;
}
}
}
return count;
}
function bfs(grid,i,j){
let queue=[];
queue.push([i,j]);
while(queue.length){
let current=queue.shift();
i=current[0];
j=current[1];
if(i>=0&&i<grid.length&&j>=0&&j<grid[0].length&&grid[i][j]=='1'){
grid[i][j]='0';
queue.push([i+1,j]);
queue.push([i-1,j]);
queue.push([i,j+1]);
queue.push([i,j-1]);
}
}
}
:::
性能分析:
时间复杂度：O(MN)，其中 M 和 N 分别为行数和列数。
空间复杂度：O(min(M,N))，在最坏情况下，整个网格均为陆地，队列的大小可以达到 min(M,N)。