题目一. 柠檬⽔找零

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


点赞(0) 打赏

评论列表 共有 0 条评论

暂无评论

微信公众账号

微信扫一扫加关注

发表
评论
返回
顶部