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/414126.html

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

相关文章

考研数据结构算法机试训练1

考研数据结构算法机试训练1

中南大学上机压轴题 测试数据&#xff1a; 3 500 0.6 100 0.8 200 0.7 100 输出 390首先要对输入的折扣进行排序&#xff0c;优先使用比率低的z进行支付。 然后用lowcost记录目前多少钱是打过折的。T-lowcost就是剩余没打折的。 每次循环用上一个人的折扣额度。若所有人折扣额…
阅读更多...
Android 跨进程通信aidl及binder机制详解（二）

Android 跨进程通信aidl及binder机制详解（二）

跨进程通信流程 通过上文可发现&#xff0c;要实现跨进程通信&#xff0c;需要客户端、服务端、客户端与服务端通信规约也就是通过aidl生成的java接口。下面用一个图来表述&#xff1a; 对于上图的调用过程&#xff0c;我们做一下解释&#xff1a;上图中列了几个对象的关联关系…
阅读更多...
windows安装部署node.js并搭建Vue项目

windows安装部署node.js并搭建Vue项目

一、官网下载安装包 官网地址&#xff1a;https://nodejs.org/zh-cn/download/ 二、安装程序 1、安装过程 如果有C/C编程的需求&#xff0c;勾选一下下图所示的部分&#xff0c;没有的话除了选择一下node.js安装路径&#xff0c;直接一路next 2、测试安装是否成功 【winR】…
阅读更多...
Windows系统x86机器安装（麒麟、统信）ARM系统详细教程

Windows系统x86机器安装（麒麟、统信）ARM系统详细教程

本次介绍在window系统x86机器上安装国产系统 arm 系统的详细教程。 注：ubuntu 的arm系统安装是一样的流程。 1.安装环境准备。 首先，你得有台电脑，配置别太差，至少4核8G内存，安装window10或者11都行（为啥不能是Window7，你要用也不是不行，你先解决win7补丁更新问题）。…
阅读更多...
目标检测——车辆障碍物数据集

目标检测——车辆障碍物数据集

检测道路上障碍物对于道路安全、自动驾驶技术的发展以及交通流畅性都具有重要性和意义。以下是这些重要性和意义的详细解释&#xff1a; 道路安全 从道路安全的角度来看&#xff0c;小障碍物可能给行驶中的车辆带来潜在风险。例如&#xff0c;一个丢弃在道路上的轮胎或纸箱可能…
阅读更多...
36.云原生之SpringCloud+k8s实践

36.云原生之SpringCloud+k8s实践

云原生专栏大纲 文章目录 SpringCloudk8s介绍spring-cloud-kubernetes服务发现配置管理负载均衡选主 spring-cloud-bookinfo案例构建项目环境配置namespace部署与验证productpagegatewaybookinfo-admindetailsratingsreviewsreviews-v1reviews-v2 总结 SpringCloudk8s介绍 ht…
阅读更多...
配置Windows和Linux之间的WireGuard对接

配置Windows和Linux之间的WireGuard对接

正文共&#xff1a;1197 字 20 图&#xff0c;预估阅读时间&#xff1a;2 分钟 今天简单测试一下WireGuard在Windows系统和Linux系统之间的对接情况。首先下载Windows安装包&#xff0c;这个安装包的轻量化程度让我大为震惊&#xff0c;可以说是第一次看见这么小的安装包&#…
阅读更多...
Flask学习笔记

Flask学习笔记

不论POST请求还是GET请求都支持在 URL 中添加变量&#xff0c;可以选择性的加上一个转换器&#xff0c;为变量指定数据类型。 history_alarm.route(/test/<int:post_id>, methods[POST]) def test(post_id):print(f"参数类型为&#xff1a;{type(post_id)}")i…
阅读更多...
语音编码的区别和使用场景

语音编码的区别和使用场景

语音编码标准各自在音质、数据压缩率、对带宽的需求、计算复杂性、延迟、鲁棒性以及专利许可费用等方面有所不同。这些差异决定了它们在不同场景下的使用。那常见语音编码标准的区别和典型使用场景&#xff1a; 1. G.711&#xff1a; 区别&#xff1a;使用脉冲编码调制&#…
阅读更多...
IDEA开发环境热部署

IDEA开发环境热部署

开发环境热部署 在实际的项目开发调试过程中会频繁地修改后台类文件&#xff0c;导致需要重新编译重新启动&#xff0c;整个过程非常麻烦&#xff0c;影响开发效率。Spring Boot提供了spring-boot-devtools组件&#xff0c;使得无须手动重启SpringBoot应用即可重新编译、启动项…
阅读更多...
水电表远程集中抄表管理系统

水电表远程集中抄表管理系统

水电表远程集中抄表管理系统是当前水电行业智能化发展的关键技术之一&#xff0c;为水电企业和用户提供了便捷、高效的抄表管理解决方案。该系统结合了远程监控、自动抄表、数据分析等多种功能&#xff0c;实现了水电抄表的智能化和精准化&#xff0c;为用户节省了大量人力物力…
阅读更多...
【自然语言处理三-self attention自注意是什么】

【自然语言处理三-self attention自注意是什么】

自然语言处理三-自注意力 self attention 自注意力是什么&#xff1f;自注意力模型出现的原因是什么&#xff1f;词性标注问题解决方法1-扩展window&#xff0c;引用上下文解决方法2-运用seq2seq架构新问题来了&#xff1a;参数量增加、无法并行的顽疾 自注意力self attention模…
阅读更多...
JDK安装及环境变量配置（保姆级教程）

JDK安装及环境变量配置（保姆级教程）

什么是JDK&#xff1f; JDK&#xff08;Java Development Kit&#xff09;是Java开发工具包的缩写 它是Java开发人员必备的软件包之一。JDK包含了用于编译、调试和运行Java程序的各种工具和库。通过安装JDK&#xff0c;开发人员可以开始编写、编译和运行Java应用程序、Applet和…
阅读更多...
UE5 UE4 自定义插件自动开启关联插件（plugin enable）

UE5 UE4 自定义插件自动开启关联插件（plugin enable）

在我们自己编写UE4、UE5的插件时&#xff0c;常常需要开启相关联的插件进行功能编写。 例如&#xff1a;UE4/5 批量进行贴图Texture压缩、修改饱和度_ue4批量修改纹理大小-CSDN博客 而让插件使用者每次使用时&#xff0c;依次进行开启其他相关联插件确实有些麻烦。 如何只需要…
阅读更多...
【医学影像】LIDC-IDRI数据集的无痛制作

【医学影像】LIDC-IDRI数据集的无痛制作

LIDC-IDRI数据集制作 0.下载0.0 链接汇总0.1 步骤 1.合成CT图reference 0.下载 0.0 链接汇总 LIDC-IDRI官方网址&#xff1a;https://www.cancerimagingarchive.net/nbia-search/?CollectionCriteriaLIDC-IDRINBIA Data Retriever 下载链接&#xff1a;https://wiki.canceri…
阅读更多...
麒麟银河操作系统V10部署ffmpeg

麒麟银河操作系统V10部署ffmpeg

麒麟银河操作系统V10部署ffmpeg 部署ffmpeg用来处理视频的各种操作 想使用ffmpeg&#xff0c;要先安装nasm&#xff0c;yasm&#xff0c;x264之后&#xff0c;否则会报错 nkvers 查看麒麟操作系统版本 cat /proc/version #查看linux版本信息 uname -a #查看linux版本和内核…
阅读更多...
Seawater resistant ADS-B Antenna for off-shore use

Seawater resistant ADS-B Antenna for off-shore use

目录 Introduction Technical data Introduction This ADS-B antenna, made of V4A (1.4571 316Ti) stainless special steel, is suitable for off-shore use and includes mounting kit. Condensation in the antenna itself is excluded by a hermetically sealed seal. …
阅读更多...
弱结构化日志 Flink SQL 怎么写？SLS SPL 来帮忙

弱结构化日志 Flink SQL 怎么写？SLS SPL 来帮忙

作者&#xff1a;潘伟龙&#xff08;豁朗&#xff09; 背景 日志服务 SLS 是云原生观测与分析平台&#xff0c;为 Log、Metric、Trace 等数据提供大规模、低成本、实时的平台化服务&#xff0c;基于日志服务的便捷的数据接入能力&#xff0c;可以将系统日志、业务日志等接入 …
阅读更多...
Spring Boot到底是如何进行自动配置的？

Spring Boot到底是如何进行自动配置的？

【1】从 spring.factories 配置文件中加载 EnableAutoConfiguration 自动配置类&#xff09;,获取的自动配 置类如图所示。 【2】若 EnableAutoConfiguration 等注解标有要 exclude 的自动配置类&#xff0c;那么再将这个自动配置类 排除掉&#xff1b; 【3】排除掉要 exclude …
阅读更多...
【Azure 架构师学习笔记】-Azure Synapse -- Link for SQL 实时数据加载

【Azure 架构师学习笔记】-Azure Synapse -- Link for SQL 实时数据加载

本文属于【Azure 架构师学习笔记】系列。 本文属于【Azure Synapse】系列。 前言 Azure Synapse Link for SQL 可以提供从SQL Server或者Azure SQL中接近实时的数据加载。通过这个技术&#xff0c;使用SQL Server/Azure SQL中的新数据能够几乎实时地传送到Synapse&#xff08;…
阅读更多...
最新文章

Copyright @ 2022~2023