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

LeetCode994.腐烂的橘子

 看完题我觉得这不是和上一道岛屿的题一样简单嘛,然后写了将近2个小时才写出来,我的思路就是,用check()先对grid检查一下,是否有以下情况:

(如果有1的周围都是空,则这个位置用不腐烂,返回-1; 如果全是1,返回永不腐烂,返回-1;如果没有2,永不腐烂,则返回-1),

定义一个hasFresh()方法看grid中是不是还有fresh的橘子1,然后在orangesRotting()方法算minute。

就是在while(hasFresh())中对grid全部扫描一遍,如果有2,就把它放进栈中,扫描完了就把这些2的坐标拿出来,然后把2的周围的1变成2调用turnRot(),这算是变腐烂了1次,minute++,然后又是while去检查是否还有fresh,如果还有就继续腐烂,最后直到没有了fresh就跳出循环返回minute。

但是如果是一列2,2,1,0,1,1就出现死循环了,因为第一个1腐烂后无法去腐烂后面但是又始终hasFresh,

于是我加了一个visit布尔数组,如果发现了一个2并且它没有visit才把它放进栈,然后visit改为true表示已经用它腐烂过周围了不能再次腐烂周围了,下次扫面到这个2就不会放进栈了,那么上面的情况就当第一个1变成2并且visit后就没有可以放进栈的2了,所以扫描一遍后stack还是empty,所以当扫描一遍后stack还是empty的话直接返回-1,

以下是我的代码:

class Solution {public int orangesRotting(int[][] grid) {int m = grid.length;int n = grid[0].length;int minute =0;boolean[][] visit = new boolean[m][n];if(check(grid) == -1)return -1;while(hasFresh(grid)){Stack<Integer[]> stack = new Stack<>(); for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 2 && visit[i][j] == false){visit[i][j] = true;Integer[] index = new Integer[]{i,j};stack.push(index);}}}if(stack.isEmpty()){return -1;}while(!stack.isEmpty()){Integer[] a = stack.pop();grid = turnRot(grid, a[0], a[1]);}minute++;}return minute;}public int[][] turnRot(int[][] grid, int i, int j){if(i-1>=0 && grid[i-1][j]==1)grid[i-1][j] = 2;if(i+1<grid.length && grid[i+1][j]==1)grid[i+1][j] = 2;if(j-1>=0 && grid[i][j-1]==1)grid[i][j-1] = 2;if(j+1<grid[0].length && grid[i][j+1]==1)grid[i][j+1] = 2;return grid;}public boolean hasFresh(int[][] grid){int m = grid.length;int n = grid[0].length;for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 1)return true;}}return false;}public int check(int[][] grid){int m = grid.length;int n = grid[0].length;//如果有1的周围都是空,则这个位置用不腐烂,返回-1for(int i =0;i<m;i++){for(int j=0;j<n;j++){if((grid[i][j] == 1)){if(i-1>=0 && grid[i-1][j]!=0)continue;if(i+1<grid.length && grid[i+1][j]!=0)continue;if(j-1>=0 && grid[i][j-1]!=0)continue;if(j+1<grid[0].length && grid[i][j+1]!=0)continue;return -1;}}}if(statuCode == 0)return 0;//如果全是1,返回永不腐烂,返回-1statuCode = -1;for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] != 1){statuCode =1;}}}if(statuCode == -1)return -1;//如果没有2,用不腐烂,则返回-1statuCode =-1;for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 2){statuCode=1;}}}if(statuCode == -1)return -1;return 1;}}

我这个算法写的太屎了,尤其是check方法全靠一种一种情况排除,还是看看官方题解吧,写到这里的时候,我想去看看check方法能不能优化一下,把有些情况放一起check,比如那个全是1就不用判断了,因为它包含在没有2的情况里面,但是你猜怎么了?

我发现有了visit数组后,check中的所有情况都不用check,因为他们都是使得stack为空,直接返回-1了,我只能说牛逼。所以可以删掉check方法,改成代码如下:

class Solution {public int orangesRotting(int[][] grid) {int m = grid.length;int n = grid[0].length;int minute =0;boolean[][] visit = new boolean[m][n];while(hasFresh(grid)){Stack<Integer[]> stack = new Stack<>(); for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 2 && visit[i][j] == false){visit[i][j] = true;Integer[] index = new Integer[]{i,j};stack.push(index);}}}if(stack.isEmpty()){return -1;}while(!stack.isEmpty()){Integer[] a = stack.pop();grid = turnRot(grid, a[0], a[1]);}minute++;}return minute;}public int[][] turnRot(int[][] grid, int i, int j){if(i-1>=0 && grid[i-1][j]==1)grid[i-1][j] = 2;if(i+1<grid.length && grid[i+1][j]==1)grid[i+1][j] = 2;if(j-1>=0 && grid[i][j-1]==1)grid[i][j-1] = 2;if(j+1<grid[0].length && grid[i][j+1]==1)grid[i][j+1] = 2;return grid;}public boolean hasFresh(int[][] grid){int m = grid.length;int n = grid[0].length;for(int i =0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j] == 1)return true;}}return false;}}

看看官方题解的做法吧,题解用的叫多源广度优先搜索,和上一道题岛屿的数量的解法差不多,先上代码:

class Solution {int[] dr = new int[]{-1, 0, 1, 0};int[] dc = new int[]{0, -1, 0, 1};public int orangesRotting(int[][] grid) {int R = grid.length, C = grid[0].length;Queue<Integer> queue = new ArrayDeque<Integer>();Map<Integer, Integer> depth = new HashMap<Integer, Integer>();for (int r = 0; r < R; ++r) {for (int c = 0; c < C; ++c) {if (grid[r][c] == 2) {int code = r * C + c;queue.add(code);depth.put(code, 0);}}}int ans = 0;while (!queue.isEmpty()) {int code = queue.remove();int r = code / C, c = code % C;for (int k = 0; k < 4; ++k) {int nr = r + dr[k];int nc = c + dc[k];if (0 <= nr && nr < R && 0 <= nc && nc < C && grid[nr][nc] == 1) {grid[nr][nc] = 2;int ncode = nr * C + nc;queue.add(ncode);depth.put(ncode, depth.get(code) + 1);ans = depth.get(ncode);}}}for (int[] row: grid) {for (int v: row) {if (v == 1) {return -1;}}}return ans;}
}

它每个元素用序号(行号*每行的个数+列好)来表示,用一个队列来装一层的2的序号,然后用一个Map<Integer, Integer> depth表示每个节点的深度,key是序号,value是腐烂时间,他的腐烂时间其实就是父节点的腐烂时间+1,然后遍历完一次就把队列里的2取出来反向解出行号和列号,然后把周围腐烂,把周围的序号放进队列,把所有时间,也就是父节点时间+1放入map,然后取出时间,因为每次所放入的时间都是上一次的时间+1,所以最后一次的时间就是最大时间,所以最后返回ans是没有问题的,在返回之前先检查一遍,如果还有没腐烂的橘子1就返回-1。

相关文章:

LeetCode994.腐烂的橘子

看完题我觉得这不是和上一道岛屿的题一样简单嘛&#xff0c;然后写了将近2个小时才写出来&#xff0c;我的思路就是&#xff0c;用check()先对grid检查一下&#xff0c;是否有以下情况&#xff1a; &#xff08;如果有1的周围都是空&#xff0c;则这个位置用不腐烂&#xff0c;…...

【开源】基于Vue和SpringBoot的康复中心管理系统

项目编号&#xff1a; S 056 &#xff0c;文末获取源码。 \color{red}{项目编号&#xff1a;S056&#xff0c;文末获取源码。} 项目编号&#xff1a;S056&#xff0c;文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 普通用户模块2.2 护工模块2.3 管理员…...

【音视频基础】AVI文件格式

AVI文件采用的是RIFF文件结构方式。波形音频wave&#xff0c;MIDI和数字视频AVI都采用这种格式存储。 AVI文件的整体结构如下图所示 构造RIFF文件的基本单元叫做数据块&#xff08;Chunk&#xff09;&#xff0c;每个数据块包含3个部分 4字节的数据块标记&#xff08;或者叫…...

图书馆整理I(从尾到头打印列表),剑指offer,力扣

目录 题目地址&#xff1a; 我们直接看题解吧&#xff1a; 解题方法&#xff1a; 难度分析&#xff1a; 审题目事例提示&#xff1a; 解题思路(辅助栈)&#xff1a; 代码&#xff08;递归&#xff09;&#xff1a; 代码&#xff08;列表插入&#xff09;&#xff1a; 相似题目对…...

C++编写的多线程自动爬虫程序

目录 引言 一、程序的设计 二、程序的实现 三、程序的测试 四、优化与改进 五、代码示例 总结 引言 随着互联网的快速发展&#xff0c;网络爬虫程序已经成为数据采集、信息处理的重要工具。C作为一种高效的编程语言&#xff0c;具有高效的并发处理能力和丰富的网络编程…...

SMB信息泄露的利用

一、背景 今天分享SMB信息泄露&#xff0c;SMB&#xff08;Server Message Block&#xff09;网络通信协议&#xff0c;早些时候被用于Web链接和客户端与服务器之间的信息通信&#xff0c;现在大部分Web页面使用HTTP协议&#xff0c;在web领域应用较少。另一方面SMB协议还是被…...

QT自定义信号,信号emit,信号参数注册

qt如何自定义信号 使用signals声明返回值是void在需要发送信号的地方使用 emit 信号名字(参数)进行发送 在需要链接的地方使用connect进行链接 ct进行链接...

06.webpack性能优化--构建速度

优化babel-loaderhappyPackIgnorePluginparalleUglifyPluginnoParse自动刷新 1 happypack多进程打包 js单线程&#xff0c;开启多进程打包提高构建速度&#xff08;特别是多核CPU&#xff09; const HappyPack require(happypack)module.exports smart(webpackCommonConf,…...

11-15 周三 softmax 回归学习

11-15 周三 softmax 回归学习 时间版本修改人描述2023年11月15日11:17:27V0.1宋全恒新建文档 简介 softmax分享可以参考什么是softmax 回归估计一个连续值&#xff0c;分类预测一个离散类别。 恶意软件的判断 回归和分类 分类可以认为从回归的单输出变成多输出 B站学习 softm…...

React新手必懂的知识点

react思想&#xff1a;组件化开发 React 的核心概念是组件化开发&#xff0c;将用户界面拆分成独立的可复用组件。学习如何创建和使用 React 组件&#xff0c;以及组件之间的数据传递和通信是非常重要的。 React的思想就是拆分组件与使用组件。 import React from react;// 定…...

es为什么这么快

es为什么这么快的方式 es的基于Lucene开源搜索引擎&#xff0c;负责文件存储和搜索&#xff0c;支持http请求&#xff0c;以json形式展示 这样介绍你有可能有点迷糊我们详细解释 es 使用的倒排索引的方式&#xff0c;进行数据存储方式&#xff0c;给每一个字段创建索引&…...

Pandas分组聚合_Python数据分析与可视化

Pandas分组聚合 分组单列和多列分组Series 系列分组通过数据类型或者字典分组获取单个分组对分组进行迭代 聚合应用单个聚合函数应用多个聚合函数自定义函数传入 agg() 中对不同的列使用不同的聚合函数 分组聚合的流程主要有三步&#xff1a; 分割步骤将 DataFrame 按照指定的…...

VMware17虚拟机Linux安装教程(详解附图,带VMware Workstation 17 Pro安装)

一、安装 VMware 附官方下载链接&#xff08;VM 17 pro&#xff09;&#xff1a;https://download3.vmware.com/software/WKST-1701-WIN/VMware-workstation-full-17.0.1-21139696.exe 打开下载好的VMware Workstation 17 Pro安装包&#xff1b; 点击下一步&#xff1b; 勾选我…...

基于SDN技术构建多平面业务承载网络

随着企业数字化的浪潮席卷各个行业&#xff0c;传统网络架构面临着更为复杂和多样化的挑战。企业正在寻找一种全面适应数字化需求的网络解决方案。随着软件定义网络&#xff08;SDN&#xff09;的发展&#xff0c;“多业务SDN一张网”解决方案为企业提供了一种全新的网络架构&a…...

关于卓越服务的调研报告

NetSuite知识会发起的本次调研从2023年11月2日开始&#xff0c;到11月12日结束。16日已向参与调研的朋友邮件回复&#xff0c;感谢您的付出&#xff01;今朝分享此报告&#xff0c;各位同学参考。 调研问题与反馈总结 问题1&#xff1a;您能想到哪些服务组织能够提供高满意度&…...

ubuntu22.04换源

1、系统信息 lsb_release -a No LSB modules are available. Distributor ID: Ubuntu Description: Ubuntu 22.04.3 LTS Release: 22.04 Codename: jammy2、进入 /etc/apt/ 目录&#xff1a; cd /etc/apt/ 3、备份默认源文件 sudo cp sources.list sources.list_bak 4、编…...

03. Python中的语句

1、前言 在《Python基础数据类型》一文中&#xff0c;我们了解了Python中的基础数据类型&#xff0c;今天我们继续了解下Python中的语句和函数。 2、语句 在Python中常用的语句可以大致分为两类&#xff1a;条件语句、循环语句。 2.1、条件语句 条件语句就是我们编码时常见…...

Linux CentOS7 添加网卡

一台主机中安装多块网卡&#xff0c;有许多优势。可以实现多项功能。 为了学习网卡参数的设置&#xff0c;可以为主机添加多块网卡。与添加磁盘一样&#xff0c;要在VMware中设置。利用图形化方式或命令行查看或设置网卡。本文仅初步讨论添加、查看与删除网卡&#xff0c;有关…...

2311rust,到54版本更新

1.50.0稳定版 常量泛型数组索引 继续向稳定的常量泛型迈进,此版本为[T;N]数组,添加了ops::Index和IndexMut的实现. fn second<C>(container: &C) -> &C::Output whereC: std::ops::Index<usize> ?Sized, {&container[1] } fn main() {let arra…...

【linux】补充:高效处理文本的命令学习(tr、uniq、sort、cut)

目录 一、tr——转换、压缩、删除 1、tr -s “分隔符” &#xff08;指定压缩连续的内容&#xff09; 2、tr -d 想要删除的东西 ​编辑 3、tr -t 内容1 内容2 将内容1全部转换为内容2&#xff08;字符数需要一一对应&#xff09; 二、cut——快速剪裁命令 三、uniq——去…...

Redis篇---第七篇

系列文章目录 文章目录 系列文章目录前言一、是否使用过 Redis Cluster 集群,集群的原理是什么?二、 Redis Cluster 集群方案什么情况下会导致整个集群不可用?三、Redis 集群架构模式有哪几种?前言 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分…...

Shell脚本:Linux Shell脚本学习指南(第一部分Shell基础)一

你好&#xff0c;欢迎来到「Linux Shell脚本」学习专题&#xff0c;你将享受到免费的 Shell 编程资料&#xff0c;以及很棒的浏览体验。 这套 Shell 脚本学习指南针对初学者编写&#xff0c;它通俗易懂&#xff0c;深入浅出&#xff0c;不仅讲解了基本知识&#xff0c;还深入底…...

长短期记忆(LSTM)与RNN的比较:突破性的序列训练技术

长短期记忆&#xff08;Long short-term memory, LSTM&#xff09;是一种特殊的RNN&#xff0c;主要是为了解决长序列训练过程中的梯度消失和梯度爆炸问题。简单来说&#xff0c;就是相比普通的RNN&#xff0c;LSTM能够在更长的序列中有更好的表现。 Why LSTM提出的动机是为了解…...

Swift 如何打造兼容新老系统的字符串分割(split)方法

0. 概览 在 Swift 的开发中&#xff0c;我们经常要与字符串打交道。其中一个常见的操作就是用特定的“分隔符”来分割字符串&#xff0c;这里分隔符可能不仅仅是字符&#xff0c;而是多字符组成的字符串。 从 iOS 16 开始&#xff0c; 新增了对应的方法来专注此事。不过&am…...

JVM面试必备

目录 JVM三大问题 一、JVM内存区域划分 ​编辑 二、JVM类加载机制 双亲委派模型&#xff08;常考) 类加载的格式&#xff0c;类卸载 三、垃圾回收&#xff08;GC) 具体垃圾回收GC步骤 1.判定对象是否为垃圾 方案1:引用计数 方案2&#xff1a;可达性分析 2.释放对象的…...

战神传奇【我本沉默精修版】win服务端+双端+充值后台+架设教程

搭建资源下载:战神传奇【我本沉默精修版】win服务端双端充值后台架设教程-海盗空间...

安卓手机投屏到电视,跨品牌、跨地域同样可以实现!

在手机网页上看到的视频&#xff0c;也可以投屏到电视上看&#xff01; 长时间使用手机&#xff0c;难免脖子会酸。这时候&#xff0c;如果你将手机屏幕投屏到大电视屏幕&#xff0c;可以减缓脖子的压力&#xff0c;而且大屏的视觉体验更爽。 假设你有一台安卓手机&#xff0c;…...

python变量名解析总结

1 python变量名解析总结 点号和无点号变量名&#xff0c;用不同的处理方式。 &#xff08;1&#xff09; 无点号的变量名&#xff0c;比如X&#xff0c;使用的是作用域。 &#xff08;2&#xff09; 有点号的变量名&#xff0c;比如obj.X&#xff0c;使用对象的命名空间。 …...

端口号大揭秘:网络世界的“门牌号”有多牛?

大家好&#xff0c;今天我们来聊一聊网络中的端口号。如果你以为端口号只是冷冰冰的数字&#xff0c;那你就大错特错了。端口号&#xff0c;这些看似枯燥的数字背后&#xff0c;隐藏着一个个生动的故事。 目录 大家好&#xff0c;今天我们来聊一聊网络中的端口号。如果你以为端…...

vue解除数据双向绑定

let obj JSON.parse(JSON.stringify(data));例如&#xff0c;table列表中&#xff0c;点击编辑时&#xff0c;可对val进行如上操作来解除双向绑定...