994. 腐烂的橘子
994. 腐烂的橘子(面试题打卡/前缀和/简单)
来源:力扣(LeetCode)
链接:https://leetcode.cn/problems/rotting-oranges/
题干:
在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:
- 值
0代表空单元格; - 值
1代表新鲜橘子; - 值
2代表腐烂的橘子。
每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。
返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。
提示:
m == grid.lengthn == grid[i].length1 <= m, n <= 10grid[i][j]仅为0、1或2
示例:
输入: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. 腐烂的橘子(面试题打卡/前缀和/简单) 来源:力扣(LeetCode) 链接:https://leetcode.cn/problems/rotting-oranges/ 题干: 在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:…...
Rx.NET in Action 第三章学习笔记
3 C#函数式编程思想 本章内容包括 将 C# 与函数式技术相结合使用委托和 lambda 表达式使用 LINQ 查询集合 面向对象编程为程序开发提供了巨大的生产力。它将复杂的系统分解为类,使项目更易于管理,而对象则是一个个孤岛,你可以集中精力分别处理…...
Windows11环境下VS2019调用Pytorch语义分割模型(C++版)
语义分割模型在训练时往往采用python脚本进行网络搭建和训练,并获得训练好的模型。为了提高效率方便整个工程项目部署,实际工程应用中通常希望使用C编程语言调用训练好的网络模型。查询大量网络资料并踩过无数坑后,经实际测试实现了在window1…...
Milkv Duo 以太网使用与配置
网络配置 使能网卡 使用ip link查看是否存在eth0网卡,若无使用如下命令使能网卡: ip link set eth0 up两次使用ip link确认网卡eth0已经使能。 配置IP、gws 本人设备连接到华为路由器下,故增加如下路由信息: ip route add d…...
bash: make: command not found
make之后报错信息如下:cd 对应的文件路径后 make 发现报错:bash: make: command not found 这个原因可能是没有安装make工具,也可能是安装了make之后,没有将make的文件路径添加到系统环境变量中 有没有安装make,可以使用Search Everything搜索是否有make…...
热点如何用于期刊写作——以chatGPT为例
交叉领域A,B 以自己为例子,A是教育 B是技术,我是教育技术学专业。 经验来源 知网关于GPT的140余篇专业论文的观察 截止至2023年8月14日15:35:45 学习每出现一个热点,如何应用于学术。 实践阅读发现 套路一:谈理论…...
IGV.js 的完全本地化运行探索
问题及解决方法 IGV.js 完全本地化是为了合规,不使用外网的情况下查看基因组。不联网需要下载 genomes.json 文件及其中的内容之外,还需要修改 igv.js本身,防止5s超时后才显示网页内容。修改的关键词是: genomes.json,改为本地的…...
网络安全渗透测试之靶场训练
NWES: 7月26号武汉地震检测中心遭受境外具有政府背景的黑客组织和不法分子的网络攻击。 目前网络攻击主要来自以下几种方式: DDOS:分布式拒绝服务攻击。通过制造大量无用的请求向目标服务器发起访问,使其因短时间内无法处理大量请求而陷入瘫痪。主要针对…...
Java课题笔记~ Spring 的事务管理
一、Spring 的事务管理 事务原本是数据库中的概念,在 Dao 层。但一般情况下,需要将事务提升到业务层,即 Service 层。这样做是为了能够使用事务的特性来管理具体的业务。 在 Spring 中通常可以通过以下两种方式来实现对事务的管理ÿ…...
仿到位|独立版家政上门预约服务小程序家政保洁师傅上门服务小程序上门服务在线派单源码
上门预约服务派单小程序家政 小程序 同城预约 开源代码 独立版. 程序完整,经过安装检测,可放心下载安装。 适合本地的一款上门预约服务小程序,功能丰富,适用多种场景。 程序功能:城市管理/小程序DIY/服务订单/师傅管理/会员卡功能/营销功能/文章功能等等...
Observability:识别生成式 AI 搜索体验中的慢速查询
作者:Philipp Kahr Elasticsearch Service 用户的重要注意事项:目前,本文中描述的 Kibana 设置更改仅限于 Cloud 控制台,如果没有我们支持团队的手动干预,则无法进行配置。 我们的工程团队正在努力消除对这些设置的限制…...
接口测试及接口抓包常用的测试工具
接口 接口测试是测试系统组件间接口的一种测试。接口测试主要用于检测外部系统与系统之间以及内部各个子系统之间的交互点。测试的重点是要检查数据的交换,传递和控制管理过程,以及系统间的相互逻辑依赖关系等。 接口测试的重要性 是节省时间前后端不…...
CH342/CH343/CH344/CH347/CH9101/CH9102/CH9103/CH9104 Linux串口驱动使用教程
CH343 Linux串口驱动 ch343ser_linux 支持USB转串口芯片 ch342/ch343/ch344/ch347/ch9101/ch9102/ch9103/ch9104等 ,同时该驱动配合ch343_lib库还提供了芯片GPIO接口的读写功能,内部EEPROM的信息配置和读取功能等。 芯片型号串口数量GPIO数量CH342F/K2C…...
反射和工厂设计模式---工厂设计模式
一、工厂设计模式概述 ■什么是工厂设计模式 工厂模式(Factory Pattern)是开发中比较常用的设计模式之一。 它属于创建型模式(单例模式就是创建型模式的一种),这种模式让我们在创建对象时不会直接暴露创建逻辑,而是通过使用一个共同的接口来完成对象的…...
【算法——双指针】LeetCode 283 移动零
题目描述: 思路: (双指针) O(n)O(n)O(n) 给定一个数组 nums,要求我们将所有的 0 移动到数组的末尾,同时保持非零元素的相对顺序。 如图所示,数组nums [0,1,0,3,12],移动完成后变成nums [1,3,12,0,0] &am…...
腾讯云轻量服务器和云服务器的CPU处理器有差别吗?
腾讯云轻量应用服务器和CVM云服务器的CPU处理器性能有差别吗?创建轻量应用服务器时不支持指定底层物理服务器的CPU型号,腾讯云将随机分配满足套餐规格的物理CPU型号,通常优先选择较新代次的CPU型号。而云服务器CVM的CPU处理器型号、主频都是有…...
Redis_亿级访问量数据处理
11. 亿级访问量数据处理 11.1 场景表述 手机APP用户登录信息,一天用户登录ID或设备ID电商或者美团平台,一个商品对应的评论文章对应的评论APP上有打卡信息网站上访问量统计统计新增用户第二天还留存商品评论的排序月活统计统计独立访客(Unique Vistito…...
Java-类型和变量(基于C语言的补充)
一个简单的Java程序 args){ System.out.println("Hello,world"); } }通过上述代码,我们可以看到一个完整的Java程序的结构,Java程序的结构由如下三个部分组成: 1.源文件(扩展名为*.java):源文件带有类的定义…...
机器学习笔记:李宏毅diffusion model
1 概念原理 首先sample 一个都是噪声的vector然后经过denoise network 过滤一些杂质接着继续不断denoise,直到最后出来一张清晰图片 【类似于做雕塑,一开始只是一块石头(噪声很杂的雕塑),慢慢雕刻出想要的花纹】 同一个…...
STM32--TIM定时器(2)
文章目录 输出比较PWM输出比较通道参数计算舵机简介直流电机简介TB6612 PWM基本结构PWM驱动呼吸灯PWM驱动舵机PWM控制电机 输出比较 输出比较,简称OC(Output Compare)。 输出比较的原理是,当定时器计数值与比较值相等或者满足某种…...
Oracle查询表空间大小
1 查询数据库中所有的表空间以及表空间所占空间的大小 SELECTtablespace_name,sum( bytes ) / 1024 / 1024 FROMdba_data_files GROUP BYtablespace_name; 2 Oracle查询表空间大小及每个表所占空间的大小 SELECTtablespace_name,file_id,file_name,round( bytes / ( 1024 …...
从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)
设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile,新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
C++八股 —— 单例模式
文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全(Thread Safety) 线程安全是指在多线程环境下,某个函数、类或代码片段能够被多个线程同时调用时,仍能保证数据的一致性和逻辑的正确性…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Java毕业设计:WML信息查询与后端信息发布系统开发
JAVAWML信息查询与后端信息发布系统实现 一、系统概述 本系统基于Java和WML(无线标记语言)技术开发,实现了移动设备上的信息查询与后端信息发布功能。系统采用B/S架构,服务器端使用Java Servlet处理请求,数据库采用MySQL存储信息࿰…...
比较数据迁移后MySQL数据库和OceanBase数据仓库中的表
设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...
为什么要创建 Vue 实例
核心原因:Vue 需要一个「控制中心」来驱动整个应用 你可以把 Vue 实例想象成你应用的**「大脑」或「引擎」。它负责协调模板、数据、逻辑和行为,将它们变成一个活的、可交互的应用**。没有这个实例,你的代码只是一堆静态的 HTML、JavaScript 变量和函数,无法「活」起来。 …...
MySQL 索引底层结构揭秘:B-Tree 与 B+Tree 的区别与应用
文章目录 一、背景知识:什么是 B-Tree 和 BTree? B-Tree(平衡多路查找树) BTree(B-Tree 的变种) 二、结构对比:一张图看懂 三、为什么 MySQL InnoDB 选择 BTree? 1. 范围查询更快 2…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
