【LeetCode with JavaScript】 200. Number of Islands

客官°小女子只卖身不卖艺 2022-05-24 08:42 115阅读 0赞

原题网址：[https://leetcode.com/problems/number-of-islands][https_leetcode.com_problems_number-of-islands]  
难度：Medium

#### 题目 ####

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"代表陆地，"0"代表海洋。

1.  首先定义一个函数 `clearIsland(x, y, grid)`，函数功能输入一个 (x, y) 坐标，将该点连着的陆地 “1”，全部清理为 “0”，实现思路类似二叉树的**深度优先遍历(Depth-First Traversa)**，对该点的上下左右方向依次进行递归查找，当超出边界或抵达海洋，则结束单次递归；
2.  对 Input 的二维数组进行遍历，对每个 “1”，调用一次 `clearIsland`，清空该点连着的陆地，并使岛屿数量加一。

实现代码如下：

/**
     * @param {character[][]} grid
     * @return {number}
     */
    var numIslands = function(grid) {
    	var num = 0;
    	for(var i = 0; i < grid.length; i++) {
    		for(var j = 0; j < grid[0].length; j++) {
    			if(grid[i][j] === "1") {
    				findIsland(i, j, grid);
    				num ++;
    			}
    		}
    	}
    	return num;
    }
    
    function findIsland(x, y, grid) {
    	if(x < 0 || y < 0 
    		|| x > grid.length - 1 || y > grid[x].length - 1
    		|| grid[x][y] === "0")
    		return;
    
    	grid[x][y] = "0";
    
    	findIsland(x - 1, y, grid);
    	findIsland(x, y - 1, grid);
    	findIsland(x + 1, y, grid);
    	findIsland(x, y + 1, grid);
    }

Your runtime beats 93.88 % of javascript submissions.  
运行时间：68ms，clear！

[https_leetcode.com_problems_number-of-islands]: https://leetcode.com/problems/number-of-islands