php网站模板免费下载,网页数据可视化设计案例,做网站有什么好的推荐,制作企业网站是怎么收费的【LetMeFly】1705.吃苹果的最大数目#xff1a;贪心(优先队列) - 清晰题解
力扣题目链接#xff1a;https://leetcode.cn/problems/maximum-number-of-eaten-apples/
有一棵特殊的苹果树#xff0c;一连 n 天#xff0c;每天都可以长出若干个苹果。在第 i 天#xff0c;…【LetMeFly】1705.吃苹果的最大数目贪心(优先队列) - 清晰题解
力扣题目链接https://leetcode.cn/problems/maximum-number-of-eaten-apples/
有一棵特殊的苹果树一连 n 天每天都可以长出若干个苹果。在第 i 天树上会长出 apples[i] 个苹果这些苹果将会在 days[i] 天后也就是说第 i days[i] 天时腐烂变得无法食用。也可能有那么几天树上不会长出新的苹果此时用 apples[i] 0 且 days[i] 0 表示。
你打算每天 最多 吃一个苹果来保证营养均衡。注意你可以在这 n 天之后继续吃苹果。
给你两个长度为 n 的整数数组 days 和 apples 返回你可以吃掉的苹果的最大数目。 示例 1
输入apples [1,2,3,5,2], days [3,2,1,4,2]
输出7
解释你可以吃掉 7 个苹果
- 第一天你吃掉第一天长出来的苹果。
- 第二天你吃掉一个第二天长出来的苹果。
- 第三天你吃掉一个第二天长出来的苹果。过了这一天第三天长出来的苹果就已经腐烂了。
- 第四天到第七天你吃的都是第四天长出来的苹果。示例 2
输入apples [3,0,0,0,0,2], days [3,0,0,0,0,2]
输出5
解释你可以吃掉 5 个苹果
- 第一天到第三天你吃的都是第一天长出来的苹果。
- 第四天和第五天不吃苹果。
- 第六天和第七天你吃的都是第六天长出来的苹果。提示
apples.length ndays.length n1 n 2 * 1040 apples[i], days[i] 2 * 104只有在 apples[i] 0 时days[i] 0 才成立
解题方法贪心
思路很简单 有一些苹果你先吃哪个答案是先吃腐烂最早的。 因此可以使用优先队列从第0天开始模拟到第 n − 1 n-1 n−1天 每天将当天新苹果入队腐烂较早的最优先 当队列不空且今天还没吃到苹果时不断出队若已腐烂则丢弃若未腐烂则吃一个并将剩下的苹果入队。 遍历完 0 0 0到 n − 1 n-1 n−1天不再有新苹果了但队列中可能有旧苹果。
这次和之前有所不同不再一天一天吃而是几天几天连续算 假设当前是第 d a y day day天队首苹果有 a p p l e N u m appleNum appleNum个且将在 r o t D a y rotDay rotDay腐烂则能连续吃 m a x ( 0 , m i n ( r o t D a y − d a y , a p p l e N u m ) ) max(0, min(rotDay - day, appleNum)) max(0,min(rotDay−day,appleNum))天。 为什么 0 0 0到 n − 1 n-1 n−1天要一天一天地吃而从第 n n n天开始可以连续吃同一批苹果 因为从第 n n n天开始不会产生新苹果了我们不再关心苹果的“产生日期”只要没过保质期就能吃。 但是前 n n n天可不一样例如第 0 0 0天产 2 2 2个 1000 1000 1000天保质期的苹果第 1 1 1天产 1 1 1个保质期 1 1 1天的苹果那么就不能照着第 0 0 0天的 2 2 2个连续吃完而应该第 0 0 0和 3 3 3天吃第 0 0 0天产的第 1 1 1天吃第 1 1 1天产的。 本质上来说就是前 n n n天每天都有新苹果产生可能导致队首苹果不再是腐烂最早的苹果。 时间复杂度 O ( n log n ) O(n\log n) O(nlogn)空间复杂度 O ( n ) O(n) O(n)
AC代码
C
/** Author: LetMeFly* Date: 2024-12-24 10:56:16* LastEditors: LetMeFly.xyz* LastEditTime: 2024-12-24 18:41:09*/
// 不能只按照腐烂截止时间
// 例如不能为了吃截止时间为6的4,5而空出第3天
/*
[1,2,3,5,2]
[3,2,1,4,2]0-3, 1, 1-3, 2, 2-3, 1, 3-7, 5, 4-6, 20 1, 2 3, 6 4, 5
*/
// 前n天应该 边遍历边入队
class Solution {
public:int eatenApples(vectorint apples, vectorint days) {priority_queuepairint, int, vectorpairint, int, greater pq;int ans 0, day 0;for (; day apples.size(); day) {if (apples[day]) {pq.push({day days[day], apples[day]});}while (pq.size()) {auto [rotDay, appleNum] pq.top();pq.pop();if (rotDay day) {continue;}ans;appleNum--;if (appleNum) {pq.push({rotDay, appleNum});}break;}}while (pq.size()) {auto [rotDay, appleNum] pq.top();pq.pop();int eat max(0, min(rotDay - day, appleNum));ans eat;day eat;}return ans;}
};Python Author: LetMeFly
Date: 2024-12-24 18:46:52
LastEditors: LetMeFly.xyz
LastEditTime: 2024-12-24 18:56:55from typing import List
import heapqclass Solution:def eatenApples(self, apples: List[int], days: List[int]) - int:pq []ans 0for day in range(len(apples)):if apples[day]:heapq.heappush(pq, (day days[day], apples[day]))while pq:rotDay, appleNum heapq.heappop(pq)if rotDay day:continueans 1appleNum - 1if appleNum:heapq.heappush(pq, (rotDay, appleNum))breakday 1 # 注意这里和C不一样python执行完day是能取到的右值while pq:rotDay, appleNum heapq.heappop(pq)eat max(0, min(rotDay - day, appleNum))ans eatday eatreturn ansJava
/** Author: LetMeFly* Date: 2024-12-24 18:58:06* LastEditors: LetMeFly.xyz* LastEditTime: 2024-12-24 19:07:07*/
import java.util.PriorityQueue;class Solution {public int eatenApples(int[] apples, int[] days) {PriorityQueueint[] pq new PriorityQueueint[]((a, b) - a[0] - b[0]);int ans 0, day 0;for (; day apples.length; day) {if (apples[day] 0) {pq.add(new int[]{day days[day], apples[day]});}while (pq.size() 0) {int[] temp pq.poll();int rotDay temp[0], appleNum temp[1];if (rotDay day) {continue;}ans;appleNum--;if (appleNum 0) {pq.add(new int[]{rotDay, appleNum});}break;}}while (!pq.isEmpty()) {int[] temp pq.poll();int rotDay temp[0], appleNum temp[1];int eat Math.max(0, Math.min(rotDay - day, appleNum));ans eat;day eat;}return ans;}
}Go
/** Author: LetMeFly* Date: 2024-12-24 19:07:32* LastEditors: LetMeFly.xyz* LastEditTime: 2024-12-24 23:43:52*/
package main
import container/heaptype pair struct{ rotDay, appleNum int}
type PQ []pairfunc (pq PQ) Len() int { return len(pq) }
func (pq PQ) Less(i, j int) bool { return pq[i].rotDay pq[j].rotDay }
func (pq PQ) Swap(i, j int) { pq[i], pq[j] pq[j], pq[i] }
func (pq *PQ) Push(v any) { *pq append(*pq, v.(pair)) }
func (pq *PQ) Pop() any { v : (*pq)[len(*pq) - 1]; *pq (*pq)[:len(*pq) - 1]; return v }func min_eatenApples(a, b int) int { if a b { return a}; return b}
func max_eatenApples(a, b int) int { if a b { return a}; return b}func eatenApples(apples []int, days []int) (ans int) {var pq PQfor day : range apples {if apples[day] 0 {heap.Push(pq, pair{day days[day], apples[day]})}for len(pq) 0 {v : heap.Pop(pq).(pair)rotDay, appleNum : v.rotDay, v.appleNumif rotDay day {continue}ansappleNum--if appleNum 0 {heap.Push(pq, pair{rotDay, appleNum})}break}}day : len(apples)for len(pq) 0 {v : heap.Pop(pq).(pair)rotDay, appleNum : v.rotDay, v.appleNumeat : max_eatenApples(0, min_eatenApples(rotDay - day, appleNum))ans eatday eat}return
}Golang的堆是一个接口需要实现Len、Less、Swap、Push、Pop方法。
可参考与ChatGPT的对话 同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~ Tisfyhttps://letmefly.blog.csdn.net/article/details/144705583
