题目一. 柠檬⽔找零
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();}
}
