Leetcode 152 被围绕的区域 | 岛屿数量

1 题目130. 被围绕的区域给你一个m x n的矩阵board由若干字符X和O组成捕获所有被围绕的区域连接一个单元格与水平或垂直方向上相邻的单元格连接。区域连接所有O的单元格来形成一个区域。围绕如果一个区域中的所有O单元格都不在棋盘的边缘则该区域被包围。这样的区域完全被X单元格包围。通过原地将输入矩阵中的所有O替换为X来捕获被围绕的区域。你不需要返回任何值。示例 1输入board [[X,X,X,X],[X,O,O,X],[X,X,O,X],[X,O,X,X]]输出[[X,X,X,X],[X,X,X,X],[X,X,X,X],[X,O,X,X]]解释在上图中底部的区域没有被捕获因为它在 board 的边缘并且不能被围绕。示例 2输入board [[X]]输出[[X]]提示m board.lengthn board[i].length1 m, n 200board[i][j]为X或O2 代码实现cclass Solution { public: void solve(vectorvectorchar board) { if (board.empty() || board[0].empty()) return ; int m board.size(); int n board[0].size(); for (int i 0 ; i m ; i ){ if (board[i][0] O) dfs(board, i, 0 , m , n); if (board[i][n -1 ] O) dfs(board,i , n -1 , m , n); } for (int j 0 ; j n ; j){ if (board[0][j] O) dfs(board, 0, j, m, n); if (board[m-1][j] O) dfs(board, m-1, j, m, n); } for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] A) board[i][j] O; else if (board[i][j] O) board[i][j] X; } } } private: void dfs(vectorvectorchar board, int i, int j, int m, int n) { if (i 0 || i m || j 0 || j n || board[i][j] ! O) { return; } board[i][j] A; dfs(board, i - 1, j, m, n); dfs(board, i 1, j, m, n); dfs(board, i, j - 1, m, n); dfs(board, i, j 1, m, n); } };js/** * param {character[][]} board * return {void} Do not return anything, modify board in-place instead. */ var solve function(board) { if (!board || board.length 0) return; const m board.length; const n board[0].length; for (let i 0; i m; i) { if (board[i][0] O) dfs(board, i, 0, m, n); if (board[i][n-1] O) dfs(board, i, n-1, m, n); } for (let j 0; j n; j) { if (board[0][j] O) dfs(board, 0, j, m, n); if (board[m-1][j] O) dfs(board, m-1, j, m, n); } for (let i 0; i m; i) { for (let j 0; j n; j) { if (board[i][j] A) board[i][j] O; else if (board[i][j] O) board[i][j] X; } } }; function dfs(board, i, j, m, n) { if (i 0 || i m || j 0 || j n || board[i][j] ! O) { return; } board[i][j] A; dfs(board, i - 1, j, m, n); dfs(board, i 1, j, m, n); dfs(board, i, j - 1, m, n); dfs(board, i, j 1, m, n); }思考这什么其实我一点都不知道该怎么做我是想到之前有DFS , BFS 动态规划。但是放在图里面要怎么做呢题解题目要求把被 X 完全包围的所有O变成X边界上的 O 永远不会被包围不能变和边界 O 连通的 O也不会被包围不能变剩下的内部孤立 O才需要变成 X反向思维先找到所有边界上的 O用 DFS / BFS 把和边界 O 连通的所有 O 标记出来比如改成临时字符A最后遍历矩阵标记为A→ 恢复成O安全不包围还是O→ 变成X被包围这道题本质是二维网格的连通性搜索两种方法都可以DFS深度优先搜索代码简洁递归实现BFS广度优先搜索非递归用队列避免栈溢出DFS#include vector using namespace std; class Solution { public: void solve(vectorvectorchar board) { if (board.empty() || board[0].empty()) return; int m board.size(); // 行数 int n board[0].size(); // 列数 // 1. 遍历 4 条边界把边界 O 及其连通 O 标记为 A for (int i 0; i m; i) { // 第一列 if (board[i][0] O) dfs(board, i, 0, m, n); // 最后一列 if (board[i][n-1] O) dfs(board, i, n-1, m, n); } for (int j 0; j n; j) { // 第一行 if (board[0][j] O) dfs(board, 0, j, m, n); // 最后一行 if (board[m-1][j] O) dfs(board, m-1, j, m, n); } // 2. 遍历整个矩阵替换字符 for (int i 0; i m; i) { for (int j 0; j n; j) { // 标记 A 安全 O恢复 if (board[i][j] A) board[i][j] O; // 剩下的 O 被包围改成 X else if (board[i][j] O) board[i][j] X; } } } private: // DFS 递归函数把当前 O 标记为 A并向上下左右搜索 void dfs(vectorvectorchar board, int i, int j, int m, int n) { // 越界 或 不是 O直接返回 if (i 0 || i m || j 0 || j n || board[i][j] ! O) { return; } // 标记为临时字符 A board[i][j] A; // 上下左右四个方向递归搜索 dfs(board, i - 1, j, m, n); // 上 dfs(board, i 1, j, m, n); // 下 dfs(board, i, j - 1, m, n); // 左 dfs(board, i, j 1, m, n); // 右 } };边界判断矩阵为空直接返回遍历四条边第一列、最后一列、第一行、最后一行遇到O就启动 DFSDFS 函数先判断越界 是否是 O是 O 就标记成A表示安全递归上下左右继续找连通的 O最终替换A→O剩余O→X如果矩阵特别大DFS 递归可能栈溢出BFS 更安全。BFS#include vector #include queue using namespace std; class Solution { public: // 方向数组上下左右 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; void solve(vectorvectorchar board) { if (board.empty()) return; int m board.size(), n board[0].size(); queuepairint, int q; // 1. 把所有边界 O 入队 for (int i 0; i m; i) { for (int j 0; j n; j) { // 只处理边界上的 O if ((i 0 || i m-1 || j 0 || j n-1) board[i][j] O) { q.push({i, j}); board[i][j] A; } } } // 2. BFS 扩散标记 while (!q.empty()) { auto [x, y] q.front(); q.pop(); // 遍历四个方向 for (auto dir : dirs) { int nx x dir[0]; int ny y dir[1]; // 合法且是 O就标记并入队 if (nx 0 nx m ny 0 ny n board[nx][ny] O) { board[nx][ny] A; q.push({nx, ny}); } } } // 3. 最终替换 for (int i 0; i m; i) { for (int j 0; j n; j) { if (board[i][j] A) board[i][j] O; else if (board[i][j] O) board[i][j] X; } } } };运行流程演示输入矩阵X X X X X O O X X X O X X O X X找到边界 O只有(3,1)那个 ODFS/BFS 标记它为A其他内部 O 没有被标记最终替换标记 A → O其他 O → X核心要点反向思维不找被包围的找不被包围的边界 O 是安全区连通的 O 都安全用临时字符 A做标记避免重复遍历搜索只用上下左右四个方向总结这道题核心是反向标记不是直接找被包围区域DFS 代码简洁好写适合面试BFS 非递归适合大数据时间复杂度O(m×n)每个格子只访问一次空间复杂度O(m×n)递归栈 / 队列最大空间3 题目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提示m grid.lengthn grid[i].length1 m, n 300grid[i][j]的值为0或14 代码实现cclass Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(); int 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, m, n); } } } return count; } private: void dfs(vectorvectorchar grid, int i, int j, int m, int n) { if (i 0 || i m || j 0 || j n || grid[i][j] 0) { return; } grid[i][j] 0; dfs(grid, i - 1, j, m, n); dfs(grid, i 1, j, m, n); dfs(grid, i, j - 1, m, n); dfs(grid, i, j 1, m, n); } };js/** * param {character[][]} grid * return {number} */ var numIslands function(grid) { if (!grid || grid.length 0) return 0; const m grid.length; const n grid[0].length; let count 0; for (let i 0; i m; i) { for (let j 0; j n; j) { if (grid[i][j] 1) { count; dfs(grid, i, j, m, n); } } } return count; }; function dfs(grid, i, j, m, n) { if (i 0 || i m || j 0 || j n || grid[i][j] 0) { return; } grid[i][j] 0; dfs(grid, i - 1, j, m, n); dfs(grid, i 1, j, m, n); dfs(grid, i, j - 1, m, n); dfs(grid, i, j 1, m, n); }思考诶我咋整我怎么知道是不是连续的题解这道题和刚才的被围绕的区域是一模一样的思路学会这道图的 DFS/BFS 你就彻底通了一、先搞懂什么是岛屿1 陆地0 海洋上下左右连在一起的 11 个岛屿只要不连在一起就是新的岛屿二、核心思路超级简单遍历整个网格遇到 1→ 说明找到一个新岛屿计数 1马上用DFS / BFS把这块陆地所有连在一起的 1 全部淹掉变成 0继续遍历重复上面步骤为什么要淹掉避免重复计数已经算过的岛屿就别再碰了。三、DFS 解法代码最短面试首选#include vector using namespace std; class Solution { public: int numIslands(vectorvectorchar grid) { if (grid.empty() || grid[0].empty()) return 0; int m grid.size(); // 行数 int n grid[0].size(); // 列数 int count 0; // 岛屿数量 // 1. 遍历每一个格子 for (int i 0; i m; i) { for (int j 0; j n; j) { // 2. 遇到陆地 1发现新岛屿 if (grid[i][j] 1) { count; // 计数1 dfs(grid, i, j, m, n); // 3. DFS 把整个岛屿淹成 0 } } } return count; } private: // DFS把当前及相连的所有 1 都变成 0淹掉 void dfs(vectorvectorchar grid, int i, int j, int m, int n) { // 越界 或 不是陆地直接返回 if (i 0 || i m || j 0 || j n || grid[i][j] 0) { return; } // 把当前陆地淹掉1 → 0 grid[i][j] 0; // 上下左右 继续淹 dfs(grid, i - 1, j, m, n); // 上 dfs(grid, i 1, j, m, n); // 下 dfs(grid, i, j - 1, m, n); // 左 dfs(grid, i, j 1, m, n); // 右 } };四、BFS 解法非递归不爆栈#include vector #include queue using namespace std; class Solution { public: // 上下左右四个方向 int dirs[4][2] {{-1,0}, {1,0}, {0,-1}, {0,1}}; int numIslands(vectorvectorchar grid) { if (grid.empty()) return 0; int m grid.size(), n grid[0].size(); int count 0; queuepairint, int q; for (int i 0; i m; i) { for (int j 0; j n; j) { // 发现新岛屿 if (grid[i][j] 1) { count; q.push({i, j}); grid[i][j] 0; // 淹掉 // BFS 扩散淹掉整个岛屿 while (!q.empty()) { auto [x, y] q.front(); q.pop(); // 遍历四个方向 for (auto dir : dirs) { int nx x dir[0]; int ny y dir[1]; if (nx 0 nx m ny 0 ny n grid[nx][ny] 1) { grid[nx][ny] 0; q.push({nx, ny}); } } } } } } return count; } };五、怎么知道是不是连续的DFS/BFS 就是专门找 “连续 / 连通” 的工具你找到一个1让代码自动往上下左右找找到就淹成 0再也不会重复算这样每找到一次 1就是一个全新的岛屿六、运行流程1 1 0 0 0 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1遍历到左上角 1→ 计数 1淹掉一大片 1遍历到中间 1→ 计数 2淹掉遍历到右下角 1→ 计数 3淹掉最终输出3完美七、和上一题对比你会发现一模一样题目核心动作目的130 被围绕的区域找到边界 O → 标记 A保护安全 O200 岛屿数量找到 1 → 淹成 0避免重复计数本质二维网格 上下左右搜索 DFS/BFS学会这两道LeetCode 图的搜索题你直接通杀总结遇到 1 新岛屿计数 1DFS/BFS 淹掉整个岛屿防止重复时间复杂度O(m×n)每个格子只走一次空间复杂度O(m×n)递归栈 / 队列5 小结眼睛会了代码还没自己能默出来看明白了第一个dfs的思路但是具体怎么实现的细节自己要重新写写也要看看bfs怎么写。有点仓促相信睡梦中能消化一下坚持加油(ง •_•)ง