微网站建设图片,Wordpress右侧返回顶部按钮,wordpress google统计,房地产推广方案和推广思路本题中要求统计岛屿数量#xff08;数字1的上下左右均为1#xff0c;则是连续的1#xff0c;称为一块岛屿#xff09;。那么这种类型题都是需要依靠深度优先搜索#xff08;DFS#xff09;或者广度优先搜索#xff08;BFS#xff09;来做的。这两种搜索#xff0c;实际… 本题中要求统计岛屿数量数字1的上下左右均为1则是连续的1称为一块岛屿。那么这种类型题都是需要依靠深度优先搜索DFS或者广度优先搜索BFS来做的。这两种搜索实际上都是利用了递归和回溯递归三部曲
本题两种方法都可以这里采用dfs我们知道 首先要确定递归函数的参数这里我们需要将二维数组grid传入然后还需要传入一个点的横坐标i以及它的纵坐标j。因为我们只能通过坐标来定位。然后确定返回值通常返回值都是void。
然后确定终止条件当我们的点移动到边界上的时候就该停止了。也就是i0或者igrid.length或者j0或者jgrid[0].length(注意这里i是横坐标横坐标的最大也就是二维数组的大小。j是纵坐标j最大应该是在一行中也就是二维数组中的一个一维数组的长度但是不确定当前二维数组有几个一维数组所以选择grid[0].length)
然后确定单层递归的逻辑上述的终止条件一旦触发则直接return。然后其他情况我们首先要把遇到的这块土地上的数据置为0防止重复遇到。然后我们就可以判断这块坐标的上下左右都是不是1即是否符合题中要求这里就是递归
注意如何体现这个坐标点(i,j)的上下左右呢 上i-1j 下i1j 左ij-1 右ij1
在函数中之所以用两层for循环是为了遍历二维数组找寻数字为1的坐标因为题中并没有给出岛屿的坐标需要我们首先找到第一个然后再判断这个坐标旁边的点是否符合进而继续寻找岛屿
public int numIslands(char[][] grid) {int res 0; //记录找到的岛屿数量for(int i 0;i grid.length;i){for(int j 0;j grid[0].length;j){//找到“1”res加一同时淹没这个岛if(grid[i][j] 1){res;dfs(grid,i,j);}}}return res;
}
//使用DFS“淹没”岛屿
public void dfs(char[][] grid, int i, int j){//搜索边界索引越界或遍历到了0if(i 0 || i grid.length || j 0 || j grid[0].length || grid[i][j] 0) return;//将这块土地标记为0grid[i][j] 0;//根据每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成对上下左右的相邻顶点进行dfsdfs(grid,i - 1,j);dfs(grid,i 1,j);dfs(grid,i,j 1);dfs(grid,i,j - 1);
}
