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”，作为岛屿的开头。

for (int i = 0; i  
 
 
nr 是二维数组的行数，nc 是二维数组的列数。一旦找到 “1” 就 ++count，即认为找到了一座新的岛屿。同时，使用 helper 函数去寻找与当前 “1” 直接或间接连接在一起的 “1” 。
 
 
② Find Island：寻找与当前 “1” 直接或间接连接在一起的 “1”，它们构成一座岛屿。
 
void helper(vector& grid, int r, int c) {
    int nr = grid.size();
    int nc = grid[0].size();
    grid[r][c] = '0';
    if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);
    if (r + 1 = 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);
    if (c + 1  
 
 
这四个 if 其实就是做上下左右四个方向的边界判断，同时判断当前 “1” 的邻居是不是 “1” 。若找到相邻的 “1”，那么再递归寻找与相邻的 “1” 直接或间接连接在一起的 “1” 。
 
 
class Solution {
public:
    void helper(vector& grid, int r, int c) {
        int nr = grid.size();
        int nc = grid[0].size();
        grid[r][c] = '0';
        if (r - 1 >= 0 && grid[r - 1][c] == '1') helper(grid, r - 1, c);
        if (r + 1 = 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);
        if (c + 1  
 
 
2  994. 腐烂的橘子
 
与  200. 岛屿数量  像又不像，区别在于是否有时间观念
 
2.1  智障遍历法
 
解题思路：
 
每个时刻都遍历二维数组，寻找腐烂的橘子（2）
对位于腐烂的橘子（2）四周的新鲜橘子（1）进行污染
直到所有新鲜橘子都被污染，或者无法继续污染
具体代码：
 
① 寻找腐烂的橘子（2），与 200 题的代码几乎一样。
 
for (int i = 0; i  
② 对位于腐烂的橘子（2）四周的新鲜橘子（1）进行污染。
 
void helper(vector& grid, int r, int c) {
    if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;
    if (r + 1 = 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;
    if (c + 1  
③ 判断是否所有的新鲜橘子（1）都被污染。
 
bool isRotted(vector& grid) {
    for (int i = 0; i  
④ 判断是否无法继续污染：在进行新一轮污染之前，先把上一轮的污染结果 grid 存入 temp 中，如果这一轮污染后有 temp == grid，则说明已经无法继续污染了。
 
vector temp = grid;
for (int i = 0; i  
 
 
这样做还有一个好处，就是可以通过 if (temp[i][j] == 2) 来寻找腐烂的橘子，避免在这一轮中新腐烂的橘子参与到污染中。
 
 
class Solution {
public:
    int nr, nc;
    void helper(vector& grid, int r, int c) {
        if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;
        if (r + 1 = 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;
        if (c + 1  
 
 
2.2  仿层序遍历法
 
参考官方题解进行了升级，仿二叉树的层序遍历，不用像 2.1 那样每次都进行全部遍历
 
核心思想：将属于同一时刻的腐烂橘子视为属于同一层。
 
 
 
 
上图画出了橘子逐步腐烂的 5 个时刻，每个时刻中打红叉的腐烂橘子属于同一层，打灰叉的腐烂橘子属于上一层。
 
 
解题思路：
 

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

  思路说明图：

  

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

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

  具体代码：

  ① 初始化：

  • 计数新鲜橘子的数量，即 freshCount + 1
  • 记录腐烂橘子的位置，即将横纵坐标送入队列中

    int freshCount = 0;
    queue q;
    for (int i = 0; i  
     
     
    nr 是 grid 的行数，nc 是 grid 的列数。
     
     
    ② 循环结构和二叉树的层序遍历一模一样：
     
    

    • 获取当前层中腐烂橘子的个数
    • 遍历当前层中的腐烂橘子

      while (!q.empty()) {
          int currentSize = q.size();
          for (int i = 0; i  
      ③ 针对每个腐烂橘子，对其四周进行污染：
       
      

      • 判断上/下/左/右位置是否越界，若越界则跳过该位置
      • 若该位置上的是新鲜橘子，则进行污染并将其入队
      • 同时将污染标志置为 true，新鲜橘子数量 - 1

        for (int i = 0; i = nr || y = nc || grid[x][y] == 0)
                continue;
            if (grid[x][y] == 1) {
                hasPolluted = true;
                --freshCount;
                grid[x][y] = 2;
                q.push(make_pair(x, y));
            }
            if (freshCount == 0) break;
        }

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

        class Solution {
        public:
            int dir_x[4] = {0, 1, 0, -1};
            int dir_y[4] = {1, 0, -1, 0};
            int orangesRotting(vector& grid) {
                int nr = grid.size();
                if (nr == 0) return 0;
                int nc = grid[0].size();
                int freshCount = 0;
                queue q;
                for (int i = 0; i = nr || y = nc || grid[x][y] == 0)
                                continue;
                            if (grid[x][y] == 1) {
                                hasPolluted = true;
                                --freshCount;
                                grid[x][y] = 2;
                                q.push(make_pair(x, y));
                            }
                            if (freshCount == 0) break;
                        }
                    }
                    if (hasPolluted) ++timeCount;
                    hasPolluted = false;
                }
                return freshCount == 0 ? timeCount : -1;
            }
        };

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

        int dir_x[4] = {0, 1, 0, -1};
        int dir_y[4] = {1, 0, -1, 0};
        for (int i = 0; i = nr || y = nc)
            // ...
        }

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

本网站所收集的部分公开资料来源于AI生成和互联网，转载的目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。