• LeetCode 热题 100 | 图论（一）

    目录

    1  200. 岛屿数量

    2  994. 腐烂的橘子

    2.1  智障遍历法

    2.2  仿层序遍历法

    菜鸟做题，语言是 C++

    1  200. 岛屿数量

    解题思路：

    1. 遍历二维数组，寻找 “1”（若找到则岛屿数量 +1）
    2. 寻找与当前 “1” 直接或间接连接在一起的 “1”
    3. 将这些 “1” 置为 “0”，再寻找下一个 “1”

    思路说明图：

    如步骤 1 所示，我们找到 “1”（红框内部），它可以作为一个岛屿的开头。接下来，我们寻找与这个 “1” 直接或间接连接在一起的 “1”，如步骤 2 所示。这一坨 “1”（红框内部）构成一个岛屿。

    直接连接 是指上下左右四个方向，斜对角方向的不算。

    除此之外，为了避免我们下一次寻找 “1” 时，把这座岛屿内部的 “1” 视为下一个岛屿的开头，我们要将这些 “1” 置为 “0” 。

    我们是对整个二维数组进行遍历的，若不在遍历完一座岛屿后将 “1” 置为 “0”，那么这座岛屿除开头之外的 “1” 会被误认为是下一座岛屿的开头。

    具体代码：

    ① Find “1”：在二维数组中寻找 “1”，作为岛屿的开头。

    1. for (int i = 0; i < nr; ++i) {
    2.     for (int j = 0; j < nc; ++j) {
    3.         if (grid[i][j] == '1') {
    4.             ++count;
    5.             helper(grid, i, j);
    6.         }
    7.     }
    8. }

    nr 是二维数组的行数，nc 是二维数组的列数。一旦找到 “1” 就 ++count，即认为找到了一座新的岛屿。同时，使用 helper 函数去寻找与当前 “1” 直接或间接连接在一起的 “1” 。

    ② Find Island：寻找与当前 “1” 直接或间接连接在一起的 “1”，它们构成一座岛屿。

    1. void helper(vectorchar>>& grid, int r, int c) {
    2.     int nr = grid.size();
    3.     int nc = grid[0].size();
    4.  
    5.     grid[r][c] = '0';
    6.     if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);
    7.     if (r + 1 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);
    8.     if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);
    9.     if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);
    10. }

    这四个 if 其实就是做上下左右四个方向的边界判断，同时判断当前 “1” 的邻居是不是 “1” 。若找到相邻的 “1”，那么再递归寻找与相邻的 “1” 直接或间接连接在一起的 “1” 。

    1. class Solution {
    2. public:
    3.     void helper(vectorchar>>& grid, int r, int c) {
    4.         int nr = grid.size();
    5.         int nc = grid[0].size();
    6.  
    7.         grid[r][c] = '0';
    8.         if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);
    9.         if (r + 1 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);
    10.         if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);
    11.         if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);
    12.     }
    13.  
    14.     int numIslands(vectorchar>>& grid) {
    15.         int nr = grid.size();
    16.         if (nr == 0) return 0;
    17.         int nc = grid[0].size();
    18.  
    19.         int count = 0;
    20.         for (int i = 0; i < nr; ++i) {
    21.             for (int j = 0; j < nc; ++j) {
    22.                 if (grid[i][j] == '1') {
    23.                     ++count;
    24.                     helper(grid, i, j);
    25.                 }
    26.             }
    27.         }
    28.         return count;
    29.     }
    30. };

    2  994. 腐烂的橘子

    与  200. 岛屿数量  像又不像，区别在于是否有时间观念

    2.1  智障遍历法

    解题思路：

    1. 每个时刻都遍历二维数组，寻找腐烂的橘子（2）
    2. 对位于腐烂的橘子（2）四周的新鲜橘子（1）进行污染
    3. 直到所有新鲜橘子都被污染，或者无法继续污染

    具体代码：

    ① 寻找腐烂的橘子（2），与 200 题的代码几乎一样。

    1. for (int i = 0; i < nr; ++i) {
    2.     for (int j = 0; j < nc; ++j) {
    3.         if (temp[i][j] == 2)
    4.             helper(grid, i, j);
    5.     }
    6. }

    ② 对位于腐烂的橘子（2）四周的新鲜橘子（1）进行污染。

    1. void helper(vectorint>>& grid, int r, int c) {
    2.     if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;
    3.     if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;
    4.     if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;
    5.     if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;
    6. }

    ③ 判断是否所有的新鲜橘子（1）都被污染。

    1. bool isRotted(vectorint>>& grid) {
    2.     for (int i = 0; i < nr; ++i) {
    3.         for (int j = 0; j < nc; ++j) {
    4.              if (grid[i][j] == 1) return false;
    5.         }
    6.     }
    7.     return true;
    8. }

    ④ 判断是否无法继续污染：在进行新一轮污染之前，先把上一轮的污染结果 grid 存入 temp 中，如果这一轮污染后有 temp == grid，则说明已经无法继续污染了。

    1. vectorint>> temp = grid;
    2. for (int i = 0; i < nr; ++i) {
    3.     for (int j = 0; j < nc; ++j) {
    4.         if (temp[i][j] == 2)
    5.             helper(grid, i, j);
    6.     }
    7. }
    8. if (temp == grid) return -1;

    这样做还有一个好处，就是可以通过 if (temp[i][j] == 2) 来寻找腐烂的橘子，避免在这一轮中新腐烂的橘子参与到污染中。

    1. class Solution {
    2. public:
    3.     int nr, nc;
    4.     void helper(vectorint>>& grid, int r, int c) {
    5.         if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;
    6.         if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;
    7.         if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;
    8.         if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;
    9.     }
    10.  
    11.     bool isRotted(vectorint>>& grid) {
    12.         for (int i = 0; i < nr; ++i) {
    13.             for (int j = 0; j < nc; ++j) {
    14.                 if (grid[i][j] == 1) return false;
    15.             }
    16.         }
    17.         return true;
    18.     }
    19.  
    20.     int orangesRotting(vectorint>>& grid) {
    21.         nr = grid.size();
    22.         nc = grid[0].size();
    23.  
    24.         int count = 0;
    25.         while (!isRotted(grid)) {
    26.             vectorint>> temp = grid;
    27.             for (int i = 0; i < nr; ++i) {
    28.                 for (int j = 0; j < nc; ++j) {
    29.                     if (temp[i][j] == 2)
    30.                         helper(grid, i, j);
    31.                 }
    32.             }
    33.             if (temp == grid) return -1;
    34.             ++count;
    35.             if (isRotted(grid)) return count;
    36.         }
    37.         return count;
    38.     }
    39. };

    2.2  仿层序遍历法

    参考官方题解进行了升级，仿二叉树的层序遍历，不用像 2.1 那样每次都进行全部遍历

    核心思想：将属于同一时刻的腐烂橘子视为属于同一层。

    上图画出了橘子逐步腐烂的 5 个时刻，每个时刻中打红叉的腐烂橘子属于同一层，打灰叉的腐烂橘子属于上一层。

    解题思路：

    • 将属于同一时刻的腐烂橘子送入队列中
    • 出队并遍历属于同一时刻的腐烂橘子
    • 对四周的新鲜橘子进行污染并送入队列中

    思路说明图：

    对于时刻 1，让腐烂的橘子入队；对于时刻 2，队列中的腐烂橘子出队，让它们对四周的新鲜橘子进行污染，最后将新被污染的橘子入队。以此类推。

    在一轮污染中，如果有橘子被污染，则计时器 +1，同时判断新鲜橘子是否被污染完毕；如果没有橘子被污染，则跳出循环，同时判断新鲜橘子是否被污染完毕。若没有橘子被污染且新鲜橘子没有被污染完毕，则表明无法污染所有新鲜橘子。

    具体代码：

    ① 初始化：

    • 计数新鲜橘子的数量，即 freshCount + 1
    • 记录腐烂橘子的位置，即将横纵坐标送入队列中
    1. int freshCount = 0;
    2. queueint, int>> q;
    3. for (int i = 0; i < nr; ++i) {
    4.     for (int j = 0; j < nc; ++j) {
    5.         if (grid[i][j] == 1) {
    6.             ++freshCount;
    7.         } else if (grid[i][j] == 2) {
    8.             q.push(make_pair(i, j));
    9.         }
    10.     }
    11. }

    nr 是 grid 的行数，nc 是 grid 的列数。

    ② 循环结构和二叉树的层序遍历一模一样：

    • 获取当前层中腐烂橘子的个数
    • 遍历当前层中的腐烂橘子
    1. while (!q.empty()) {
    2.     int currentSize = q.size();
    3.     for (int i = 0; i < currentSize; ++i) {
    4.         pair<int, int> pos = q.front();
    5.         q.pop();
    6.  
    7.         // 对橘子进行污染
    8.     }
    9. }

    ③ 针对每个腐烂橘子，对其四周进行污染：

    • 判断上/下/左/右位置是否越界，若越界则跳过该位置
    • 若该位置上的是新鲜橘子，则进行污染并将其入队
    • 同时将污染标志置为 true，新鲜橘子数量 - 1
    1. for (int i = 0; i < 4; ++i) {
    2.     int x = pos.first + dir_x[i];
    3.     int y = pos.second + dir_y[i];
    4.     if (x < 0|| x >= nr || y < 0|| y >= nc || grid[x][y] == 0)
    5.         continue;
    6.     if (grid[x][y] == 1) {
    7.         hasPolluted = true;
    8.         --freshCount;
    9.         grid[x][y] = 2;
    10.         q.push(make_pair(x, y));
    11.     }
    12.     if (freshCount == 0) break;
    13. }

    hasPolluted 用于表明当前层中是否至少有一个腐烂橘子造成了污染，如果没有造成污染，那么就要考虑是否无法污染所有新鲜橘子了。

    1. class Solution {
    2. public:
    3.     int dir_x[4] = {0, 1, 0, -1};
    4.     int dir_y[4] = {1, 0, -1, 0};
    5.     int orangesRotting(vectorint>>& grid) {
    6.         int nr = grid.size();
    7.         if (nr == 0) return 0;
    8.         int nc = grid[0].size();
    9.  
    10.         int freshCount = 0;
    11.         queueint, int>> q;
    12.         for (int i = 0; i < nr; ++i) {
    13.             for (int j = 0; j < nc; ++j) {
    14.                 if (grid[i][j] == 1) {
    15.                     ++freshCount;
    16.                 } else if (grid[i][j] == 2) {
    17.                     q.push(make_pair(i, j));
    18.                 }
    19.             }
    20.         }
    21.  
    22.         int timeCount = 0;
    23.         int hasPolluted = false;
    24.         while (!q.empty()) {
    25.             int currentSize = q.size();
    26.             for (int i = 0; i < currentSize; ++i) {
    27.                 pair<int, int> pos = q.front();
    28.                 q.pop();
    29.                 for (int i = 0; i < 4; ++i) {
    30.                     int x = pos.first + dir_x[i];
    31.                     int y = pos.second + dir_y[i];
    32.                     if (x < 0|| x >= nr || y < 0|| y >= nc || grid[x][y] == 0)
    33.                         continue;
    34.                     if (grid[x][y] == 1) {
    35.                         hasPolluted = true;
    36.                         --freshCount;
    37.                         grid[x][y] = 2;
    38.                         q.push(make_pair(x, y));
    39.                     }
    40.                     if (freshCount == 0) break;
    41.                 }
    42.             }
    43.             if (hasPolluted) ++timeCount;
    44.             hasPolluted = false;
    45.         }
    46.         return freshCount == 0 ? timeCount : -1;
    47.     }
    48. };

    技能点：使用循环结构来测试上/下/左/右四个方位。

    1. int dir_x[4] = {0, 1, 0, -1};
    2. int dir_y[4] = {1, 0, -1, 0};
    3.  
    4. for (int i = 0; i < 4; ++i) {
    5.     int x = pos.first + dir_x[i];
    6.     int y = pos.second + dir_y[i];
    7.     if (x < 0|| x >= nr || y < 0|| y >= nc)
    8.     // ...
    9. }

    并且用逆否命题来作为判断条件，就不需要写很多 && 了！

  • 相关阅读:
    如何构建一个外卖微信小程序
    java计算机毕业设计响应式交友网站MyBatis+系统+LW文档+源码+调试部署
    PEG化哌唑嗪-量子点/PEG修饰红色InP/ZnS量子点/PEG/g-C3N4量子点复合荧光纳米微球
    vue3中hooks的介绍及用法
    ubuntu疑难杂症
    HIK录像机GB28181对接相机不在线问题随笔
    Android手机或平板设置浏览器的UserAgent
    Socks5代理与IP代理：网络安全与爬虫中的应用
    11月第1周榜单丨飞瓜数据B站UP主排行榜（哔哩哔哩）发布！
    DS1302时钟芯片(SPI协议)
  • 原文地址：https://blog.csdn.net/m0_64140451/article/details/136325923