Voyz's Studio.

LeetCode算法笔记--岛屿数量

字数统计: 409阅读时长: 2 min
2021/03/18 Share

LeetCode算法笔记-Day74

200. 岛屿数量

给你一个由 ‘1’(陆地)和 ‘0’(水)组成的的二维网格,请你计算网格中岛屿的数量。

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
· 示例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

DFS

遇到岛屿时(grid[i][j] === ‘1’) 则岛屿数量+1 且 将相邻所有陆地变为0 直至遍历完整个网格

Answer:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
/**
* @param {character[][]} grid
* @return {number}
*/
var numIslands = function(grid) {
// 边界处理
if(grid.length == 0) return 0;

let row = grid.length,
column = grid[0].length,
len = grid.length,
res = 0;

const DFS = (grid,i,j) => {
// base case (递归终止条件)
if(i<0 || j< 0 || i>row-1 || j>column-1 || grid[i][j] == '0') return;

// 将其变成水域
grid[i][j] = '0';

// 上下左右
DFS(grid,i-1,j);
DFS(grid,i,j+1);
DFS(grid,i+1,j);
DFS(grid,i,j-1);
}

// 遍历整个网格
for(let r=0;r<row;r++){
for(c=0;c<column;c++){
if(grid[r][c] == '1'){
res += 1;
DFS(grid,r,c)
}
}
}

return res;

};
CATALOG
  1. 1. LeetCode算法笔记-Day74
    1. 1.1. 200. 岛屿数量
    2. 1.2. DFS
      1. 1.2.1. Answer: