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

994. 腐烂的橘子

994. 腐烂的橘子(面试题打卡/前缀和/简单)

来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rotting-oranges/

题干:

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

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

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

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

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 仅为 012

示例:

输入:grid = [[2,1,1],[1,1,0],[0,1,1]]
输出:4输入:grid = [[2,1,1],[0,1,1],[1,0,1]]
输出:-1
解释:左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。输入:grid = [[0,2]]
输出:0
解释:因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0

题解:

广度优先遍历:

使用一个队列来保存腐烂橘子的坐标。首先,遍历整个网格,将腐烂橘子的坐标加入队列,并统计新鲜橘子的数量。然后,开始进行腐烂,每一轮从队列中取出腐烂橘子的坐标,遍历其四个方向,将新鲜橘子标记为腐烂,并将其坐标加入队列。每一轮腐烂后,分钟数加一。最后,如果还有新鲜橘子剩余,则返回 -1,否则返回腐烂的分钟数。

class Solution {public static int orangesRotting(int[][] grid) {int n = grid.length, m = grid[0].length;// 记录新鲜橘子数int freshOranges = 0;// 保存腐烂橘子的坐标Queue<int[]> queue = new LinkedList<>();// 遍历网格,将腐烂橘子坐标入队,并统计新鲜橘子数量for (int i = 0; i < n; i++) {for (int j = 0; j < m; j++) {if (grid[i][j] == 2) {queue.offer(new int[]{i, j});} else if (grid[i][j] == 1) {freshOranges++;}}}// 如果没有新鲜橘子,则不需要进行腐烂if (freshOranges == 0) {return 0;}int minutes = -1;int[] dx = {-1, 0, 1, 0}, dy = {0, 1, 0, -1};// 开始腐烂while (!queue.isEmpty()) {int size = queue.size();for (int i = 0; i < size; i++) {int[] orange = queue.poll();// 上下左右for (int j = 0; j < 4; j++) {int x = orange[0] + dx[j], y = orange[1] + dy[j];// 如果新的坐标越界或不是新鲜橘子,则越过if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != 1) {continue;}// 将新鲜橘子标记为腐烂,并入队grid[x][y] = 2;queue.offer(new int[]{x, y});freshOranges--;}}// 每一轮腐烂后,分钟数加一minutes++;}// 如果还有新鲜橘子剩余,则返回 -1if (freshOranges > 0) {return -1;}// 返回腐烂的分钟数return minutes;}
}

相关文章:

994. 腐烂的橘子

994. 腐烂的橘子(面试题打卡/前缀和/简单) 来源&#xff1a;力扣&#xff08;LeetCode&#xff09; 链接&#xff1a;https://leetcode.cn/problems/rotting-oranges/ 题干&#xff1a; 在给定的 m x n 网格 grid 中&#xff0c;每个单元格可以有以下三个值之一&#xff1a;…...

Rx.NET in Action 第三章学习笔记

3 C#函数式编程思想 本章内容包括 将 C# 与函数式技术相结合使用委托和 lambda 表达式使用 LINQ 查询集合 面向对象编程为程序开发提供了巨大的生产力。它将复杂的系统分解为类&#xff0c;使项目更易于管理&#xff0c;而对象则是一个个孤岛&#xff0c;你可以集中精力分别处理…...

Windows11环境下VS2019调用Pytorch语义分割模型(C++版)

语义分割模型在训练时往往采用python脚本进行网络搭建和训练&#xff0c;并获得训练好的模型。为了提高效率方便整个工程项目部署&#xff0c;实际工程应用中通常希望使用C编程语言调用训练好的网络模型。查询大量网络资料并踩过无数坑后&#xff0c;经实际测试实现了在window1…...

Milkv Duo 以太网使用与配置

网络配置 使能网卡 使用ip link查看是否存在eth0网卡&#xff0c;若无使用如下命令使能网卡&#xff1a; ip link set eth0 up两次使用ip link确认网卡eth0已经使能。 配置IP、gws 本人设备连接到华为路由器下&#xff0c;故增加如下路由信息&#xff1a; ip route add d…...

bash: make: command not found

make之后报错信息如下&#xff1a;cd 对应的文件路径后 make 发现报错&#xff1a;bash: make: command not found 这个原因可能是没有安装make工具,也可能是安装了make之后,没有将make的文件路径添加到系统环境变量中 有没有安装make,可以使用Search Everything搜索是否有make…...

热点如何用于期刊写作——以chatGPT为例

交叉领域A&#xff0c;B 以自己为例子&#xff0c;A是教育 B是技术&#xff0c;我是教育技术学专业。 经验来源 知网关于GPT的140余篇专业论文的观察 截止至2023年8月14日15:35:45 学习每出现一个热点&#xff0c;如何应用于学术。 实践阅读发现 套路一&#xff1a;谈理论…...

IGV.js 的完全本地化运行探索

问题及解决方法 IGV.js 完全本地化是为了合规&#xff0c;不使用外网的情况下查看基因组。不联网需要下载 genomes.json 文件及其中的内容之外&#xff0c;还需要修改 igv.js本身&#xff0c;防止5s超时后才显示网页内容。修改的关键词是: genomes.json&#xff0c;改为本地的…...

网络安全渗透测试之靶场训练

NWES: 7月26号武汉地震检测中心遭受境外具有政府背景的黑客组织和不法分子的网络攻击。 目前网络攻击主要来自以下几种方式: DDOS&#xff1a;分布式拒绝服务攻击。通过制造大量无用的请求向目标服务器发起访问&#xff0c;使其因短时间内无法处理大量请求而陷入瘫痪。主要针对…...

Java课题笔记~ Spring 的事务管理

一、Spring 的事务管理 事务原本是数据库中的概念&#xff0c;在 Dao 层。但一般情况下&#xff0c;需要将事务提升到业务层&#xff0c;即 Service 层。这样做是为了能够使用事务的特性来管理具体的业务。 在 Spring 中通常可以通过以下两种方式来实现对事务的管理&#xff…...

仿到位|独立版家政上门预约服务小程序家政保洁师傅上门服务小程序上门服务在线派单源码

上门预约服务派单小程序家政 小程序 同城预约 开源代码 独立版. 程序完整,经过安装检测,可放心下载安装。 适合本地的一款上门预约服务小程序,功能丰富,适用多种场景。 程序功能:城市管理/小程序DIY/服务订单/师傅管理/会员卡功能/营销功能/文章功能等等...

Observability:识别生成式 AI 搜索体验中的慢速查询

作者&#xff1a;Philipp Kahr Elasticsearch Service 用户的重要注意事项&#xff1a;目前&#xff0c;本文中描述的 Kibana 设置更改仅限于 Cloud 控制台&#xff0c;如果没有我们支持团队的手动干预&#xff0c;则无法进行配置。 我们的工程团队正在努力消除对这些设置的限制…...

接口测试及接口抓包常用的测试工具

接口 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换&#xff0c;传递和控制管理过程&#xff0c;以及系统间的相互逻辑依赖关系等。 接口测试的重要性 是节省时间前后端不…...

CH342/CH343/CH344/CH347/CH9101/CH9102/CH9103/CH9104 Linux串口驱动使用教程

CH343 Linux串口驱动 ch343ser_linux 支持USB转串口芯片 ch342/ch343/ch344/ch347/ch9101/ch9102/ch9103/ch9104等 &#xff0c;同时该驱动配合ch343_lib库还提供了芯片GPIO接口的读写功能&#xff0c;内部EEPROM的信息配置和读取功能等。 芯片型号串口数量GPIO数量CH342F/K2C…...

反射和工厂设计模式---工厂设计模式

一、工厂设计模式概述 ■什么是工厂设计模式 工厂模式(Factory Pattern)是开发中比较常用的设计模式之一。 它属于创建型模式(单例模式就是创建型模式的一种)&#xff0c;这种模式让我们在创建对象时不会直接暴露创建逻辑&#xff0c;而是通过使用一个共同的接口来完成对象的…...

【算法——双指针】LeetCode 283 移动零

题目描述&#xff1a; 思路&#xff1a; (双指针) O(n)O(n)O(n) 给定一个数组 nums&#xff0c;要求我们将所有的 0 移动到数组的末尾&#xff0c;同时保持非零元素的相对顺序。 如图所示&#xff0c;数组nums [0,1,0,3,12]&#xff0c;移动完成后变成nums [1,3,12,0,0] &am…...

腾讯云轻量服务器和云服务器的CPU处理器有差别吗?

腾讯云轻量应用服务器和CVM云服务器的CPU处理器性能有差别吗&#xff1f;创建轻量应用服务器时不支持指定底层物理服务器的CPU型号&#xff0c;腾讯云将随机分配满足套餐规格的物理CPU型号&#xff0c;通常优先选择较新代次的CPU型号。而云服务器CVM的CPU处理器型号、主频都是有…...

Redis_亿级访问量数据处理

11. 亿级访问量数据处理 11.1 场景表述 手机APP用户登录信息&#xff0c;一天用户登录ID或设备ID电商或者美团平台&#xff0c;一个商品对应的评论文章对应的评论APP上有打卡信息网站上访问量统计统计新增用户第二天还留存商品评论的排序月活统计统计独立访客(Unique Vistito…...

Java-类型和变量(基于C语言的补充)

一个简单的Java程序 args){ System.out.println("Hello,world"); } }通过上述代码&#xff0c;我们可以看到一个完整的Java程序的结构&#xff0c;Java程序的结构由如下三个部分组成&#xff1a; 1.源文件&#xff08;扩展名为*.java)&#xff1a;源文件带有类的定义…...

机器学习笔记:李宏毅diffusion model

1 概念原理 首先sample 一个都是噪声的vector然后经过denoise network 过滤一些杂质接着继续不断denoise&#xff0c;直到最后出来一张清晰图片 【类似于做雕塑&#xff0c;一开始只是一块石头&#xff08;噪声很杂的雕塑&#xff09;&#xff0c;慢慢雕刻出想要的花纹】 同一个…...

STM32--TIM定时器(2)

文章目录 输出比较PWM输出比较通道参数计算舵机简介直流电机简介TB6612 PWM基本结构PWM驱动呼吸灯PWM驱动舵机PWM控制电机 输出比较 输出比较&#xff0c;简称OC&#xff08;Output Compare&#xff09;。 输出比较的原理是&#xff0c;当定时器计数值与比较值相等或者满足某种…...

MFC内存泄露

1、泄露代码示例 void X::SetApplicationBtn() {CMFCRibbonApplicationButton* pBtn GetApplicationButton();// 获取 Ribbon Bar 指针// 创建自定义按钮CCustomRibbonAppButton* pCustomButton new CCustomRibbonAppButton();pCustomButton->SetImage(IDB_BITMAP_Jdp26)…...

Java - Mysql数据类型对应

Mysql数据类型java数据类型备注整型INT/INTEGERint / java.lang.Integer–BIGINTlong/java.lang.Long–––浮点型FLOATfloat/java.lang.FloatDOUBLEdouble/java.lang.Double–DECIMAL/NUMERICjava.math.BigDecimal字符串型CHARjava.lang.String固定长度字符串VARCHARjava.lang…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

力扣热题100 k个一组反转链表题解

题目: 代码: func reverseKGroup(head *ListNode, k int) *ListNode {cur : headfor i : 0; i < k; i {if cur nil {return head}cur cur.Next}newHead : reverse(head, cur)head.Next reverseKGroup(cur, k)return newHead }func reverse(start, end *ListNode) *ListN…...

从 GreenPlum 到镜舟数据库:杭银消费金融湖仓一体转型实践

作者&#xff1a;吴岐诗&#xff0c;杭银消费金融大数据应用开发工程师 本文整理自杭银消费金融大数据应用开发工程师在StarRocks Summit Asia 2024的分享 引言&#xff1a;融合数据湖与数仓的创新之路 在数字金融时代&#xff0c;数据已成为金融机构的核心竞争力。杭银消费金…...

MySQL 主从同步异常处理

阅读原文&#xff1a;https://www.xiaozaoshu.top/articles/mysql-m-s-update-pk MySQL 做双主&#xff0c;遇到的这个错误&#xff1a; Could not execute Update_rows event on table ... Error_code: 1032是 MySQL 主从复制时的经典错误之一&#xff0c;通常表示&#xff…...

图解JavaScript原型:原型链及其分析 | JavaScript图解

​​ 忽略该图的细节&#xff08;如内存地址值没有用二进制&#xff09; 以下是对该图进一步的理解和总结 1. JS 对象概念的辨析 对象是什么&#xff1a;保存在堆中一块区域&#xff0c;同时在栈中有一块区域保存其在堆中的地址&#xff08;也就是我们通常说的该变量指向谁&…...

【若依】框架项目部署笔记

参考【SpringBoot】【Vue】项目部署_no main manifest attribute, in springboot-0.0.1-sn-CSDN博客 多一个redis安装 准备工作&#xff1a; 压缩包下载&#xff1a;http://download.redis.io/releases 1. 上传压缩包&#xff0c;并进入压缩包所在目录&#xff0c;解压到目标…...