网站架构功能模块及描述,国外10条新闻简短,php成品网站下载,宁波产品网站设计模板岛屿数量
给你一个由 ‘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
解题思路
1、使用深度优先搜索DFS来遍历二维网格找到所有岛屿。(PS: 深度优先搜索DFS一般是使用递归来实现)2、对于每个遍历到的陆地‘1’开始进行搜索将其与相邻的陆地标记为已访问过直到将整个岛屿搜索完成。3、统计搜索过程中遇到的岛屿数量。
Java实现
public class NumberOfIslands {public int numIslands(char[][] grid) {if (grid null || grid.length 0 || grid[0].length 0) {return 0;}int m grid.length;int n grid[0].length;int count 0;
// {1, 1, 0, 0, 0},
// {1, 1, 0, 0, 0},
// {0, 0, 1, 0, 0},
// {0, 0, 0, 1, 1}for (int i 0; i m; i) {for (int j 0; j n; j) {if (grid[i][j] 1) {// 当前位置为陆地开始进行深度优先搜索// 直到grid[i][j]周边没有相连的陆地dfs(grid, i, j);// 每开始一次搜索岛屿数量加一count;}}}return count;}/*** 深度优先搜索函数* param grid* param i* param j*/private void dfs(char[][] grid, int i, int j) {int m grid.length;int n grid[0].length;// 边界条件和递归终止条件if (i 0 || i m || j 0 || j n || grid[i][j] 0) {return;}grid[i][j] 0; //将当前单元格标记为已访问//继续搜索当前位置的上、下、左、右四个方向,探索相邻的单元格//直到没有相邻的岛屿grid[i][j] 0dfs(grid, i 1, j);dfs(grid, i - 1, j);dfs(grid, i, j 1);dfs(grid, i, j - 1);}public static void main(String[] args) {NumberOfIslands islands new NumberOfIslands();char[][] grid {{1, 1, 0, 0, 0},{1, 1, 0, 0, 0},{0, 0, 1, 0, 0},{0, 0, 0, 1, 1}};System.out.println(Number of islands: islands.numIslands(grid));}
}
时间空间复杂度 时间复杂度O(m * n)其中 m 和 n 分别是二维网格的行数和列数因为需要遍历整个二维网格。 空间复杂度O(m * n)深度优先搜索的递归调用可能达到 O(m * n) 的深度其中 m 和 n 分别是二维网格的行数和列数。
