网站制作多少钱,王烨娟,如何做地方网站推广,专业品牌营销策划Problem: 200. 岛屿数量 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
该问题可以归纳为一类遍历二维矩阵的题目#xff0c;此类中的一部分题目可以利用DFS来解决#xff0c;具体到本题目#xff1a; 1.我们首先要针对于二维数组上的每一个点#xff0c;尝试展… Problem: 200. 岛屿数量 文章目录 题目描述思路解题方法复杂度Code 题目描述 思路
该问题可以归纳为一类遍历二维矩阵的题目此类中的一部分题目可以利用DFS来解决具体到本题目 1.我们首先要针对于二维数组上的每一个点尝试展开DFS 2.我们定义一个和给定矩阵一样大的布尔类型的矩阵visited用于辅助判断是否开展DFS,若是符合的合法点则设置为true 3.我们在DFS的具体实现中以每一个点为基础从该点的上下左右四个方位开始尝试是否DFS 解题方法 1.定义二维辅助数组visited初始化大小为给定数组grid的大小若在后续操作中标记某一点为true则表示该位置是已经遍历过的合法位置定义记录岛屿数量的变量count 2.在主函数numIslands中我们遍历二维数组中每一个点当满足visited[i][j] ! true grid[i][j] 1’时则代表此处最少存在一个岛屿count加一再调用DFS函数 3.DFS函数的具体处理 3.1 每次先将当前合法位置设置为truevisited中定义一个二维数组**int[][] directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};用于记录当前某一位置的点的四个方位上下左右 3.2 for循环范围1~4循环中每次执行 int newI i directions[k][0];int newJ j directions[k][1];**用于记录当前位置的新的位置并判断当前新位置是否合法若合法则DFS递归调用在新的位置的基础上 复杂度
时间复杂度: O ( m n ) O(mn) O(mn) 空间复杂度: O ( m n ) O(mn) O(mn) Code
class Solution {private boolean[][] visited;private int row;private int col;/*** Get all the island counts** param grid Given a two-dimensional array* return int*/public int numIslands(char[][] grid) {row grid.length;col grid[0].length;visited new boolean[row][col];//The count of islandint count 0;for (int i 0; i row; i) {for (int j 0; j col; j) {if (visited[i][j] ! true grid[i][j] 1) {count;dfs(grid, i, j);}}}return count;}/*** Try dfs or not from each point in a two-dimensional array** param grid Given a two-dimensional array* param i Abscissa* param j Ordinate*/private void dfs(char[][] grid, int i, int j) {//Record four bearingsint[][] directions {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};//The current legal location is set to truevisited[i][j] true;for (int k 0; k 4; k) {int newI i directions[k][0];int newJ j directions[k][1];if (newI 0 newI row newJ 0 newJ col visited[newI][newJ] false grid[newI][newJ] 1) {dfs(grid, newI, newJ);}}}
}
