网站建设问题及解决办法,网站手机站怎么做,常德投诉网站,网站建设公司人员工资题目描述
给你一个由 1#xff08;陆地#xff09;和 0#xff08;水#xff09;组成的的二维网格#xff0c;请你计算网格中岛屿的数量。
岛屿总是被水包围#xff0c;并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外#xff0c;你可以假设该网…题目描述
给你一个由 1陆地和 0水组成的的二维网格请你计算网格中岛屿的数量。
岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外你可以假设该网格的四条边均被水包围。
示例 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
提示
m grid.lengthn grid[i].length1 m, n 300grid[i][j] 的值为 0 或 1
解题思路
岛屿问题是网格 DFS 问题的典型代表我们所熟悉的 DFS深度优先搜索问题通常是在树或者图结构上进行的。而岛屿 DFS 问题是在一种「网格」结构中进行的。
我们首先明确一下岛屿问题中的网格结构是如何定义的以方便我们后面的讨论。
网格问题是由 m×n 个小方格组成一个网格每个小方格与其上下左右四个方格认为是相邻的要在这样的网格上进行某种搜索。
岛屿问题是一类典型的网格问题。每个格子中的数字可能是 0 或者 1。我们把数字为 0 的格子看成海洋格子数字为 1 的格子看成陆地格子这样相邻的陆地格子就连接成一个岛屿。
网格结构中的格子有多少相邻结点答案是上下左右四个。对于格子 (r, c) 来说r 和 c 分别代表行坐标和列坐标四个相邻的格子分别是 (r-1, c)、(r1, c)、(r, c-1)、(r, c1)。换句话说网格结构是「四叉」的。
代码
/*** param {character[][]} grid* return {number}*/
var numIslands function(grid) {//深度优先let count 0;let m grid.length;let n grid[0].length;const dfs (i, j) {if(i 0 || j 0 || i m || j n || grid[i][j] 0) return;//下标越界或不是陆地返回grid[i][j] 0;//将陆地置为水避免后续访问重复计算这个位置//检验它的上下左右方向有没有陆地dfs(i 1, j);dfs(i - 1, j);dfs(i, j 1);dfs(i, j - 1);}for(let i 0; i m; i) {for(let j 0; j n; j) {if(grid[i][j] 1) {//找到陆地dfs(i, j);//找到这个陆地所属的一整块岛屿整个岛屿原本的的1都被置为0count;//岛屿数量增加}}}return count;
};代码分析 var numIslands function(grid) { 定义了一个名为 numIslands 的函数它接受一个二维数组 grid 作为参数。 let count 0; 声明一个变量 count 用来计数岛屿的数量初始值为 0。 let m grid.length; 获取网格的行数。 let n grid[0].length; 获取网格的列数。 const dfs (i, j) { 定义一个名为 dfs 的函数它接受两个参数 i 和 j分别代表当前要访问的网格的行和列的索引。 if(i 0 || j 0 || i m || j n || grid[i][j] 0) return; 这是一个边界检查确保不会访问网格外的元素并且只有当当前位置是陆地即 grid[i][j] 的值为 ‘1’时才会继续执行。 grid[i][j] 0; 将当前位置标记为已访问通过将其值改为 0。 dfs(i 1, j); 递归调用 dfs 函数检查当前位置的下方是否有陆地。 dfs(i - 1, j); 递归调用 dfs 函数检查当前位置的上方是否有陆地。 dfs(i, j 1); 递归调用 dfs 函数检查当前位置的右侧是否有陆地。 dfs(i, j - 1); 递归调用 dfs 函数检查当前位置的左侧是否有陆地。 for(let i 0; i m; i) { 开始一个外层循环遍历每一行。 for(let j 0; j n; j) { 开始一个内层循环遍历每一列。 if(grid[i][j] 1) { 检查当前位置是否是陆地。 dfs(i, j); 如果是陆地调用 dfs 函数从这个位置开始进行深度优先搜索将整个岛屿标记为已访问。 这里每一块陆地通过这个函数都会变为海洋不会影响其他陆地的搜索下面直接统计数量 count; 每找到一个岛屿岛屿计数器 count 增加 1。 return count; 返回岛屿的总数。
这段代码的总体思路是使用深度优先搜索DFS来遍历整个网格。对于每个未被访问的陆地单元格它都会递归地标记所有相邻的陆地单元格直到没有更多的陆地可以访问。每完成一次这样的搜索就意味着找到了一个岛屿因此增加岛屿的计数。这个过程会一直重复直到所有的陆地都被访问过。最后函数返回找到的岛屿总数。
