❌

阅读视图

发现新文章，点击刷新页面。

【Chthollist】双周赛第70场：LC5971：T1「贪心 & 排序」

✇LeetCode 每日一题题解
chthollists

前言

大家好，我是新人LeetCoder：「Chthollist」
正在坚持每日更新LeetCode每日一题，发布的题解有些会参考其他大佬的思路(参考资料的链接会放在最下面)，欢迎大家关注我 ~ ~ ~
同时也在进行其他专项类型题目的刷题与题解活动，相关资料也会同步到「GitHub」上面 ~
今天是坚持写题解的27天(haha，从21年圣诞节开始的)，大家一起加油！

  • 双周赛第70场：LeetCode：5971.打折购买糖果的最小开销
    • 时间：2022-01-22
    • 力扣难度：Easy
    • 个人难度：Easy
    • 数据结构：数组
    • 算法：贪心

LeetCode每日一题.jpg

双周赛第70场：LeetCode：5971.打折购买糖果的最小开销

1. 题目描述

  • 题目：原题链接

    • 一家商店正在打折销售糖果。每购买两个糖果，商店会免费送一个糖果。
    • 免费送的糖果唯一的限制是：它的价格需要小于等于购买的两个糖果价格的较小值 。
    • 比方说，总共有 4 个糖果，价格分别为 1 ，2 ，3 和 4 ，一位顾客买了价格为 2 和 3 的糖果，那么他可以免费获得价格为 1 的糖果，但不能获得价格为 4 的糖果。
    • 给你一个下标从 0 开始的整数数组 cost ，其中 cost[i] 表示第 i 个糖果的价格，请你返回获得 所有 糖果的最小总开销。

  • 输入输出规范

    • 输入：价格数组 cost
    • 输出：整型，表示最小花费

  • 输入输出示例

    • 输入：cost = [6,5,7,9,2,2]
    • 输出：23

2. 方法：贪心 & 排序

  • 思路

    • 本题要计算购买所有物品的最小开销，且可以买二赠一，但是赠送的一定比买的这两个便宜
    • 根据贪心的思想，我们每次可以选择买最贵的两个物品，然后赠送第三贵的物品，然后再从剩余的物品中重复这一操作，剩余物品不足两个时直接购买，最后得到的就是最小开销
    • 那么，虽然解题思路非常容易理解，但是如何证明这样贪心求解一定是最优解呢
    • 简单通过反证法来证明：如果每次购买的不是最贵的两个，而是任意两个物品，这里假设买了第二和第三贵的物品，那么获赠的只能是第四贵及以下的物品，最贵的物品仍然必须购买，那么，局部花费为：cost[1]+cost[2]+cost[3]，而贪心求解的结果为买第一、第二、第四贵：cost[1]+cost[2]+cost[4]，花费更小

  • 题解：排序并模拟

###java

  > public int minimumCost(int[] cost) {
  >     if(cost == null || cost.length == 0) return 0;
  >     int n = cost.length;
  >     if(n == 1) return cost[0];
  >     if(n == 2) return cost[0] + cost[1];
  >     int minCost = 0;
  >     Arrays.sort(cost);
  >     for(int i = n-1; i>=0; i--) {
  >         minCost += cost[i];
  >         if(i - 1 >= 0)  minCost += cost[i - 1];
  >         i-=2;
  >     }
  >     return minCost;
  > }
  > ```

* 复杂度分析：n 是数组的长度

  * 时间复杂度：$O(nlog)$，受限于排序的复杂度
  * 空间复杂度：$O(1)$
---



## 最后
如果本文有所帮助的话，欢迎大家可以给个三连「点赞」&「收藏」&「关注」 ~ ~ ~
也希望大家有空的时候光临我的其他平台，上面会更新Java面经、八股文、刷题记录等等，欢迎大家光临交流，谢谢！
* 「[个人博客](https://chthollists.github.io/)」
* 「[掘金](https://juejin.cn/user/26854211457719)」
* 「[简书](https://www.jianshu.com/u/8000305d22b9)」
❌