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.腐烂的橘子
看完题我觉得这不是和上一道岛屿的题一样简单嘛,然后写了将近2个小时才写出来,我的思路就是,用check()先对grid检查一下,是否有以下情况: (如果有1的周围都是空,则这个位置用不腐烂,…...

【开源】基于Vue和SpringBoot的康复中心管理系统
项目编号: S 056 ,文末获取源码。 \color{red}{项目编号:S056,文末获取源码。} 项目编号:S056,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 普通用户模块2.2 护工模块2.3 管理员…...

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

图书馆整理I(从尾到头打印列表),剑指offer,力扣
目录 题目地址: 我们直接看题解吧: 解题方法: 难度分析: 审题目事例提示: 解题思路(辅助栈): 代码(递归): 代码(列表插入): 相似题目对…...

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

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

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

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

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

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

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

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

VMware17虚拟机Linux安装教程(详解附图,带VMware Workstation 17 Pro安装)
一、安装 VMware 附官方下载链接(VM 17 pro):https://download3.vmware.com/software/WKST-1701-WIN/VMware-workstation-full-17.0.1-21139696.exe 打开下载好的VMware Workstation 17 Pro安装包; 点击下一步; 勾选我…...

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

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

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/ 目录: cd /etc/apt/ 3、备份默认源文件 sudo cp sources.list sources.list_bak 4、编…...

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

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

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 “分隔符” (指定压缩连续的内容) 2、tr -d 想要删除的东西 编辑 3、tr -t 内容1 内容2 将内容1全部转换为内容2(字符数需要一一对应) 二、cut——快速剪裁命令 三、uniq——去…...

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

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

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

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

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

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

安卓手机投屏到电视,跨品牌、跨地域同样可以实现!
在手机网页上看到的视频,也可以投屏到电视上看! 长时间使用手机,难免脖子会酸。这时候,如果你将手机屏幕投屏到大电视屏幕,可以减缓脖子的压力,而且大屏的视觉体验更爽。 假设你有一台安卓手机,…...

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

端口号大揭秘:网络世界的“门牌号”有多牛?
大家好,今天我们来聊一聊网络中的端口号。如果你以为端口号只是冷冰冰的数字,那你就大错特错了。端口号,这些看似枯燥的数字背后,隐藏着一个个生动的故事。 目录 大家好,今天我们来聊一聊网络中的端口号。如果你以为端…...

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