【贪心算法】（第一篇）

目录

柠檬⽔找零（easy）

题目解析

讲解算法原理

编写代码

将数组和减半的最少操作次数（medium）

题目解析

讲解算法原理

编写代码

柠檬⽔找零（easy）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

在柠檬⽔摊上，每⼀杯柠檬⽔的售价为 5 美元。顾客排队购买你的产品，（按账单 bills ⽀付的顺序）⼀次购买⼀杯。
每位顾客只买⼀杯柠檬⽔，然后向你付 5 美元、 10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你⽀付 5 美元。
注意，⼀开始你⼿头没有任何零钱。
给你⼀个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

⽰例1：
输⼊：bills=[5,5,5,10,20]
输出：true
解释：
前3位顾客那⾥，我们按顺序收取3张5美元的钞票。
第4位顾客那⾥，我们收取⼀张10美元的钞票，并返还5美元。
第5位顾客那⾥，我们找还⼀张10美元的钞票和⼀张5美元的钞票。
由于所有客⼾都得到了正确的找零，所以我们输出true。
⽰例2：
输⼊：bills=[5,5,10,10,20]
输出：false
解释：
前2位顾客那⾥，我们按顺序收取2张5美元的钞票。
对于接下来的2位顾客，我们收取⼀张10美元的钞票，然后返还5美元。
对于最后⼀位顾客，我们⽆法退回15美元，因为我们现在只有两张10美元的钞票。由于不是每位顾客都得到了正确的找零，所以答案是false。

提⽰：
◦ 1 <= bills.length <= 10(5)
◦ bills[i] 不是 5 就是 10 或是 20

讲解算法原理

解法（贪⼼）：
贪⼼策略：
分情况讨论：
a. 遇到 5 元钱，直接收下；
b. 遇到 10 元钱，找零 5 元钱之后，收下；
c. 遇到 20 元钱：
i. 先尝试凑 10 + 5 的组合；
ii. 如果凑不出来，拼凑 5 + 5 + 5 的组合；

编写代码

c++算法代码：

class Solution
{
public:
 bool lemonadeChange(vector<int>& bills) 
 {
 int five = 0, ten = 0;
 for(auto x : bills)
 {
 if(x == 5) five++; // 5 元：直接收下 else if(x == 10) // 10 元：找零 5 元 {
 if(five == 0) return false;
 five--; ten++;
 }
 else // 20 元：分情况讨论
 {
 if(ten && five) // 贪⼼
 {
 ten--; five--;
 }
 else if(five >= 3)
 {
 five -= 3;
 }
 else return false;
 }
 }
 return true;
 }
};

java算法代码：

class Solution
{
 public boolean lemonadeChange(int[] bills) 
 {
 int five = 0, ten = 0;
 for(int x : bills)
 {
 if(x == 5) // 5 元：直接收下
 {
 five++;
 }
 else if(x == 10) // 10 元：找零 5 元 {
 if(five == 0) return false;
 five--; ten++;
 }
 else // 20 元：分情况讨论
 {
 if(five != 0 && ten != 0) // 贪⼼ {
 five--; ten--;
 }
 else if(five >= 3)
 {
 five -= 3;
 }
 else return false;
 }
 }
 return true;
 }
}

将数组和减半的最少操作次数（medium）

题目解析

1.题目链接：. - 力扣（LeetCode）

2.题目描述

给你⼀个正整数数组 nums 。每⼀次操作中，你可以从 nums 中选择任意⼀个数并将它减⼩到恰好⼀半。（注意，在后续操作中你可以对减半过的数继续执⾏操作）
请你返回将 nums 数组和⾄少减少⼀半的最少操作数。
⽰例1：
输⼊：nums=[5,19,8,1]
输出：3
解释：初始nums的和为5+19+8+1=33。
以下是将数组和减少⾄少⼀半的⼀种⽅法：
选择数字19并减⼩为9.5。
选择数字9.5并减⼩为4.75。
选择数字8并减⼩为4。
最终数组为[5,4.75,4,1]，和为5+4.75+4+1=14.75。nums的和减⼩了33-14.75=18.25，减⼩的部分超过了初始数组和的⼀半，18.25>=33/2=16.5。
我们需要3个操作实现题⽬要求，所以返回3。
可以证明，⽆法通过少于3个操作使数组和减少⾄少⼀半。⽰例2：
输⼊：nums=[3,8,20]
输出：3
解释：初始nums的和为3+8+20=31。
以下是将数组和减少⾄少⼀半的⼀种⽅法：
选择数字20并减⼩为10。
选择数字10并减⼩为5。
选择数字3并减⼩为1.5。
最终数组为[1.5,8,5]，和为1.5+8+5=14.5。
nums的和减⼩了31-14.5=16.5，减⼩的部分超过了初始数组和的⼀半，16.5>=31/2=16.5。
我们需要3个操作实现题⽬要求，所以返回3。可以证明，⽆法通过少于3个操作使数组和减少⾄少⼀半。

提⽰：
◦ 1 <= nums.length <= 10^5
◦ 1 <= nums[i] <= 10^7

讲解算法原理

解法（贪⼼）：
贪⼼策略：
a. 每次挑选出「当前」数组中「最⼤」的数，然后「减半」；b. 直到数组和减少到⾄少⼀半为⽌。
为了「快速」挑选出数组中最⼤的数，我们可以利⽤「堆」这个数据结构。

编写代码

c++算法代码：

class Solution
{
public:
 int halveArray(vector<int>& nums) 
 {
 priority_queue<double> heap; // 创建⼀个⼤根堆 double sum = 0.0;
 for(int x : nums) // 把元素都丢进堆中，并求出累加和 {
 heap.push(x);
 sum += x;
 }
 sum /= 2.0; // 先算出⽬标和
 int count = 0;
 while(sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下 {
 double t = heap.top() / 2.0;
 heap.pop();
 sum -= t;
 count++;
 heap.push(t);
 }
 return count;
 }
};

java算法代码：

class Solution
{
 public int halveArray(int[] nums) 
 {
 // 创建⼀个⼤根堆
 PriorityQueue<Double> heap = new PriorityQueue<>((a, b) -> 
b.compareTo(a)); 
 double sum = 0.0;
 for(int x : nums) // 把元素都丢进堆中，并求出累加和
 {
 heap.offer((double)x);
 sum += x;
 }
 sum /= 2.0; // 先算出⽬标和
 int count = 0;
 while(sum > 0) // 依次取出堆顶元素减半，直到减到之前的⼀半以下 {
 double t = heap.poll() / 2.0;
 sum -= t;
 count++;
 heap.offer(t);
 }
 return count;
 }
}