当前位置: 首页 > 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;当定时器计数值与比较值相等或者满足某种…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

FastAPI 教程:从入门到实践

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

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…...

Redis数据倾斜问题解决

Redis 数据倾斜问题解析与解决方案 什么是 Redis 数据倾斜 Redis 数据倾斜指的是在 Redis 集群中&#xff0c;部分节点存储的数据量或访问量远高于其他节点&#xff0c;导致这些节点负载过高&#xff0c;影响整体性能。 数据倾斜的主要表现 部分节点内存使用率远高于其他节…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

让回归模型不再被异常值“带跑偏“,MSE和Cauchy损失函数在噪声数据环境下的实战对比

在机器学习的回归分析中&#xff0c;损失函数的选择对模型性能具有决定性影响。均方误差&#xff08;MSE&#xff09;作为经典的损失函数&#xff0c;在处理干净数据时表现优异&#xff0c;但在面对包含异常值的噪声数据时&#xff0c;其对大误差的二次惩罚机制往往导致模型参数…...

vulnyx Blogger writeup

信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面&#xff0c;gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress&#xff0c;说明目标所使用的cms是wordpress&#xff0c;访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...

Kafka主题运维全指南:从基础配置到故障处理

#作者&#xff1a;张桐瑞 文章目录 主题日常管理1. 修改主题分区。2. 修改主题级别参数。3. 变更副本数。4. 修改主题限速。5.主题分区迁移。6. 常见主题错误处理常见错误1&#xff1a;主题删除失败。常见错误2&#xff1a;__consumer_offsets占用太多的磁盘。 主题日常管理 …...

嵌入式学习之系统编程(九)OSI模型、TCP/IP模型、UDP协议网络相关编程(6.3)

目录 一、网络编程--OSI模型 二、网络编程--TCP/IP模型 三、网络接口 四、UDP网络相关编程及主要函数 ​编辑​编辑 UDP的特征 socke函数 bind函数 recvfrom函数&#xff08;接收函数&#xff09; sendto函数&#xff08;发送函数&#xff09; 五、网络编程之 UDP 用…...