当前位置: 首页 > news >正文

LeetCode 热题 100_腐烂的橘子(52_994_中等_C++)(图;广度优先遍历(队列))

LeetCode 热题 100_腐烂的橘子(52_994)

    • 题目描述:
    • 输入输出样例:
    • 题解:
      • 解题思路:
        • 思路一(广度优先遍历(队列)):
      • 代码实现
        • 代码实现(思路一(广度优先遍历(队列))):
        • 以思路一为例进行调试
        • 部分代码解读

题目描述:

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

值 0 代表空单元格;
值 1 代表新鲜橘子;
值 2 代表腐烂的橘子。

每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。

输入输出样例:

示例 1:
在这里插入图片描述

输入:grid = [[2,1,1],[1,1,0],[0,1,1]]
输出:4

示例 2:
输入:grid = [[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个方向上。

示例 3:
输入:grid = [[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示:
m== grid.length
n == grid[i].length
1 <= m, n <= 10
grid[i][j] 仅为 0、1 或 2

题解:

解题思路:

思路一(广度优先遍历(队列)):

1、从柿子腐烂的过程,可以容易的想到腐烂是从坏柿子为中心开始一圈一圈向外进行蔓延。每个柿子为一个腐烂的中心,同时进行腐烂。容易想到每个腐烂的橘子为中心同时进行广度优先遍历,将好柿子变为坏柿子。

2、具体思路如下:
① 一开始遍历整个网格,将所有腐烂的柿子入队(并统计好柿子的数量,如果好柿子的数量为0则返回时间0)。

② 统计此时队列中腐烂柿子的数量n0。
③ 将n0个腐烂柿子出队,并将其上下左右好柿子入队,入队时将其变为腐烂的柿子。
④ 此时将时间(time)+1,并更新剩余好柿子数量(好柿子-新腐烂的柿子)。

⑤ 统计此时队列中腐烂柿子的数量n1。
⑥ 将n1个腐烂柿子出队,并将其上下左右好柿子入队,入队时将其变为腐烂的柿子。
⑦ 此时将时间(time)+1,并更新剩余好柿子数量(好柿子-新腐烂的柿子)。



重复上述过程,直至队列为空为止。
⑧ 如果好柿子的数量>0,则输出-1。如果好柿子的数量=0,则输出时间(time)。

3、复杂度分析:
① 时间复杂度:O(mn),其中 n,m 分别为 grid 的行数与列数,先对网格的坏橘子入队,统计好橘子的数量O(mn)。再进行一次广度优先搜索的时间O(mn)。
② 空间复杂度:O(m+n),主要取决于栈的深度,最坏情况为m=n时,中心的一个为坏橘子,栈中元素最多为最外层的数量(2m+2n)。

代码实现

代码实现(思路一(广度优先遍历(队列))):
int orangesRotting(vector<vector<int>>& grid) {//网格的行和列int r_size=grid.size(),c_size=grid[0].size();//好柿子的数量int nums_goodOrange=0;//最小分钟数int time=0;//存放腐烂句子的队列queue<pair<int,int>> Q;//遍历网格统计好橘子的数量,并将坏橘子入队(进行后续的广度优先遍历)for (int r = 0; r < r_size; r++){for (int c = 0; c < c_size; c++){//坏柿子入队if (grid[r][c]==2){Q.push({r,c});//统计好柿子数量}else if(grid[r][c]==1){nums_goodOrange+=1;}}}//如果好橘子的数量为0则之间返回0if (nums_goodOrange==0) return 0;//注意我们队列中一开始会存储坏橘子的数量,所以我们在这里加上,便于我们后续统计好橘子转换为坏橘子的数量nums_goodOrange+=Q.size();while (!Q.empty()){//“一层”坏橘子的数量int n=Q.size();//将n0个腐烂柿子出队,并将其上下左右好柿子入队,入队时将其变为腐烂的柿子//此时将时间(time)+1,并更新剩余好柿子数量(好柿子-新腐烂的柿子)。for (int i = 0; i < n; i++){auto rc= Q.front();Q.pop();int r=rc.first,c=rc.second;//处理坏柿子紧挨着上下左右的好柿子if (r-1>=0 && grid[r-1][c]==1){grid[r-1][c]=2;Q.push({r-1,c});}if (r+1<r_size && grid[r+1][c]==1){grid[r+1][c]=2;Q.push({r+1,c});}if (c-1>=0 && grid[r][c-1]==1){grid[r][c-1]=2;Q.push({r,c-1});}if (c+1<c_size && grid[r][c+1]==1){grid[r][c+1]=2;Q.push({r,c+1});}}//新腐烂一层柿子后time+1,更新好柿子的数量++time;nums_goodOrange-=n;}if (nums_goodOrange>0){return -1;}//注意一开始我们统计了一次,最开始就是腐烂的坏柿子,所以要减去return time-1;
}
以思路一为例进行调试
#include<iostream>
#include <vector>
#include<queue>
using namespace std;class Solution {
public:int orangesRotting(vector<vector<int>>& grid) {//网格的行和列int r_size=grid.size(),c_size=grid[0].size();//好柿子的数量int nums_goodOrange=0;//最小分钟数int time=0;//存放腐烂句子的队列queue<pair<int,int>> Q;//遍历网格统计好橘子的数量,并将坏橘子入队(进行后续的广度优先遍历)for (int r = 0; r < r_size; r++){for (int c = 0; c < c_size; c++){//坏柿子入队if (grid[r][c]==2){Q.push({r,c});//统计好柿子数量}else if(grid[r][c]==1){nums_goodOrange+=1;}}}//如果好橘子的数量为0则之间返回0if (nums_goodOrange==0) return 0;//注意我们队列中一开始会存储坏橘子的数量,所以我们在这里加上,便于我们后续统计好橘子转换为坏橘子的数量nums_goodOrange+=Q.size();while (!Q.empty()){//“一层”坏橘子的数量int n=Q.size();//将n0个腐烂柿子出队,并将其上下左右好柿子入队,入队时将其变为腐烂的柿子//此时将时间(time)+1,并更新剩余好柿子数量(好柿子-新腐烂的柿子)。for (int i = 0; i < n; i++){auto rc= Q.front();Q.pop();int r=rc.first,c=rc.second;//处理坏柿子紧挨着上下左右的好柿子if (r-1>=0 && grid[r-1][c]==1){grid[r-1][c]=2;Q.push({r-1,c});}if (r+1<r_size && grid[r+1][c]==1){grid[r+1][c]=2;Q.push({r+1,c});}if (c-1>=0 && grid[r][c-1]==1){grid[r][c-1]=2;Q.push({r,c-1});}if (c+1<c_size && grid[r][c+1]==1){grid[r][c+1]=2;Q.push({r,c+1});}}//新腐烂一层柿子后time+1,更新好柿子的数量++time;nums_goodOrange-=n;}if (nums_goodOrange>0){return -1;}//注意一开始我们统计了一次,最开始就是腐烂的坏柿子,所以要减去return time-1;}
};int main(int argc, char const *argv[])
{vector<vector<int>> grid={{2,1,1},{0,1,1},{1,0,1}};//统计腐烂柿子的数量并输出Solution s;cout<<s.orangesRotting(grid);return 0;
}
部分代码解读

pair<int,int>的解读请点击此链接:(LeetCode 热题 100_岛屿数量(51_200_中等_C++)(图;深度优先遍历;广度优先搜索)(pair<int,int>)

LeetCode 热题 100_腐烂的橘子(52_994)原题链接
欢迎大家和我沟通交流(✿◠‿◠)

相关文章:

LeetCode 热题 100_腐烂的橘子(52_994_中等_C++)(图;广度优先遍历(队列))

LeetCode 热题 100_腐烂的橘子&#xff08;52_994&#xff09; 题目描述&#xff1a;输入输出样例&#xff1a;题解&#xff1a;解题思路&#xff1a;思路一&#xff08;广度优先遍历&#xff08;队列&#xff09;&#xff09;&#xff1a; 代码实现代码实现&#xff08;思路一…...

Nginx 可观测性最佳实践

Nginx 介绍 Nginx 是一个开源、轻量级、高性能的 HTTP 和反向代理服务器&#xff0c;也可以用于 IMAP/POP3 代理服务器。Nginx 因其采用的异步非阻塞工作模型&#xff0c;使其具备高并发、低资源消耗的特性。高度模块化设计也使得 Nginx 具备很好的扩展性&#xff0c;在处理静…...

LabVIEW光流跟踪算法

1. 光流跟踪算法的概述 光流&#xff08;Optical Flow&#xff09;是一种图像处理技术&#xff0c;用于估算图像中像素点的运动。通过比较连续帧图像&#xff0c;光流算法可以分析图像中的运动信息&#xff0c;广泛用于目标跟踪、运动检测和视频处理等场景。该示例使用了NI Vi…...

Jira用例自动去除summary重复用例

title: Jira用例自动去除summary重复用例 tags: - jira - python categories: - python一、背景与需求二、解决方案思路三、实施步骤本文永久更新地址: 在使用 Jira 进行项目管理时&#xff0c;测试用例的维护至关重要。随着项目推进&#xff0c;用例数量增多&#xff0c;可能…...

基于openEuler22.03SP4部署Prometheus+Grafana

测试环境 Virtual Box&#xff0c;openEuler-22.03-LTS-SP4-x86_64-dvd.iso&#xff0c;4 vCPU, 8G RAM, 60 vDisk。最小化安装。需联网。 系统环境 关闭防火墙 systemctl stop firewalld systemctl disable firewalld systemctl status firewalld selinux关闭 sed -ri…...

泛目录和泛站有什么差别

啥是 SEO 泛目录&#xff1f; 咱先来说说 SEO 泛目录是啥。想象一下&#xff0c;你有一个巨大的图书馆&#xff0c;里面的书架上摆满了各种各样的书&#xff0c;每一本书都代表着一个网页。而 SEO 泛目录呢&#xff0c;就像是一个超级图书管理员&#xff0c;它的任务就是把这些…...

css 布局及动画应用(flex+transform+transition+animation)

文章目录 css 布局及动画应用animationtransform&#xff0c;transition&#xff0c;animation 综合应用实例代码实例解释 css 布局及动画应用 Display用法 作用&#xff1a;用于控制元素的显示类型&#xff0c;如块级元素、内联元素、无显示等。常见属性值及示例&#xff1a;…...

springboot vue uniapp 仿小红书 1:1 还原 (含源码演示)

线上预览: 移动端 http://8.146.211.120:8081/ 管理端 http://8.146.211.120:8088/ 小红书凭借优秀的产品体验 和超高人气 目前成为笔记类产品佼佼者 此项目将详细介绍如何使用Vue.js和Spring Boot 集合uniapp 开发一个仿小红书应用&#xff0c;凭借uniapp 可以在h5 小程序 app…...

lombok在高版本idea中注解不生效的解决

环境&#xff1a; IntelliJ IDEA 2024.3.1.1 Spring Boot Maven 问题描述 使用AllArgsConstructor注解一个用户类&#xff0c;然后调用全参构造方法创建对象&#xff0c;出现错误&#xff1a; java: 无法将类 com.itheima.pojo.User中的构造器 User应用到给定类型; 需要:…...

跨境电商领域云手机之选:亚矩阵云手机的卓越优势

在跨境电商蓬勃发展的当下&#xff0c;云手机已成为众多企业拓展海外市场的得力助手。亚矩阵云手机凭借其独特优势&#xff0c;在竞争激烈的云手机市场中崭露头角。不过&#xff0c;鉴于市场上云手机服务供应商繁多&#xff0c;企业在抉择时需对诸多要素予以审慎考量。 跨境电商…...

Linux第二课:LinuxC高级 学习记录day02

2.4、shell中的特殊字符 2.4.4、命令置换符 或者 $() 反引号&#xff1a;esc下面的按键&#xff0c;英文状态下直接按 功能&#xff1a;将一个命令的输出作为另一个命令的参数 echo 不会认为hostname是一个命令 加上 之后&#xff0c;先执行hostname&#xff0c;拿到主机名…...

6. NLP自然语言处理(Natural Language Processing)

自然语言是指人类日常使用的语言&#xff0c;如中文、英语、法语等。 自然语言处理是人工智能&#xff08;AI&#xff09;领域中的一个重要分支&#xff0c;它结合了计算机科学、语言学和统计学的方法&#xff0c;通过算法对文本和语音进行分析&#xff0c;使计算机能够理解、解…...

win10电脑 定时关机

win10电脑 定时关机 https://weibo.com/ttarticle/p/show?id2309405110707766296723 二、使用任务计划程序设置定时关机打开任务计划程序&#xff1a; 按下“Win S”组合键&#xff0c;打开搜索框。 在搜索框中输入“任务计划程序”&#xff0c;然后点击搜索结果中的“任务…...

linux删除用户

1、查看账号 cat /etc/passwd 查看所有用户账号信息&#xff1a;该文件记录了系统中的所有用户账号信息&#xff0c;包括用户名、用户ID、用户所属组等。 2、删除账号 基本删除&#xff1a;使用userdel命令删除用户账号&#xff0c;格式为userdel [选项] 用户名。如果不加任…...

FPGA的 基本结构(Xilinx 公司Virtex-II 系列FPGA )

以Xilinx 公司Virtex-II 系列FPGA 为例&#xff0c;其基本结构由下图所示。它是主要由两大部分组成&#xff1a;可编程输入/输出&#xff08;Programmable I/Os&#xff09;部分和内部可配置&#xff08;Configurable Logic&#xff09;部分。 可编程输入/输出&#xff08;I/Os…...

Springboot项目如何消费Kafka数据

目录 一、引入依赖二、添加Kafka配置三、创建 Kafka 消费者&#xff08;一&#xff09;Kafka生产的消息是JSON 字符串1、方式一2、方式二&#xff1a;需要直接访问消息元数据 &#xff08;二&#xff09;Kafka生产的消息是对象Order 四、创建 启动类五、配置 Kafka 生产者&…...

LeetCode 热题 100 | 子串

子串基础 前缀和&#xff1a;前面的数加在一起等于多少&#xff0c;放进map里&#xff0c;key为和&#xff0c;value为这个和出现的次数。单调队列&#xff1a;单调递增/递减队列&#xff0c;每次加入新元素&#xff0c;比新元素大/小的元素全部弹出。滑动窗口&#xff1a;两层…...

深度学习笔记11-优化器对比实验(Tensorflow)

&#x1f368; 本文为&#x1f517;365天深度学习训练营中的学习记录博客&#x1f356; 原作者&#xff1a;K同学啊 目录 一、导入数据并检查 二、配置数据集 三、数据可视化 四、构建模型 五、训练模型 六、模型对比评估 七、总结 一、导入数据并检查 import pathlib,…...

【掌握 JavaScript 数组迭代:map 和 includes 的使用技巧】

map map()方法是数组原型的一个函数&#xff0c;用于对数组的每个元素执行一个函数&#xff0c;并返回一个新的数组&#xff0c;其中包含么哦一个元素执行的结果。 语法 const newArray array.map(callback(currentValue, index, arr), thisValue)参数 callback&#xff1…...

深入浅出 Android AES 加密解密:从理论到实战

深入浅出 Android AES 加密解密&#xff1a;从理论到实战 在现代移动应用中&#xff0c;数据安全是不可忽视的一环。无论是用户隐私保护&#xff0c;还是敏感信息的存储与传输&#xff0c;加密技术都扮演着重要角色。本文将以 AES&#xff08;Advanced Encryption Standard&am…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

如何在网页里填写 PDF 表格?

有时候&#xff0c;你可能希望用户能在你的网站上填写 PDF 表单。然而&#xff0c;这件事并不简单&#xff0c;因为 PDF 并不是一种原生的网页格式。虽然浏览器可以显示 PDF 文件&#xff0c;但原生并不支持编辑或填写它们。更糟的是&#xff0c;如果你想收集表单数据&#xff…...

USB Over IP专用硬件的5个特点

USB over IP技术通过将USB协议数据封装在标准TCP/IP网络数据包中&#xff0c;从根本上改变了USB连接。这允许客户端通过局域网或广域网远程访问和控制物理连接到服务器的USB设备&#xff08;如专用硬件设备&#xff09;&#xff0c;从而消除了直接物理连接的需要。USB over IP的…...

Python 包管理器 uv 介绍

Python 包管理器 uv 全面介绍 uv 是由 Astral&#xff08;热门工具 Ruff 的开发者&#xff09;推出的下一代高性能 Python 包管理器和构建工具&#xff0c;用 Rust 编写。它旨在解决传统工具&#xff08;如 pip、virtualenv、pip-tools&#xff09;的性能瓶颈&#xff0c;同时…...

动态 Web 开发技术入门篇

一、HTTP 协议核心 1.1 HTTP 基础 协议全称 &#xff1a;HyperText Transfer Protocol&#xff08;超文本传输协议&#xff09; 默认端口 &#xff1a;HTTP 使用 80 端口&#xff0c;HTTPS 使用 443 端口。 请求方法 &#xff1a; GET &#xff1a;用于获取资源&#xff0c;…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

在 Visual Studio Code 中使用驭码 CodeRider 提升开发效率:以冒泡排序为例

目录 前言1 插件安装与配置1.1 安装驭码 CodeRider1.2 初始配置建议 2 示例代码&#xff1a;冒泡排序3 驭码 CodeRider 功能详解3.1 功能概览3.2 代码解释功能3.3 自动注释生成3.4 逻辑修改功能3.5 单元测试自动生成3.6 代码优化建议 4 驭码的实际应用建议5 常见问题与解决建议…...

aardio 自动识别验证码输入

技术尝试 上周在发学习日志时有网友提议“在网页上识别验证码”&#xff0c;于是尝试整合图像识别与网页自动化技术&#xff0c;完成了这套模拟登录流程。核心思路是&#xff1a;截图验证码→OCR识别→自动填充表单→提交并验证结果。 代码在这里 import soImage; import we…...