Voyz's Studio.

LeetCode算法笔记--岛屿数量

算法题 热题HOT100 DFS 岛屿问题
字数统计: 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：
Total : 137
2021
2020
2019
2018
技术贴 JavaScript Flutter 算法题 热题HOT100 哈希表 滑动窗口 回溯算法 链表 二分法 矩阵 动态规划 贪心算法 指针 快速排序 迭代 二叉树 数组 快慢指针 排序 背包问题 单调栈 栈 DFS 岛屿问题 React Native React 旅行记 效率工具 python 小程序 英语 生活 足球 算法 性能优化 ES6 TypeScript koa