200. 岛屿数量

leetcode

题目

image.png

思路一 DFS

遍历二维数组，遇到1，岛屿数量加一，同时要把岛屿自身以及上下左右沉默（置0），结束后回到岛屿自身继续遍历，如此往复直到数组结束。

复杂度

时间复杂度：O(MN)，MN分别为二维数组的长度。
空间复杂度：O(MN)，MN分别为二维数组的长度。递归中的调用帧保存。

编码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const numIslands = (grid) => {
  let count = 0
  for (let i = 0; i < grid.length; i++) {
    for (let j = 0; j < grid[i].length; j++) {
      if (grid[i][j] === '1') {
        count += 1
        turnZero(i, j, grid)
      }
    }
  }
  return count
}
function turnZero(i, j, grid) {
  if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length) return
  if (grid[i][j] === '0') return
  grid[i][j] = '0'
  turnZero(i - 1, j, grid)
  turnZero(i + 1, j, grid)
  turnZero(i, j - 1, grid)
  turnZero(i, j + 1, grid)
}