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; ++i) {
    for (int j = 0; j < nc; ++j) {
        if (grid[i][j] == '1') {
            ++count;
            helper(grid, i, j);
        }
    }
}

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

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

void helper(vector<vector<char>>& 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 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);
    if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);
    if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);
}

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

class Solution {
public:
    void helper(vector<vector<char>>& 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 < nr && grid[r + 1][c] == '1') helper(grid, r + 1, c);
        if (c - 1 >= 0 && grid[r][c - 1] == '1') helper(grid, r, c - 1);
        if (c + 1 < nc && grid[r][c + 1] == '1') helper(grid, r, c + 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        int nr = grid.size();
        if (nr == 0) return 0;
        int nc = grid[0].size();

        int count = 0;
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (grid[i][j] == '1') {
                    ++count;
                    helper(grid, i, j);
                }
            }
        }
        return count;
    }
};

2  994. 腐烂的橘子

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

2.1  智障遍历法

解题思路：

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

具体代码：

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

for (int i = 0; i < nr; ++i) {
    for (int j = 0; j < nc; ++j) {
        if (temp[i][j] == 2)
            helper(grid, i, j);
    }
}

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

void helper(vector<vector<int>>& grid, int r, int c) {
    if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;
    if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;
    if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;
    if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;
}

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

bool isRotted(vector<vector<int>>& grid) {
    for (int i = 0; i < nr; ++i) {
        for (int j = 0; j < nc; ++j) {
             if (grid[i][j] == 1) return false;
        }
    }
    return true;
}

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

vector<vector<int>> temp = grid;
for (int i = 0; i < nr; ++i) {
    for (int j = 0; j < nc; ++j) {
        if (temp[i][j] == 2)
            helper(grid, i, j);
    }
}
if (temp == grid) return -1;

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

class Solution {
public:
    int nr, nc;
    void helper(vector<vector<int>>& grid, int r, int c) {
        if (r - 1 >= 0 && grid[r - 1][c] == 1) grid[r - 1][c] = 2;
        if (r + 1 < nr && grid[r + 1][c] == 1) grid[r + 1][c] = 2;
        if (c - 1 >= 0 && grid[r][c - 1] == 1) grid[r][c - 1] = 2;
        if (c + 1 < nc && grid[r][c + 1] == 1) grid[r][c + 1] = 2;
    }

    bool isRotted(vector<vector<int>>& grid) {
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (grid[i][j] == 1) return false;
            }
        }
        return true;
    }

    int orangesRotting(vector<vector<int>>& grid) {
        nr = grid.size();
        nc = grid[0].size();

        int count = 0;
        while (!isRotted(grid)) {
            vector<vector<int>> temp = grid;
            for (int i = 0; i < nr; ++i) {
                for (int j = 0; j < nc; ++j) {
                    if (temp[i][j] == 2)
                        helper(grid, i, j);
                }
            }
            if (temp == grid) return -1;
            ++count;
            if (isRotted(grid)) return count;
        }
        return count;
    }
};

2.2  仿层序遍历法

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

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

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

解题思路：

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

思路说明图：

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

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

具体代码：

① 初始化：

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

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

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

  • 获取当前层中腐烂橘子的个数
  • 遍历当前层中的腐烂橘子
while (!q.empty()) {
    int currentSize = q.size();
    for (int i = 0; i < currentSize; ++i) {
        pair<int, int> pos = q.front();
        q.pop();

        // 对橘子进行污染
    }
}

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

  • 判断上/下/左/右位置是否越界，若越界则跳过该位置
  • 若该位置上的是新鲜橘子，则进行污染并将其入队
  • 同时将污染标志置为 true，新鲜橘子数量 - 1
for (int i = 0; i < 4; ++i) {
    int x = pos.first + dir_x[i];
    int y = pos.second + dir_y[i];
    if (x < 0|| x >= nr || y < 0|| 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<vector<int>>& grid) {
        int nr = grid.size();
        if (nr == 0) return 0;
        int nc = grid[0].size();

        int freshCount = 0;
        queue<pair<int, int>> q;
        for (int i = 0; i < nr; ++i) {
            for (int j = 0; j < nc; ++j) {
                if (grid[i][j] == 1) {
                    ++freshCount;
                } else if (grid[i][j] == 2) {
                    q.push(make_pair(i, j));
                }
            }
        }

        int timeCount = 0;
        int hasPolluted = false;
        while (!q.empty()) {
            int currentSize = q.size();
            for (int i = 0; i < currentSize; ++i) {
                pair<int, int> pos = q.front();
                q.pop();
                for (int i = 0; i < 4; ++i) {
                    int x = pos.first + dir_x[i];
                    int y = pos.second + dir_y[i];
                    if (x < 0|| x >= nr || y < 0|| 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 < 4; ++i) {
    int x = pos.first + dir_x[i];
    int y = pos.second + dir_y[i];
    if (x < 0|| x >= nr || y < 0|| y >= nc)
    // ...
}

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

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/423421.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

langchain学习笔记（七）

langchain学习笔记（七）

RunnablePassthrough: Passing data through | &#x1f99c;️&#x1f517; Langchain 1、RunnablePassthrough可以在不改变或添加额外键的情况下传递输入。通常和RunnableParallel结合使用去分配数值给到字典的新键 两种方式调用RunnablePassthrough &#xff08;1&#…
阅读更多...
MySQL进阶：全局锁、表级锁、行级锁总结

MySQL进阶：全局锁、表级锁、行级锁总结

&#x1f468;‍&#x1f393;作者简介&#xff1a;一位大四、研0学生&#xff0c;正在努力准备大四暑假的实习 &#x1f30c;上期文章&#xff1a;MySQL进阶&#xff1a;MySQL事务、并发事务问题及隔离级别 &#x1f4da;订阅专栏&#xff1a;MySQL进阶 希望文章对你们有所帮助…
阅读更多...
Linux学习笔记:进程的终止和等待

Linux学习笔记:进程的终止和等待

进程终止和等待 进程终止进程退出场景进程常见退出方式_exit()退出exit()退出return退出exit()与_exit()的不同之处 进程的等待什么是进程等待?为什么要进行进程等待如何进行等待wait方式:waitpid方式 进程终止 进程退出场景 一般来讲,进程的退出场景有三种: 代码运行完毕,…
阅读更多...
Unity RectTransform·屏幕坐标转换

Unity RectTransform·屏幕坐标转换

RectTransform转屏幕坐标 分两种情况 Canvas渲染模式为Overlay时&#xff0c;使用此方式 public Rect GetScreenCoordinatesOfCorners(RectTransform rt) {var worldCorners new Vector3[4];rt.GetWorldCorners(worldCorners);var result new Rect(worldCorners[0].x,world…
阅读更多...
LeetCode54题：螺旋矩阵（python3）

LeetCode54题：螺旋矩阵（python3）

路径的长度即为矩阵中的元素数量&#xff0c;当路径的长度达到矩阵中的元素数量时即为完整路径&#xff0c;将该路径返回。 循环打印&#xff1a; “从左向右、从上向下、从右向左、从下向上” 四个方向循环打印。 class Solution:def spiralOrder(self, matrix: List[List[i…
阅读更多...
我的秋招数据分析岗面经分享（京东，美团，阿里，拼多多，vivo，滴滴）

我的秋招数据分析岗面经分享（京东，美团，阿里，拼多多，vivo，滴滴）

节前&#xff0c;我们社群组织了一场技术&面试讨论会&#xff0c;邀请了一些互联网大厂同学、参加社招和校招面试的同学&#xff0c;针对新手如何入门数据分析、机器学习算法、该如何备战面试、面试常考点分享等热门话题进行了深入的讨论。 基于社群的讨论&#xff0c;今天…
阅读更多...
艺术家林曦：新的一年｜开启人生的最佳竞技状态吧！

艺术家林曦：新的一年｜开启人生的最佳竞技状态吧！

开年大吉呀&#xff5e;新的一年&#xff0c;你准备好如何启程了吗&#xff1f; 　　 暄桐是一间传统美学教育教室&#xff0c;创办于2011年&#xff0c;艺术家林曦是创办人和授课老师&#xff0c;教授以书法为主的传统文化和技艺&#xff0c;皆在以书法为起点&#xff0c;亲…
阅读更多...
6、wuzhicms代码审计

6、wuzhicms代码审计

wuzhicms代码审计 前言 安装环境配置 服务器要求 Web服务器: apache/nginx/iis PHP环境要求:支持php5.2、php5.3、php5.4、php5.5、php5.6、php7.1 (推荐使用5.4或更高版本!) 数据库要求: Mysql5www/install文件夹即可进入安装页面 审计开始 首页文件index.php&#xff0c…
阅读更多...
测试需求平台8-Arco组件实现产品增改需求

测试需求平台8-Arco组件实现产品增改需求

✍此系列为整理分享已完结入门搭建《TPM提测平台》系列的迭代版&#xff0c;拥抱Vue3.0将前端框架替换成字节最新开源的arco.design&#xff0c;其中约60%重构和20%新增内容&#xff0c;定位为从 0-1手把手实现简单的测试平台开发教程&#xff0c;内容将囊括基础、扩展和实战&a…
阅读更多...
HCIA-Datacom实验指导手册：8 网络编程与自动化基础

HCIA-Datacom实验指导手册：8 网络编程与自动化基础

HCIA-Datacom实验指导手册&#xff1a;8 网络编程与自动化基础 一、实验介绍&#xff1a;二、实验拓扑&#xff1a;三、实验目的&#xff1a;四、配置步骤&#xff1a;步骤 1 完成交换机的 Telnet 预配置步骤 2 Python 代码编写 五、结果验证六、windows 计划任务程序配置七、 …
阅读更多...
大数据权限认证 Kerberos 部署

大数据权限认证 Kerberos 部署

文章目录 1、什么是 Kerberos2、Kerberos 术语和原理2.1、Kerberos 术语2.1、Kerberos 原理 3、Kerberos 服务部署3.1、前置条件3.2、安装依赖3.3、配置 krb5.conf3.4、配置 kdc.conf3.5、配置 kadm5.acl3.6、安装 KDC 数据库3.7、启动服务3.8、创建 Kerberos 管理员3.9、创建普…
阅读更多...
qsort的使用与实现

qsort的使用与实现

c语言常见的排序方法大概有这些&#xff0c;今天我们所讲的是就是qsort快排的讲解 头文件 qsort的使用 我们先使用msdn查看他的相关资料&#xff0c;得知这个函数的传参请情况 1.void *base 翻译过来就是将要排序的函数的起始位置/数组首元素地址 2.size_t num 翻译过来就是数…
阅读更多...
vue项目获取拼音首字母

vue项目获取拼音首字母

工具包 pinyin-pro npm install pinyin-pro 官方地址 pinyin-pro | pinyin-pro性能优异、转换准确的 js 中文转拼音工具https://pinyin-pro.cn/示例代码(获取每个汉字的拼音首字母) import {pinyin} from pinyin-pro;function getPinyinInitial(name){if (name) {let py p…
阅读更多...
redis实战笔记汇总

redis实战笔记汇总

文章目录 1 NoSQL入门概述1.1 能干嘛&#xff1f;1.2 传统RDBMS VS NOSQL1.3 NoSQL数据库的四大分类1.4 分布式数据库CAP原理 BASE原则1.5 分布式集群简介1.6 淘宝商品信息的存储方案 2 Redis入门概述2.1 是什么&#xff1f;2.2 能干嘛&#xff1f;2.3 怎么玩&#xff1f;核心…
阅读更多...
高性能MySQL 第4版

高性能MySQL 第4版

第一章MySQL架构 MySQL提供了多种锁的颗粒度&#xff0c;每种MySQL存储引擎都可以实现自己的锁策略和锁力度。 行级锁是在存储引擎而不是在服务器中实现的。 隔离界别 READ UNCOMMITTED - 脏读 在事务中可以可以查看到其他事务中还没有提交的修改。实际中很少用。 READ C…
阅读更多...
运筹学_1.1.4 线性规划问题-解的概念

运筹学_1.1.4 线性规划问题-解的概念

1.1.4 线性规划问题-解的概念 一、可行解与最优解二、基的概念三、基变量、基向量&#xff1b;非基变量、非基向量&#xff1b;基解、基可行解&#xff1b;四、最优解与可行解、基可行解的关系五、用例题&#xff08;枚举法&#xff09;巩固基解、基可行解、最优解三个概念1、例…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（点击事件）

鸿蒙Harmony应用开发—ArkTS声明式开发（点击事件）

组件被点击时触发的事件。 说明&#xff1a; 从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。 onClick onClick(event: (event: ClickEvent) > void) 点击动作触发该回调。 卡片能力&#xff1a; 从API version 9开始…
阅读更多...
【python】`assert`断言语句

【python】`assert`断言语句

assert是一个断言语句&#xff0c;用于在代码中检查某个条件是否为真。 如果条件为假&#xff0c;将触发AssertionError 异常&#xff0c;从而指示存在错误。
阅读更多...
【博图TIA-Api】通过Excel自动新建文件夹和导入FB块

【博图TIA-Api】通过Excel自动新建文件夹和导入FB块

【博图TIA-Api】通过Excel自动新建文件夹和导入FB块 说明思路准备获取Excel表格内文件名和FB块名等信息新建文件夹部分筛分获取的文件夹数据&#xff0c;去掉重复内容创建文件夹 导入FB块导出FB块的xml文件查找需要放置的文件夹导入块 说明 续上一篇文章&#xff0c;这次是根据…
阅读更多...
C++ //练习 10.19 用stable_partition重写前一题的程序，与stable_sort类似，在划分后的序列中维持原有元素的顺序。

C++ //练习 10.19 用stable_partition重写前一题的程序，与stable_sort类似，在划分后的序列中维持原有元素的顺序。

C Primer&#xff08;第5版&#xff09; 练习 10.19 练习 10.19 用stable_partition重写前一题的程序&#xff0c;与stable_sort类似&#xff0c;在划分后的序列中维持原有元素的顺序。 环境&#xff1a;Linux Ubuntu&#xff08;云服务器&#xff09; 工具&#xff1a;vim …
阅读更多...
最新文章

Copyright @ 2022~2023