LeetCode 994. Rotting Oranges。
题目来源:https://leetcode.com/problems/rotting-oranges
题目难度:Easy
解答1[Java]:
核心思想
设时间为 minutes,初始时 minutes为0,初始状态就已经坏掉的橙子标记为2。
第一轮处理的时候,我们只处理 minutes + 2 的元素,把这种元素周围值为1的元素设为 minutes + 3。
这样一轮结束,我们把 minutes 加1,这样,刚刚被设为 minutes + 3 的元素,在minutes 加1之后,相当于变成了 minutes+2,也就是说,minutes+2一直代表上一轮变坏的橙子。
使用变量oldFresh 和 fresh 表示上一轮剩下的新鲜橙子数和本轮之后剩下的新鲜橙子数,如果两者相同,说明有一些新鲜的橙子碰不到坏橙子,不会变坏,直接返回 -1。
代码
1 | public class Solution { |
解答2[Java]:BFS广度优先遍历
核心思路
使用一个队列。第一次遍历的时候,把所有值为2的元素放到队列中。
开始遍历,每次只遍历上一轮放到队列中的元素,每遍历到一个元素,如果元素可以把周围的橙子变坏,就把变坏的橙子的值设为2,同时添加到队列中。
代码
1 | import java.util.LinkedList; |