尧图网站建设 
题目描述给你一个由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示例 2输入grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]输出3解题思路方法一DFS核心思路遍历整个网格每遇到一个1岛屿数量 1用 DFS 把与它相连的所有1变成0淹没这个岛屿继续遍历直到网格结束关键淹没后后续遍历不会重复计数同一个岛屿。具体过程示例grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 遍历到 (0,0)1: 岛屿数1DFS淹没整个左上岛屿 [ [0,0,0,0,0], [0,0,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 遍历到 (2,2)1: 岛屿数2DFS淹没 [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,1,1] ] 遍历到 (3,3)1: 岛屿数3DFS淹没 [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0] ] 结果: 3 ✅代码实现写法1DFS递归class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private: void dfs(vectorvectorchar grid, int i, int j) { // 越界或不是陆地返回 if (i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] ! 1) { return; } // 淹没当前陆地 grid[i][j] 0; // 四个方向搜索 dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); } };写法2BFS队列class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; vectorpairint, int dirs {{1,0}, {-1,0}, {0,1}, {0,-1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; queuepairint, int q; q.push({i, j}); grid[i][j] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto [dx, dy] : dirs) { int nx x dx, ny y dy; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return count; } };复杂度分析维度复杂度说明时间复杂度O(m × n)每个格子最多访问一次空间复杂度O(m × n)DFS 递归栈最坏情况 / BFS 队列m, n 分别是网格的行数和列数。关键细节1. 为什么用0标记已访问避免重复访问同一个陆地比额外维护visited数组更省空间修改原网格但题目通常允许2. 为什么 DFS 不需要返回值因为 DFS 的作用是淹没岛屿不需要返回任何值。淹没后外层循环不会再次遇到这个岛屿。3. 为什么 BFS 用队列BFS 用队列保证按层遍历适合找最短路径。但本题只需要遍历连通块DFS 和 BFS 都可以。4. 和「岛屿的最大面积」的区别题目区别200. 岛屿数量统计岛屿个数695. 岛屿的最大面积统计最大岛屿的面积695 题需要在 DFS 中返回面积并取最大值。两种方法对比方法时间复杂度空间复杂度推荐度DFS递归O(m × n)O(m × n)⭐⭐⭐⭐⭐BFS队列O(m × n)O(m × n)⭐⭐⭐⭐DFS 代码更简洁BFS 不会栈溢出。方法二并查集核心思路把每个1看作一个独立节点相邻的1合并到同一个集合。最终集合的数量就是岛屿的数量。算法步骤初始化每个1是一个独立集合count1的总数遍历网格对于每个1检查右边和下边的邻居如果邻居也是1合并两个集合每次成功合并count--返回count即岛屿数量为什么只检查右边和下边因为遍历是从左上到右下左边和上边的邻居已经被处理过了避免重复合并。具体过程示例grid [ [1,1,0], [1,0,0], [0,0,1] ] 初始: 4 个 1count 4 (0,0)1: 检查右边(0,1)1 → 合并count3 检查下边(1,0)1 → 合并count2 (0,1)1: 检查下边(1,1)0 → 不合并 (1,0)1: 检查右边(1,1)0 → 不合并 (2,2)1: 无邻居 最终: count 2 ✅代码实现并查集模板class UnionFind { private: vectorint parent; // 父节点 vectorint rank; // 秩用于优化 int count; // 集合数量 public: UnionFind(vectorvectorchar grid) { int m grid.size(), n grid[0].size(); count 0; parent.resize(m * n); rank.resize(m * n, 0); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { parent[i * n j] i * n j; // 自己是自己的父节点 count; } } } } // 查找根节点路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } // 合并两个集合 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已经在同一集合 // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; // 合并后集合数减一 } int getCount() const { return count; } };主函数class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); UnionFind uf(grid); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { // 只检查右边和下边避免重复 if (j 1 n grid[i][j 1] 1) { uf.unite(i * n j, i * n j 1); } if (i 1 m grid[i 1][j] 1) { uf.unite(i * n j, (i 1) * n j); } } } } return uf.getCount(); } };复杂度分析维度复杂度说明时间复杂度O(m × n × α)α 是阿克曼函数的反函数接近 O(1)空间复杂度O(m × n)parent 和 rank 数组实际时间复杂度接近 O(m × n)。关键细节1. 为什么用一维数组表示二维坐标parent[i * n j] i * n j;把二维坐标(i, j)映射到一维下标i * n j方便用数组存储。2. 为什么只检查右边和下边因为遍历顺序是从左上到右下左边和上边的邻居已经被处理过了如果检查四个方向会重复合并3. 路径压缩的作用parent[x] find(parent[x]);把查找路径上的所有节点直接连到根节点加速后续查找。4. 按秩合并的作用if (rank[rootX] rank[rootY]) parent[rootX] rootY;把矮的树接到高的树上避免树退化成链表。并查集 vs DFS/BFS对比维度并查集DFS/BFS时间复杂度O(m × n × α)O(m × n)空间复杂度O(m × n)O(m × n)是否修改原网格❌ 不修改✅ 修改代码复杂度较高中等适用场景动态连通性问题静态连通块并查集的优势不修改原网格适合动态连通性问题如「岛屿数量 II」。DFS/BFS 的优势代码更简洁面试中更容易写出。总结要点说明核心思想每个 1 是独立集合相邻 1 合并关键操作遍历时只检查右边和下边合并后 count--时间复杂度O(m × n × α)接近 O(m × n)空间复杂度O(m × n) 【并查集-1】200.岛屿数量
题目描述给你一个由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示例 2输入grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ]输出3解题思路方法一DFS核心思路遍历整个网格每遇到一个1岛屿数量 1用 DFS 把与它相连的所有1变成0淹没这个岛屿继续遍历直到网格结束关键淹没后后续遍历不会重复计数同一个岛屿。具体过程示例grid [ [1,1,0,0,0], [1,1,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 遍历到 (0,0)1: 岛屿数1DFS淹没整个左上岛屿 [ [0,0,0,0,0], [0,0,0,0,0], [0,0,1,0,0], [0,0,0,1,1] ] 遍历到 (2,2)1: 岛屿数2DFS淹没 [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,1,1] ] 遍历到 (3,3)1: 岛屿数3DFS淹没 [ [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0], [0,0,0,0,0] ] 结果: 3 ✅代码实现写法1DFS递归class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j); } } } return count; } private: void dfs(vectorvectorchar grid, int i, int j) { // 越界或不是陆地返回 if (i 0 || i grid.size() || j 0 || j grid[0].size() || grid[i][j] ! 1) { return; } // 淹没当前陆地 grid[i][j] 0; // 四个方向搜索 dfs(grid, i 1, j); dfs(grid, i - 1, j); dfs(grid, i, j 1); dfs(grid, i, j - 1); } };写法2BFS队列class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; vectorpairint, int dirs {{1,0}, {-1,0}, {0,1}, {0,-1}}; for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { count; queuepairint, int q; q.push({i, j}); grid[i][j] 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto [dx, dy] : dirs) { int nx x dx, ny y dy; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return count; } };复杂度分析维度复杂度说明时间复杂度O(m × n)每个格子最多访问一次空间复杂度O(m × n)DFS 递归栈最坏情况 / BFS 队列m, n 分别是网格的行数和列数。关键细节1. 为什么用0标记已访问避免重复访问同一个陆地比额外维护visited数组更省空间修改原网格但题目通常允许2. 为什么 DFS 不需要返回值因为 DFS 的作用是淹没岛屿不需要返回任何值。淹没后外层循环不会再次遇到这个岛屿。3. 为什么 BFS 用队列BFS 用队列保证按层遍历适合找最短路径。但本题只需要遍历连通块DFS 和 BFS 都可以。4. 和「岛屿的最大面积」的区别题目区别200. 岛屿数量统计岛屿个数695. 岛屿的最大面积统计最大岛屿的面积695 题需要在 DFS 中返回面积并取最大值。两种方法对比方法时间复杂度空间复杂度推荐度DFS递归O(m × n)O(m × n)⭐⭐⭐⭐⭐BFS队列O(m × n)O(m × n)⭐⭐⭐⭐DFS 代码更简洁BFS 不会栈溢出。方法二并查集核心思路把每个1看作一个独立节点相邻的1合并到同一个集合。最终集合的数量就是岛屿的数量。算法步骤初始化每个1是一个独立集合count1的总数遍历网格对于每个1检查右边和下边的邻居如果邻居也是1合并两个集合每次成功合并count--返回count即岛屿数量为什么只检查右边和下边因为遍历是从左上到右下左边和上边的邻居已经被处理过了避免重复合并。具体过程示例grid [ [1,1,0], [1,0,0], [0,0,1] ] 初始: 4 个 1count 4 (0,0)1: 检查右边(0,1)1 → 合并count3 检查下边(1,0)1 → 合并count2 (0,1)1: 检查下边(1,1)0 → 不合并 (1,0)1: 检查右边(1,1)0 → 不合并 (2,2)1: 无邻居 最终: count 2 ✅代码实现并查集模板class UnionFind { private: vectorint parent; // 父节点 vectorint rank; // 秩用于优化 int count; // 集合数量 public: UnionFind(vectorvectorchar grid) { int m grid.size(), n grid[0].size(); count 0; parent.resize(m * n); rank.resize(m * n, 0); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { parent[i * n j] i * n j; // 自己是自己的父节点 count; } } } } // 查找根节点路径压缩 int find(int x) { if (parent[x] ! x) { parent[x] find(parent[x]); // 路径压缩 } return parent[x]; } // 合并两个集合 void unite(int x, int y) { int rootX find(x); int rootY find(y); if (rootX rootY) return; // 已经在同一集合 // 按秩合并 if (rank[rootX] rank[rootY]) { parent[rootX] rootY; } else if (rank[rootX] rank[rootY]) { parent[rootY] rootX; } else { parent[rootY] rootX; rank[rootX]; } count--; // 合并后集合数减一 } int getCount() const { return count; } };主函数class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); UnionFind uf(grid); for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { // 只检查右边和下边避免重复 if (j 1 n grid[i][j 1] 1) { uf.unite(i * n j, i * n j 1); } if (i 1 m grid[i 1][j] 1) { uf.unite(i * n j, (i 1) * n j); } } } } return uf.getCount(); } };复杂度分析维度复杂度说明时间复杂度O(m × n × α)α 是阿克曼函数的反函数接近 O(1)空间复杂度O(m × n)parent 和 rank 数组实际时间复杂度接近 O(m × n)。关键细节1. 为什么用一维数组表示二维坐标parent[i * n j] i * n j;把二维坐标(i, j)映射到一维下标i * n j方便用数组存储。2. 为什么只检查右边和下边因为遍历顺序是从左上到右下左边和上边的邻居已经被处理过了如果检查四个方向会重复合并3. 路径压缩的作用parent[x] find(parent[x]);把查找路径上的所有节点直接连到根节点加速后续查找。4. 按秩合并的作用if (rank[rootX] rank[rootY]) parent[rootX] rootY;把矮的树接到高的树上避免树退化成链表。并查集 vs DFS/BFS对比维度并查集DFS/BFS时间复杂度O(m × n × α)O(m × n)空间复杂度O(m × n)O(m × n)是否修改原网格❌ 不修改✅ 修改代码复杂度较高中等适用场景动态连通性问题静态连通块并查集的优势不修改原网格适合动态连通性问题如「岛屿数量 II」。DFS/BFS 的优势代码更简洁面试中更容易写出。总结要点说明核心思想每个 1 是独立集合相邻 1 合并关键操作遍历时只检查右边和下边合并后 count--时间复杂度O(m × n × α)接近 O(m × n)空间复杂度O(m × n)