LeetCode 200. 岛屿数量题目描述给你一个由 ‘1’陆地和 ‘0’水组成的二维网格请你计算网格中岛屿的数量。岛屿总是被水包围并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。解法一DFS推荐遍历网格遇到 ‘1’ 就计数 1然后用 DFS 把整个岛屿沉没标记为 ‘0’。classSolution{publicintnumIslands(char[][]grid){if(gridnull||grid.length0)return0;introwsgrid.length;intcolsgrid[0].length;intcount0;for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]1){count;dfs(grid,i,j);}}}returncount;}privatevoiddfs(char[][]grid,inti,intj){// 边界检查 水检查if(i0||igrid.length||j0||jgrid[0].length||grid[i][j]0){return;}// 标记为已访问沉没grid[i][j]0;// 四个方向递归dfs(grid,i1,j);dfs(grid,i-1,j);dfs(grid,i,j1);dfs(grid,i,j-1);}}复杂度分析· 时间复杂度O(M × N)每个格子最多访问一次· 空间复杂度O(M × N)最坏情况全是陆地递归栈深度解法二BFS避免栈溢出用队列替代递归适合大网格防止栈溢出。classSolution{publicintnumIslands(char[][]grid){if(gridnull||grid.length0)return0;introwsgrid.length;intcolsgrid[0].length;intcount0;int[][]dirs{{1,0},{-1,0},{0,1},{0,-1}};for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]1){count;// BFSQueueint[]queuenewLinkedList();queue.offer(newint[]{i,j});grid[i][j]0;while(!queue.isEmpty()){int[]curqueue.poll();for(int[]d:dirs){intnicur[0]d[0];intnjcur[1]d[1];if(ni0nirowsnj0njcolsgrid[ni][nj]1){grid[ni][nj]0;queue.offer(newint[]{ni,nj});}}}}}}returncount;}}复杂度分析· 时间复杂度O(M × N)· 空间复杂度O(min(M, N))队列最坏情况解法三并查集Union-Find思路把每块陆地初始为独立集合相邻陆地合并最后统计集合个数。classSolution{privateint[]parent;privateintcount;publicintnumIslands(char[][]grid){if(gridnull||grid.length0)return0;introwsgrid.length;intcolsgrid[0].length;parentnewint[rows*cols];count0;// 初始化每个陆地是一个独立集合for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]1){parent[i*colsj]i*colsj;count;}}}// 只需要向右和向下合并避免重复for(inti0;irows;i){for(intj0;jcols;j){if(grid[i][j]1){// 向下合并if(i1rowsgrid[i1][j]1){union(i*colsj,(i1)*colsj);}// 向右合并if(j1colsgrid[i][j1]1){union(i*colsj,i*colsj1);}}}}returncount;}privateintfind(intx){// 路径压缩if(parent[x]!x){parent[x]find(parent[x]);}returnparent[x];}privatevoidunion(intx,inty){introotXfind(x);introotYfind(y);if(rootX!rootY){parent[rootX]rootY;count--;// 合并后岛屿数量减 1}}}复杂度分析· 时间复杂度O(M × N × α)α 为阿克曼函数反函数近似常数· 空间复杂度O(M × N)三种解法对比解法 时间复杂度 空间复杂度 特点DFS O(M×N) O(M×N) 代码简洁可能栈溢出BFS O(M×N) O(min(M,N)) 安全代码略长并查集 O(M×N×α) O(M×N) 适合动态连通性问题易错点提示边界检查放在访问前避免数组越界入队时就标记 ‘0’BFS 尤其重要否则会重复入队修改原数组是常见做法若不允许修改需额外 boolean[][] visited面试建议· 首选 DFS代码最简洁面试官通常接受· 若面试官追问网格很大怎么办可以提 BFS 或迭代式 DFS· 若题目变形为动态加陆地如 LeetCode 305则必须用并查集
