算法通关村第十七关|青铜|贪心:无招胜有招
2023-12-14 23:25:26
贪心常见的经典应用场景:
● 排序问题:选择排序,拓扑排序
● 优先队列:堆排序
● 赫夫曼压缩编码
● 图:Prim Fruskal Dijkstra 算法
● 硬币找零问题
● 分数背包问题
● 并查集:按大小或者高度合并问题或者排名
● 任务调度部分场景
● 一些复杂问题的近似算法
1.分发饼干
原题:力扣455.
贪心策略就是将两个数组排序,然后遍历小孩数组,优先用大饼干喂给胃口大的小孩。
这里的 g 是胃口数组, s 是饼干数组
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int count = 0;
int start = s.length - 1;
for (int index = g.length - 1; index >= 0; index--) {
if (start >= 0 && g[index] <= s[start]) {
start--;
count++;
}
}
return count;
}
2.柠檬水找零
原题:力扣860.
分析收钱情况:
● 如果给 5 元,直接收下
● 如果给 10 元,收下 10 元,找零 5 元
● 如果给 20 元,收下 20 元,找零 10 元和 5 元或者三个 5 元
第二种情况下必须有 5 元才能找零。
第三种情况下优先找零 10 元,然后再找零 5 元,因为 5 元可以用在第二种和第三种情况,而 10 元只能用在第三种情况下。
代码直接列举情况就好了。
public boolean lemonadeChange(int[] bills) {
// 记录两种钞票的数目
int cash_5 = 0;
int cash_10 = 0;
for (int i = 0; i < bills.length; i++) {
if (bills[i] == 5) {
cash_5++;
} else if (bills[i] == 10) {
cash_5--;
cash_10++;
} else if (bills[i] == 20) {
if (cash_10 > 0) {
cash_10--;
cash_5--;
} else {
cash_5 -= 3;
}
}
if (cash_5 < 0 || cash_10 < 0) {
return false;
}
}
return true;
}
3.分发糖果
原题:力扣135.
需要注意,相邻的两个孩子的评分相同的时候,就不存在一个比另一个大的情况了,那么就不需要考虑糖果分配,只需给其中一个孩子分配 1 个基本糖果即可。
public int candy(int[] ratings) {
int[] candyVec = new int[ratings.length];
candyVec[0] = 1;
// 先从左到右遍历一次
for (int i = 1; i < ratings.length; i++) {
if (rating[i] > ratings[i - 1]) {
candyVec[i] = candyVec[i - 1] + 1;
} else {
// 相等的时候也赋值 1
candyVec[i] = 1;
}
}
// 再从右向左遍历一次
for (int i = ratings.length - 2; i >= 0; i--) {
if (ratings[i] > ratings[i + 1]) {
candyVec[i] = Math.max(candyVec[i], candyVec[i + 1] + 1);
}
}
int ans = 0;
for (int s : candyVec) {
ans += s;
}
return ans;
}
如果对您有帮助,请点赞关注支持我,谢谢!?
如有错误或者不足之处,敬请指正!?
个人主页:星不易 ?
算法通关村专栏:不易|算法通关村 ?
文章来源:https://blog.csdn.net/m0_57130776/article/details/134863134
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!