算法---腐烂的橘子

题目

在给定的 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

解决方法

    fun orangesRotting(grid: Array<IntArray>): Int {//统计有几个没坏的var notBad = 0//把坏的坐标记录进队列val listBad = LinkedList<IntArray>()val bad = 2val good = 1grid.forEachIndexed { row, ints ->ints.forEachIndexed { col, i ->when (i) {good -> {notBad++}bad -> {listBad += intArrayOf(row, col)}else -> {}}}}var direction = arrayOf(intArrayOf(0, -1),intArrayOf(-1, 0),intArrayOf(0, 1),intArrayOf(1, 0),)//记录轮次var count = 0//不停的取出来while (listBad.isNotEmpty() && notBad != 0) {val size = listBad.sizefor (i in 1..size) {val first = listBad.pollFirst()for (array in direction) {if (first[0] + array[0] in grid.indices && first[1] + array[1] in grid[0].indices) {when (grid[first[0] + array[0]][first[1] + array[1]]) {good -> {listBad.addLast(intArrayOf(first[0] + array[0], first[1] + array[1]))grid[first[0] + array[0]][first[1] + array[1]] = 2notBad--}bad -> {//不是我传染的 我不应该管吧 不然死循环了}else -> {}}}}}count++}//判断没坏的是不是等于0 等于0 返回次数 否则返回-1return if (notBad == 0) count else -1}

总结

1.注意:当传播到最后一轮,只要没有了好橘子,那么就算队列里面不是空的,也没有必要继续传播了。

这么难得题,我竟然想法完全没错。我真猛啊

现在面试算法不成大问题了,但是感觉项目经历亮点不够,导致不太好找。
慢慢来吧,算法不能丢,项目慢慢做。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/200818.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

详解Python Tornado框架写一个Web应用全过程

Tornado是什么 之前在看Jupyter组件的源码的时候&#xff0c;发现了tornado这个web框架。 不仅仅做一个web框架&#xff0c; 通过使用非阻塞网络I/O&#xff0c;Tornado可以扩展到数万个开放连接。 这样非常适合 long polling &#xff0c; WebSockets 以及其他需要与每个用户…

2019ICPC南京站

A A Hard Problem 题意&#xff1a;给定一个正整数 n &#xff0c;你需要找出最小整数 k&#xff0c;满足&#xff1a;从{1,2,⋯,n}中任意选择长度为k的子集&#xff0c;存在两个不同的整数 u,v∈T, 且 u 是 v 的因数。 思路&#xff1a;打表找规律 #include <bits/std…

深入解析数据结构与算法之堆

文章目录 &#x1f966;引言&#xff1a;&#x1f966;什么是堆&#x1f966;大顶堆与小顶堆&#x1f9c4;大顶堆&#xff08;Max Heap&#xff09;&#x1f9c4;小顶堆&#xff08;Min Heap&#xff09; &#x1f966;堆的表示&#x1f9c4;数组表示&#xff1a;&#x1f9c4;…

ROS2串口通讯serial库(适用于humble版本)

要的串口操作的API介绍在这里&#xff1a;serial: serial::Serial Class Reference (wjwwood.io) 但是我们不是直接利用上面这个东西&#xff0c;而是使用的是根据这个改写的一个针对ros2的一个serial库&#xff0c;这个serial库是根据上面这个库改写来的&#xff0c;ros2的库在…

渗透测试高级技巧(一):分析验签与前端加密

“开局一个登录框” 在黑盒的安全测试的工作开始的时候&#xff0c;打开网站一般来说可能仅仅是一个登录框&#xff1b;很多时候这种系统往往都是自研或者一些业务公司专门研发。最基础的情况下&#xff0c;我们会尝试使用 SQL 注入绕过或者爆破之类的常规手段&#xff0c;如果…

【STM32】TF卡FTA32文件系统

一、SD卡介绍 1.SD简介 本质&#xff1a;NandFlash控制芯片 2.SD卡存储容量等级 3.FAT文件系统的使用 4.SD卡速度等级 5.SD卡驱动方式 1.SDIO&&SD 1&#xff09;SDIO接口通信线&#xff1a;CLK/CMD/DAT0-3&#xff08;数据传输线4根&#xff09; 2&#xff09;SPI接口…

CodeWhisperer 一款好玩的 AI 插件

忙里抽闲&#xff0c;今天试了试 CodeWhisperer 这款插件&#xff0c;我是在 IDEA 中做的测试&#xff0c;下面是我的一些使用感想&#xff1a; 安装 CodeWhisperer 插件&#xff1a;在 IntelliJ IDEA 中&#xff0c;可以通过插件管理器安装 CodeWhisperer 插件&#xff0c;然…

基于Cortex®-M4F的TM4C123GH6NMRT7R 32位MCU,LM74900QRGERQ1、LM74930QRGERQ1汽车类理想二极管

一、TM4C123GH6NMRT7R IC MCU 32BIT 256KB FLASH 157BGA Tiva™C系列微控制器为设计人员提供了基于ARMCortex™-M的高性能架构&#xff0c;该架构具有广泛的集成功能以及强大的软件和开发工具生态系统。以性能和灵活性为目标&#xff0c;Tiva™C系列架构提供了一个具有FPU的80…

汽车托运汽车会产生公里数吗?

汽车托运&#xff0c;顾名思义就是把汽车放在板车上进行托运&#xff0c;既然是被托运&#xff0c;那为什么还会产生公里数呢?是被司机私用了吗?还是被当成租赁工具租借出去了呢? 其实不然&#xff0c;回到托运流程里&#xff0c;特别是大板车&#xff0c;我们的线路有很多需…

Redis(事务和持久化)(很重要!)

事务的定义&#xff1a; Redis中的事务是指一组命令的集合&#xff0c;这些命令可以在一个原子操作中执行。在Redis中&#xff0c;可以使用MULTI命令开始一个事务&#xff0c;然后使用EXEC命令来执行事务中的所有命令&#xff0c;或者使用DISCARD命令来取消事务。事务可以确保…

ERP对接淘宝/天猫/京东/拼多多商品详情数据API接口

引言 今天&#xff0c;我们时代变化非常快&#xff0c;传统行业做法&#xff0c;已经无法完全适应时代的发展。互联网的发展&#xff0c;造成了一股网购热。京东&#xff0c;天猫&#xff0c;淘宝&#xff0c;易购……网购&#xff0c;给我们生活带来了方便&#xff0c;消费者…

亚马逊第二个大语言模型 Olympus 即将上线

据外媒爆料&#xff0c;亚马逊正在训练他的第二个大语言模型——Olympus&#xff0c;很有可能在今年12月份上线。亚马逊计划将Olympus接入在线零售商店、Echo等设备上的Alexa语音助手&#xff0c;并为AWS平台提供新的功能。据说这个大语言模型规模达到2万亿&#xff08;2000B&a…

排序算法--冒泡排序

实现逻辑 ① 比较相邻的元素。如果第一个比第二个大&#xff0c;就交换他们两个。 ②对每一对相邻元素作同样的工作&#xff0c;从开始第一对到结尾的最后一对。在这一点&#xff0c;最后的元素应该会是最大的数。 ③针对所有的元素重复以上的步骤&#xff0c;除了最后一个。 ④…

java+springboot+bootstrap校园闲置物品拍卖交易平台_ngad7-

根据日常实际需要&#xff0c;一方面需要在系统中实现基础信息的管理&#xff0c;同时还需要结合实际情况的需要&#xff0c;提供校园闲置物品交易管理功能&#xff0c;方便校园闲置物品交易管理工作的展开&#xff0c;综合考虑&#xff0c;本套系统应该满足如下要求&#xff1…

Navicat DML 操作

在表格种插入 列信息 -- 修改数据 update 表名 set 列名 值1, 列名值2,[where 条件]; -- 注意&#xff1a;如果update语句没有加where 表里对应行的全部信息都会被改; -- 删除数据 delecte from 表名 [where 条件]; 未删除前&#xff1a; 执行删除后为&#xff1a; DQL - 条…

Apache Hive源码阅读环境搭建

前置软件&#xff1a; JDK 1.8 Maven 3.3.9 1 下载源码 # 下载源码 git clone https://github.com/apache/hive.gitcd hive# 查看标签 git tag# 切换到要阅读的指定版本的tag git checkout rel/release-2.1.02 编译源码 mvn clean install -DskipTests执行报错 日志如下 E…

Java精品项目源码基于SpringBoot的樱花短视频平台(v66)

Java精品项目源码基于SpringBoot的樱花短视频平台(v66) 大家好&#xff0c;小辰今天给大家介绍一个樱花短视频平台&#xff0c;演示视频公众号&#xff08;小辰哥的Java&#xff09;对号查询观看即可 文章目录 Java精品项目源码基于SpringBoot的樱花短视频平台(v66)难度指数&…

基础课8——中文分词

中文分词指的是将一个汉字序列切分成一个一个单独的词。分词就是将连续的字序列按照一定的规范重新组合成词序列的过程。在英文的行文中&#xff0c;单词之间是以空格作为自然分界符的&#xff0c;而中文只是字、句和段能通过明显的分界符来简单划界&#xff0c;唯独词没有一个…

[vxe-table] expandAll:true 当table数据更新后无法展开,只有第一次能展开才能生效的问题

:tree-config"{rowField: id,parentField: parentId,expandAll: true,reserve: true, }" :row-config"{ keyField: id, isHover: true }"参考&#xff1a; vxe tree expandAll&#xff1a;true当table数据更新后无法展开&#xff0c;只有第一次能展开才能…

go-zero微服务的使用

一、入门案例 1、使用goland创建一个工程 2、新建一个user.proto syntax "proto3";package user; // 这个地方表示生成的go的包名叫user option go_package "./user";message UserInfoRequest {int64 userId 1; }message UserInfoResponse {int64 user…