贪心算法题目详解

题目一. 柠檬⽔找零

1. 题⽬链接：860. 柠檬⽔找零

https://leetcode.cn/problems/lemonade-change/description/

2. 题⽬描述

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

3. 解法（贪⼼）：

贪⼼策略： 分情况讨论：

a. 遇到 5 元钱，直接收下；

b. 遇到 10 元钱，找零 5 元钱之后，收下；

c. 遇到 20 元钱：

i. 先尝试凑 10 + 5 的组合；

ii. 如果凑不出来，拼凑 5 + 5 + 5 的组合；

4.代码

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.题目链接：2208. 将数组和减半的最少操作次数

https://leetcode.cn/problems/minimum-operations-to-halve-array-sum/description/

2. 题⽬描述：

3. 解法（贪⼼）：

贪⼼策略：

a. 每次挑选出「当前」数组中「最⼤」的数，然后「减半」；

b. 直到数组和减少到⾄少⼀半为⽌。 为了「快速」挑选出数组中最⼤的数，我们可以利⽤「堆」这个数据结构。

4.代码

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;
 }
}

题目三. 最⼤数

1. 题⽬链接：179. 最⼤数

https://leetcode.cn/problems/largest-number/description/

2. 题⽬描述

3. 解法（贪⼼）：

可以先优化： 将所有的数字当成字符串处理，那么两个数字之间的拼接操作以及⽐较操作就会很⽅便。 贪⼼策略：
按照题⽬的要求，重新定义⼀个新的排序规则，然后排序即可。 排序规则：

a. 「A 拼接 B」 ⼤于 「B 拼接 A」，那么 A 在前，B 在后；

b. 「A 拼接 B」 等于 「B 拼接 A」，那么 A B 的顺序⽆所谓；

c. 「A 拼接 B」 ⼩于 「B 拼接 A」，那么 B 在前，A 在后；

4.代码

class Solution 
{
 public String largestNumber(int[] nums) 
 {
 // 优化：把所有的数转化成字符串 
 int n = nums.length;
 String[] strs = new String[n];
 
 for(int i = 0; i < n; i++) strs[i] = "" + nums[i];
 // 排序 
 Arrays.sort(strs, (a, b) -> 
 {
 return (b + a).compareTo(a + b);
 });
 // 提取结果 
 StringBuffer ret = new StringBuffer();
 for(String s : strs) ret.append(s);
 if(ret.charAt(0) == '0') return "0";
 return ret.toString();
 }
}