[Leetcode] Number of Islands 岛屿数量（JavaScript 实现）

pingan8787 发布于2019-08-23 12:10 / 1706人阅读

摘要：解题思路标零法对这个矩阵进行循环访问每一个点当这个点等于，岛屿数量，与其同时用算法访问周围的其他点，进行同样的操作且将访问过且等于的点标记为零。版本岛屿数量搜索右边搜索左边搜索下边搜索上边

Q: Number of Islands

Given a 2d grid map of "1"s (land) and "0"s (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

Example 2:

Input:
11000
11000
00100
00011

Output: 3

解题思路

标零法

对这个矩阵进行循环访问每一个点；
当这个点等于 1，岛屿数量 count++，与其同时用 dfs 算法（depth first search）访问周围的其他点，进行同样的操作；
且将访问过且等于 1 的点标记为零。

Solutions （JavaScript 版本）

/**
 * @param {character[][]} grid
 * @return {number}
 */
var numIslands = function(grid) {
    var count = 0    // 岛屿数量
    if (grid.length === 0) return count
    for (var i = 0; i < grid.length; i++) {
        for(var j = 0; j < grid[0].length; j++) {
            if (grid[i][j] === "1") {
                dfsSearch(grid, i, j)
                count++
            }
        }
    }
    return count
};

function dfsSearch(grid, i, j) {
    if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length) return;
    if(grid[i][j] === "1"){
        grid[i][j] = "0";
        dfsSearch(grid, i + 1, j);    // 搜索右边
        dfsSearch(grid, i - 1, j);    // 搜索左边
        dfsSearch(grid, i, j + 1);    // 搜索下边
        dfsSearch(grid, i, j - 1);    // 搜索上边
    }
}

GPU云服务器云服务器 Islands LeetCode javascript实现 javascript实现动画

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/98029.html

[Leetcode] Number of Islands 岛屿个数

摘要：同时我们每找到一个，就将其标为，这样就能把整个岛屿变成。我们只要记录对矩阵遍历时能进入多少次搜索，就代表有多少个岛屿。 Number of Islands 最新更新的思路，以及题II的解法请访问：https://yanjia.me/zh/2018/11/... Given a 2d grid map of 1s (land) and 0s (water), count the nu...

Raaabbit 2019-08-14 12:32 评论0 收藏0
[LeetCode/LintCode] Number of Islands [DFS]

摘要：两个循环遍历整个矩阵，出现则将其周围相邻的全部标记为，用子函数递归标记。注意里每次递归都要判断边界。写一个的，写熟练。 Number of Islands Problem Given a boolean/char 2D matrix, find the number of islands. 0 is represented as the sea, 1 is represented as...

Fourierr 2019-08-14 15:15 评论0 收藏0
[LeetCode] 694. Number of Distinct Islands

Problem Given a non-empty 2D array grid of 0s and 1s, an island is a group of 1s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are s...

SunZhaopeng 2019-08-16 13:50 评论0 收藏0
leetcode200. Number of Islands

摘要：题目要求提供一个二维数组表示一张地图，其中代表陆地，代表海洋。这里使用一个新的二维数组来表示对应地图上的元素属于哪个并查集。在合并的时候先进行判断，如果二者为已经相连的陆地，则无需合并，否则将新的二维数组上的元素指向所在的并查集。题目要求 Given a 2d grid map of 1s (land) and 0s (water), count the number of isla...

Zoom 2019-08-16 10:45 评论0 收藏0
前端 | 每天一个 LeetCode

摘要：在线网站地址我的微信公众号完整题目列表从年月日起，每天更新一题，顺序从易到难，目前已更新个题。这是项目地址欢迎一起交流学习。这篇文章记录我练习的 LeetCode 题目，语言 JavaScript。在线网站：https://cattle.w3fun.com GitHub 地址：https://github.com/swpuLeo/ca...我的微信公众号： showImg(htt...

张汉庆 2019-08-23 13:42 评论0 收藏0