首页 > 其他分享 >图解LeetCode——994. 腐烂的橘子

图解LeetCode——994. 腐烂的橘子

时间:2023-06-13 19:00:57浏览次数:36  
标签:994 deque int 单元格 腐烂 grid 橘子 图解 LeetCode

一、题目

在给定的 m x n 网格 grid 中,每个单元格可以有以下三个值之一:

  • 值 0 代表空单元格
  • 值 1 代表新鲜橘子
  • 值 代表腐烂的橘子

每分钟,腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。 返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能,返回 -1 。

二、示例

2.1> 示例 1:

输入】grid = [[2,1,1],[1,1,0],[0,1,1]] 【输出】4

2.2> 示例 2:

输入】grid = [[2,1,1],[0,1,1],[1,0,1]] 【输出】-1 【解释】左下角的橘子(第 2 行, 第 0 列)永远不会腐烂,因为腐烂只会发生在 4 个正向上。

2.3> 示例 3:

输入】grid = [[0,2]] 【输出】0 【解释】因为 0 分钟时已经没有新鲜橘子了,所以答案就是 0 。

提示:

  • m == grid.length
  • n == grid[i].length
  • 1 <= m, n <= 10
  • grid[i][j] 仅为 01 或 2

三、解题思路

根据题目描述,我们要计算出单元格中没有新鲜橘子为止所必须经过的最小分钟数。由于腐烂的橘子可以将好的橘子也变腐烂,所以,我们需要采用某种方式,将这种橘子腐烂的轮次模拟计算出来。

这里,我们首先创建一个队列,即:Deque。然后先将矩阵中腐烂的橘子保存到deque中。然后获取deque中存储的腐烂橘子的个数num那么当num个橘子从deque中出栈之后,就表示该轮次执行完毕

那么,当我们从队列deque弹出腐烂的橘子之后,我们会将该烂橘子的的新鲜橘子都变为烂橘子,即:grid[x][y] = 2。然后将刚刚变烂的句子放入到deque中,准备作为后续下一轮需要操作的烂橘子。

那么,需要补充一点的就是,当我们计算矩阵中腐烂橘子的同时,也可以同时获得新鲜的橘子的个数fresh当面当我们发现fresh等于0的时候,则说明所有的好橘子都被腐烂了,返回操作的轮次数;而当我们操作完所有的腐烂橘子,而fresh依然不为0,则说明某些新鲜的橘子是不会被传染腐烂的,则直接返回-1即可。

以上就是本题的解题思路。为了方便大家理解,请参照下图图解即可:

四、代码实现

class Solution {
    int fresh = 0, minute = 0;
    Deque<int[]> deque = new ArrayDeque();
    public int orangesRotting(int[][] grid) {
        int result = 0;
        for (int i = 0; i < grid.length; i++) {
            for (int j = 0; j < grid[0].length; j++) {
                if (grid[i][j] == 2) deque.addLast(new int[]{i, j});
                if (grid[i][j] == 1) fresh++;
            }
        }
        while (fresh > 0 && !deque.isEmpty()) {
            minute++;
            int nums = deque.size();
            for (int i = 0; i < nums; i++) {
                int[] cell = deque.removeFirst();
                int x = cell[0], y = cell[1];
                rot(grid, x - 1, y); // 查看上方单元格
                rot(grid, x + 1, y); // 查看下方单元格
                rot(grid, x, y - 1); // 查看左侧单元格
                rot(grid, x, y + 1); // 查看右侧单元格
            }
        }
        return fresh > 0 ? -1 : minute; 
    }
    public void rot(int[][] grid, int x, int y) {
        if (x >= 0 && y >=0 && x < grid.length && y < grid[0].length && grid[x][y] == 1) {
            grid[x][y] = 2;
            deque.addLast(new int[]{x, y});
            fresh--;
        }
    }
}

今天的文章内容就这些了:

写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享

更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」

标签:994,deque,int,单元格,腐烂,grid,橘子,图解,LeetCode
From: https://blog.51cto.com/u_15003301/6472094

相关文章

  • Leetcode常见报错的原因分析
    问题1问题描述Line522:Char69:runtimeerror:applyingnon-zerooffset18446744073709551615tonullpointer(basic_string.h)报错原因stringres=0报错分析这里报错的原因是因为使用了int整型变量来初始化string。......
  • leetcode-70 爬楼梯(java实现)
    爬楼梯题目分析1递归写法动态规划解法题目假设你正在爬楼梯。需要n阶你才能到达楼顶。每次你可以爬1或2个台阶。你有多少种不同的方法可以爬到楼顶呢?分析1递归写法如果要爬上第n阶,要么是从第n-1上面再爬1阶上去的,要么是从n-2上面再爬2阶上去的,那么我们就可以想到f(n)=......
  • leetcode 104. 二叉树的最大深度(java实现)
    104.二叉树的最大深度标题解法标题给定一个二叉树,找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。说明:叶子节点是指没有子节点的节点。解法publicclassSolution{publicintmaxDepth(TreeNoderoot){//如果节点为空,返回深度为0......
  • [LeetCode] 2475. Number of Unequal Triplets in Array
    Youaregivena 0-indexed arrayofpositiveintegers nums.Findthenumberoftriplets (i,j,k) thatmeetthefollowingconditions:0<=i<j<k<nums.lengthnums[i], nums[j],and nums[k] are pairwisedistinct.Inotherwords, nums[i]!=......
  • 【LeetCode专题#基本计算器】基本计算器I,图解中序表达式转逆波兰表达式,太难了
    基本计算器https://leetcode.cn/problems/basic-calculator/?envType=list&envId=cKNEfNsF给你一个字符串表达式s,请你实现一个基本计算器来计算并返回它的值。注意:不允许使用任何将字符串作为数学表达式计算的内置函数,比如eval()。示例1:输入:s="1+1"输出:2示例2:......
  • LeetCode 51. N 皇后
    classSolution{public:vector<vector<string>>res;vector<string>path;vector<bool>anti_diag,col,diag;voiddfs(intn,intu){if(u==n){res.push_back(path);return;......
  • leetCode1768.交替合并字符串 && [1679] K 和数对的最大数目
    题目:给你两个字符串word1和word2。请你从word1开始,通过交替添加字母来合并字符串。如果一个字符串比另一个字符串长,就将多出来的字母追加到合并后字符串的末尾。返回合并后的字符串。      输入:word1="abc",word2="pqr"      输出:"apbqcr......
  • LeetCode/区间子数组个数
    给你一个整数数组nums和两个整数:left及right找出nums中连续、非空且其中最大元素在范围[left,right]内的子数组,并返回满足条件的子数组的个数1.遍历区间右端点+同时记录满足条件的左边点位数组中不能含有大于right的元素,且至少含有一个处于[left,right]区间的元......
  • [leetcode每日一题]6.12
    1483. 树节点的第K个祖先提示困难150相关企业给你一棵树,树上有 n 个节点,按从 0 到 n-1 编号。树以父节点数组的形式给出,其中 parent[i] 是节点 i 的父节点。树的根节点是编号为 0 的节点。树节点的第 k 个祖先节点是从该节点到根节点路径上的第 k 个节点。实现......
  • 二刷Leetcode-Days10
    1.二叉树/***102.BinaryTree的层序遍历(借助辅助队列实现,递归法pass)*@paramroot*@return*/publicList<List<Integer>>levelOrder(TreeNoderoot){List<List<Integer>>resList=newArrayList<>();......