LeetCode – 1705 – 吃苹果的最大数目 – Java – 细节~

云惠网小编 2021年12月25日17:18:52
评论
2565字阅读8分33秒
摘要

文章目录题目题目解析解题方法 : 贪心思想 + 优先队列来跟着我一步步看,怎么实现这个代码第一步: 创建 三个变量 和 new 一个 PriorityQueue(优先队列),并制定该队列,每次取出 “苹果 / 数据” 时,永远是快要坏掉的 “苹果 / 数据”。第二步开始遍历 apples 和 days 数组,确认每天产出苹果数量 和 该天产出苹果的保质期。如果到了保质日期,就丢掉。如果没过保质期,就代表我们需要记入 今天苹果的个数和保质期(前提今天有苹果产出),而且也意味着我们今天开始可以吃一个苹果,但是

广告也精彩

文章目录

  • 题目
  • 题目解析
  • 解题方法 : 贪心思想 + 优先队列
  • 来跟着我一步步看,怎么实现这个代码
    • 第一步: 创建 三个变量 和 new 一个 PriorityQueue(优先队列),并制定该队列,每次取出 "苹果 / 数据" 时,永远是快要坏掉的 "苹果 / 数据"。
    • 第二步开始遍历 apples 和 days 数组,确认每天产出苹果数量 和 该天产出苹果的保质期。如果到了保质日期,就丢掉。如果没过保质期,就代表我们需要记入 今天苹果的个数和保质期(前提今天有苹果产出),而且也意味着我们今天开始可以吃一个苹果,但是这个苹果一定某天产出的苹果(该天产出苹果保质期是最短的),当我们吃完该天的苹果(前提是没过期),我们就可以将其存储的信息删除掉了。
    • 第三步: 计算带回家的苹果还可以吃几天
  • 最后附上程序

贪心思想,其实在题目解析的时候就讲了,为了吃得更多,我们选择吃那些再不吃过几天就会坏掉的苹果。而优先队列 是为了我们让我们每次吃得苹果刚好就是我们想吃的那种苹果,这就相当于 优先队列,即使帮我们分好苹果,快坏的苹果永远在我们面前。

题目解析


第二步开始遍历 apples 和 days 数组,确认每天产出苹果数量 和 该天产出苹果的保质期。如果到了保质日期,就丢掉。如果没过保质期,就代表我们需要记入 今天苹果的个数和保质期(前提今天有苹果产出),而且也意味着我们今天开始可以吃一个苹果,但是这个苹果一定某天产出的苹果(该天产出苹果保质期是最短的),当我们吃完该天的苹果(前提是没过期),我们就可以将其存储的信息删除掉了。

在这里插入图片描述

第三步: 计算带回家的苹果还可以吃几天


最后附上程序

在这里插入图片描述

题目的意思,我给你们大概整理了一下:一个苹果树,每天 产出 count 个苹果(有可能不产出,即 count == 0),现在的情况呢,就是我们嘴馋,看到老家有颗苹果树,几乎每天都可能产出苹果。这不吃,对得起我们这张嘴吗?对不起,知道嘛!所以我们在老家待的 i 天里,每天都要吃一个苹果。临走的时候还要顺着几个,当然肯定是当天没坏的。而且按照家里人的习惯,会把待在家里这几天没坏的新鲜水果全部给你。
我们呢,为了不浪费,每天吃的都是过几天就可能坏的苹果。但是呢!一个人的力量是有限的。
我们每天只吃一个苹果,吃完这个苹果,我们不再吃了,意味着:其他苹果,今天失去了被吃的机会!同时保质日期减一。
再加上家里人,认为自己家种的苹果就跟不要钱一样,往死里塞,完全不管人家受不受得了!
也就是说:存在 部分苹果 会腐烂,那就只能丢了。
大概就是这么个情况。



解题方法 : 贪心思想 + 优先队列


来跟着我一步步看,怎么实现这个代码

第一步: 创建 三个变量 和 new 一个 PriorityQueue(优先队列),并制定该队列,每次取出 “苹果 / 数据” 时,永远是快要坏掉的 “苹果 / 数据”。

class Solution {
public int eatenApples(int[] apples, int[] days) {
int result = 0; // 最终结果 - 最多吃几个苹果
int n = apples.length;// 获取在老家待多少天。
int i = 0;// 记录天数,用来对比保质期
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->a[0]-b[0]);// 每次取出的数据,都是保质期最短的那一组
while(i<n){
while(!pq.isEmpty() && pq.peek()[0] <= i){//检查 今天是否有某一天的苹果腐烂了(到保质期了)。
// pq.peek() 是返回队列中的头元素。因为我们是优先队列,所以 最快坏掉的苹果,就放在头位置
pq.poll();// 到期了,就扔掉。由此我们知道 poll 就删除出队列元素的方法
}
int rottenDay = i + days[i];// 记录当天产出苹果的保质期
int count = apples[i];// 记录 当天产出的苹果数量
if(count > 0){// 只有产出苹果,才有被记录信息的价值
pq.offer(new int[]{rottenDay,count});// 你现在可以看看 while(i<n)后面 while循环的条条件为什么是让 队列的头元素,来比较,
}
if(!pq.isEmpty()){// 这个if语句是为了防止 某天没有产出苹果,刚好又没有存货。
int[] arr = pq.peek();//获取 队列头元素,或者说:获取某天产出苹果(保质期最短的)信息
arr[1]--;// 每天吃的那一个苹果。
if(arr[1]==0){// 把某天快坏的苹果吃完了
pq.poll();// 那就没必要记着该天的苹果信息
}
result++;// 我们此时吃到了一个苹果
}
i++;// 过去了一天
}
// 回去的那天,带回来的苹果
while(!pq.isEmpty()){//防止这几天产出的苹果,刚好够吃。所以队列中也就没有数据(没有苹果可以带走)
while(!pq.isEmpty() && pq.peek()[0]<=i){
// 这个跟上面的那个 while循环是一样的,检查有没有那天的苹果到了日期。
pq.poll();//到期, 丢掉。
}
if(pq.isEmpty()){// 昨天带回来的苹果,今天就全烂了,丢完了。队列中自然就是空的,没有数据
break;// 那就没必要进行下一步,直接终止循环,返回 最终结果 result。
}
//如果程序走到这里,说明不满足循环 和 if 条件。
// 意味着:有口福了,今天还有苹果可以吃
int[] arr = pq.poll();// 获取某天最快坏掉的苹果信息(保质期,和个数)
int eatDay = Math.min(arr[0]- i,arr[1] );// 
// 首先,我们肯定只会吃没腐烂的苹果,其次我们每天只吃一个。
// 保质期减去今天,不就是苹果还有几天过期? 又可以说 一天吃一个苹果可以吃几天。
// 但是可能存在 吃不完苹果,导致腐烂的情况,或者说 在苹果坏掉之前,刚好吃完。
// 所以我们要选取最小值,来保证每天迟到苹果不是坏的。 
// 我们吃的 苹果数量 和 天数 同时 加上 eatDay。 (一天一个苹果)
result += eatDay;
i += eatDay;
}
return result;// 返回我们最终吃进肚子里的苹果总数
}
}

在这里插入图片描述

题目


在这里插入图片描述

在这里插入图片描述

本文转自 https://blog.csdn.net/DarkAndGrey/article/details/122131091

腾讯云618
云惠网小编
SpringCloud -- Config、Bus解析 java

SpringCloud — Config、Bus解析

1、Config1.1、概述简介1. 分布式面临的问题微服务意味着要将单体应用中的业务拆分成一个个子服务,每个服务的粒度相对较小,因此系统中会出现大量的服务。由于每个服务都需要必要...
Java数据结构-了解复杂度 java

Java数据结构-了解复杂度

2.实例分析与计算  四.写在最后  // 计算斐波那契递归fibonacci的时间复杂度 int fibonacci(int N) { return N < 2 ? N : fibonacci...
Java数据结构-认识顺序表 java

Java数据结构-认识顺序表

目录二.顺序表1.概念及结构2.顺序表的实现打印顺序表获取顺序表的有效长度在pos位置新增元素判断是否包含某个元素查找某个元素对应的位置获取/查找pos位置的元素给pos位置的元素...
腾讯云618

发表评论