051岛屿数量

岛屿数量题目链接https://leetcode.cn/problems/number-of-islands/description/?envTypestudy-plan-v2envIdtop-100-liked我的解答public int numIslands(char[][] grid) { int m grid.length, n grid[0].length; int[][] directions new int[][]{{-1,0}, {1,0},{0,-1},{0,1}};//上下左右四个方向 boolean[][] visited new boolean[m][n]; DequeInteger rows new LinkedList(); DequeInteger cols new LinkedList(); int ans 0; for(int i 0; i m; i){ for(int j 0; j n; j){ if(visited[i][j] || grid[i][j] 0){ continue; } //遇到没有被访问过的‘1’了 ans; rows.push(i); cols.push(j); while(!rows.isEmpty()){ int row rows.pop(); int col cols.pop(); for(int k 0; k 4; k){ row directions[k][0]; col directions[k][1]; if(row 0 row m col 0 col n grid[row][col] 1 visited[row][col] false){ visited[row][col] true; rows.push(row); cols.push(col); } row - directions[k][0]; col - directions[k][1]; } } } } return ans; }分析代码的时间复杂度为O(mn)空间复杂度为O(mn)。解题思路用visited数组记录当前位置是否被访问过遍历grid。当遇到没有被访问过的‘1’时让答案加一并让此位置的横坐标和纵坐标入栈然后从这个位置开始往上、下、左、右四个方向拓展未访问过的‘1’若存在未访问过的‘1’则让此位置的横坐标和纵坐标入栈重复此操作直到栈为空即可。看了官方题解后的解答//方法一深度优先搜索 //时间复杂度O(mn) //空间复杂度O(mn) public int numIslands(char[][] grid) { int m grid.length, n grid[0].length; int ans 0; for(int i0; im; i){ for(int j0; jn; j){ if(grid[i][j] 1){ ans; dfs(grid, i, j); } } } return ans; } public void dfs(char[][] grid, int x, int y){ int m grid.length, n grid[0].length; //越界或当前位置为‘0’ if(x0 || xm || y0 || yn || grid[x][y] 0){ return; } grid[x][y] 0; //上下左右四个方向分别进行深度优先搜索 dfs(grid, x-1, y); dfs(grid, x1, y); dfs(grid, x, y-1); dfs(grid, x, y1); } //方法二广度优先搜索 //时间复杂度O(mn) //空间复杂度O(min(m,n)) public int numIslands(char[][] grid) { int m grid.length, n grid[0].length; int[][] directions new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}}; QueueInteger neighbors new LinkedList(); int ans 0; for(int i0; im; i){ for(int j0; jn; j){ if(grid[i][j] 1){ ans; grid[i][j] 0; neighbors.add(i * n j); while(!neighbors.isEmpty()){ int index neighbors.remove(); int row index / n; int col index % n; for(int k0; k4; k){ row directions[k][0]; col directions[k][1]; if(row0 rowm col0 coln grid[row][col] 1){ grid[row][col] 0; neighbors.add(row * n col); } row - directions[k][0]; col - directions[k][1]; } } } } } return ans; } //方法三并查集 //时间复杂度O(MN×α(MN)) //空间复杂度O(MN) class UnionFind { int count;//集合总数 int[] parent;//代表节点的下标代表节点的parent是它自己 int[] size;//集合的元素个数 int[] stack;//调用find方法时对并查集做扁平化优化 public UnionFind(char[][] grid){ count 0; int m grid.length, n grid[0].length; parent new int[m * n]; size new int[m * n]; stack new int[m * n]; for(int i0; im; i){ for(int j0; jn; j){ if(grid[i][j] 1){ parent[i * n j] i * n j; size[i * n j] 1; count; } } } } public int find(int i){ int cnt 0; while(i ! parent[i]){ stack[cnt] i; i parent[i]; } //对当前集合做扁平化优化 while(cnt0){ parent[stack[--cnt]] i; } return i; } public void union(int i, int j){ int fi find(i); int fj find(j); if(fi ! fj){ //小挂大提高并查集的效率 if(size[fi] size[fj]){ parent[fj] fi; size[fi] size[fj]; } else{ parent[fi] fj; size[fj] size[fi]; } count--; } } public int getCount(){ return count; } } public int numIslands(char[][] grid) { int m grid.length, n grid[0].length; UnionFind uf new UnionFind(grid); int[][] directions new int[][]{{-1,0}, {1,0}, {0,-1}, {0,1}}; for(int i0; im; i){ for(int j0; jn; j){ if(grid[i][j] 1){ grid[i][j] 0; for(int k0; k4; k){ int ii i directions[k][0]; int jj j directions[k][1]; if(ii0 iim jj0 jjn grid[ii][jj] 1){ uf.union(i * n j, ii * n jj); } } } } } return uf.getCount(); }分析​ 1、方法一的解题思路遍历grid当遇到’1’时开始深度优先搜索深搜过程中遇到的’1’将其全部变为’0’最终进行了几次深搜就是有几个岛屿。​ 2、方法二的解题思路只是将方法一的深度优先搜索改为了广度优先搜索。遍历grid当遇到’1’时开始广度优先搜索用队列维护相邻’1’的下标广搜过程中遇到的’1’将其全部变为’0’最终进行了几次广搜就是有几个岛屿。​ 3、方法三的解题思路采用并查集。遍历grid当遇到’1’时将其置为’0’并开始向上下左右四个方向检查是否可以合并最终并查集中的集合总数就是岛屿的数量。​ 并查集并查集的关键成员变量有两个parent用来记录当前集合的代表节点代表节点的parent是它自己size用来记录当前集合的元素个数。本题并查集的关键方法有两个find方法用于查找当前元素所属集合的代表节点同时对当前集合做扁平化优化union方法用于合并两个元素所属的集合注意判断这两个元素所属的是否为同一个集合利用栈可以对并查集进行扁平化优化来提高并查集的效率。并查集效率的关键小挂大、扁平化。​ 并查集的详细知识点及其应用请参考视频链接https://www.bilibili.com/video/BV1894y1W7Sb/?spm_id_from333.1387.collection.video_card.clickvd_source8d4b451fa239e70767b6b38211a13a06总结本题有三种解决方法分别为深度优先搜索、广度优先搜索、并查集。三种方法都采用了过河拆桥即当前位置遍历完后就将当前位置的’1’置为’0’避免给后续过程带来干扰。