算法通关村第十七关-青铜挑战贪心算法思想
大家好我是苏麟 , 今天说说贪心算法 .
贪心思想很难用理论解释，本文我们先通过案例来感受一下贪心是如何解决问题的
大纲
- 难以理解的贪心算法
- 贪心问题举例
- 分发饼干
- 柠檬水找零
- 分发糖果
难以理解的贪心算法
贪心的思想非常不好解释，而且越使用权威的语言解释越难懂。而且做题的时候根据自己的理解直接做可能能做出来，而非要解释一下怎么使用的贪心的话反而懵圈了
更郁闷的是贪心的题目没有固定的套路，一题一样，好在大部分的贪心算法题不是特别难，因此公认的贪心学习法则是”直接做题，不考虑贪不贪心“，本竟我们就从一些经典题目中寻找一些“哲学规律”
贪婪算法(贪心算法)是指在对问题进行求解时，在每一步选择中都采取最好或者最优(即最有利)的选择，从而希望能够导致结果是最好或者最优的算法贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)，但是都是相对近似(接近)最优解的结果
那贪心是否一定能得到最优解呢?《算法导论》给出了最明确的答案一一贪心算法不能保证一定能得到最优解，但是对很多问题确实可以得到最优解。
我们看一个小例子 :
教室调度问题
假设有如下课程表，你希望将尽可能多的课程安排在某间教室上。
你没法让这些课都在这间教室上，因为有些课的上课时间有冲突。
你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢？
这个问题好像很难，不是吗？实际上，算法可能简单得让你大吃一惊。具体做法如下。
(1) 选出结束最早的课，它就是要在这间教室上的第一堂课。
(2) 接下来，必须选择第一堂课结束后才开始的课。同样，你选择结束最早的课，这将是要
在这间教室上的第二堂课。
重复这样做就能找出答案！下面来试一试。美术课的结束时间最早，为10:00 a.m.，因此它
就是第一堂课。
接下来的课必须在10:00 a.m.后开始，且结束得最早。
英语课不行，因为它的时间与美术课冲突，但数学课满足条件。最后，计算机课与数学课的
时间是冲突的，但音乐课可以。
因此将在这间教室上如下三堂课。
很多人都跟我说，这个算法太容易、太显而易见，肯定不对。但这正是贪婪算法的优点——
简单易行！贪婪算法很简单：每步都采取最优的做法。在这个示例中，你每次都选择结束最早的
课。用专业术语说，就是你每步都选择局部最优解，最终得到的就是全局最优解。信不信由你，
对于这个调度问题，上述简单算法找到的就是最优解！
显然，贪婪算法并非在任何情况下都行之有效，但它易于实现！
贪心问题举例
分发饼干
描述 :
假设你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。
对每个孩子 i，都有一个胃口值 g[i]，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 j，都有一个尺寸 s[j] 。如果 s[j] >= g[i]，我们可以将这个饼干 j 分配给孩子 i ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
题目 :
LeetCode 455. 分发饼干 :
分发饼干
分析 :
这里既要满足小孩的胃口，也不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子，那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的，充分利用饼千尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩所以，这里可以使用贪心策略，先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组，用大饼干优先满足胃口大的，并统计满足小孩数量就可以了。也就是这样
这里我们就考虑胃口，大饼干先喂饱大胃口，最后看能满足几个孩子的需要就行。
解析 ;
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(s);
Arrays.sort(g);
int n = g.length - 1;
int start = s.length - 1;
int count = 0;
for(int index = n;index >= 0;index--){
if(start >= 0 && s[start] >= g[index]){
count++;
start--;
}
}
return count;
}
}
柠檬水找零
描述 :
在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。
每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。
注意，一开始你手头没有任何零钱。
给你一个整数数组 bills ，其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。
题目 :
LeetCode 860.柠檬水找零 :
柠檬水找零
分析 :
由于顾客只可能给你三个面值的钞票，而且我们一开始没有任何钞票，因此我们拥有的钞票面值只可能是 5美元，10 美元和 20 美元三种。基于此，我们可以进行如下的分类讨论。
- 5 美元，由于柠檬水的价格也为 5 美元，因此我们直接收下即可。
- 10 美元，我们需要找回 5 美元，如果没有 5 美元面值的钞票，则无法正确找零。
- 20 美元，我们需要找回 15 美元，此时有两种组合方式，一种是一张 10 美元和 5 美元的钞票，一种是 3 张 5 美元的钞票，如果两种组合方式都没有，则无法正确找零。当可以正确找零时，两种找零的方式中我们更倾向于第一种，即如果存在 5 美元和 10 美元，我们就按第一种方式找零，否则按第二种方式找零，因为需要使用 5 美元的找零场景会比需要使用 10 美元的找零场景多，我们需要尽可能保留 5 美元的钞票。
基于此，我们维护两个变量表示当前手中拥有的 5 美元和 10 美元钞票的张数，从前往后遍历数组分类讨论即可。
解析 ;
class Solution {
public boolean lemonadeChange(int[] bills) {
int count_5 = 0;
int count_10 = 0;
for(int i = 0;i < bills.length ;i++){
if(bills[i] == 5){
count_5++;
}else if(bills[i] == 10){
count_10++;
count_5--;
}else if(bills[i] == 20){
if(count_10 > 0){
count_10--;
count_5--;
}else{
count_5 -= 3;
}
}
if(count_5 < 0){
return false;
}
}
return true;
}
}
分发糖果
描述 :
n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻两个孩子评分更高的孩子会获得更多的糖果。
请你给每个孩子分发糖果，计算并返回需要准备的 最少糖果数目 。
题目 :
LeetCode 135. 分发糖果 :
分发糖果
分析 :
首先我们来看这个题是什么意思。假如有5个孩子，因为每个孩子至少一个糖果，所以一定要花出去的最少糖果是{1,1,1,1,1}一共5个。
然后是相邻孩子评分更高的能获得更多的糖果。假如评分为(1,2,3,2)，则最少花出去的糖果为1,2,3,1，因为前三个评分在增加，则糖果必须递增，因此分别要发的糖果最少为(1,2,3)个，最后一个因为评分低了所以我们给最少1个。
另外，假如评分相等，例如(1,2,2,2,2}，根据题目要求，则后面重复的都给一个的就行了，也就是分别给{1,2,1,1,1}个。
我们根据题意从左向后依次比较，确定第一轮要预发的糖果数量，只要右边的比左边的大，就一直首先，加1;如果右边比左边小，就设置为1，然后继续向右比较。结果如下:
此时有人就有疑问了，题目是要求相邻的孩子评分高的孩子必须获得更多的糖果，上面序列的后面几个评分为 4、3、2 但是得到的糖果却是一样的，那怎么办呢?
很简单，我们在上面的基础上，再从右向左走一轮。如果左边的比右边的小，则不管。如果左边的比右边的大，则不是简单的加一，而是要在fi+1的基础上，先加1再赋值给你。看例子:
最后四个评分为{5 4 3 2 }，第一轮结束之后应该发的糖果为left=2,1,1,1。
如果当我们只考虑从右向左的时候，很显然
- 最后一个评分为2得到1个糖果
- 倒数第二个评分为3，得到2个糖果
- 倒数第三个评分为4，得到2+1=3个糖果
- 倒数第四个评分为5，得到3+1=4个糖果
因此最后四个的right=(4,3,2,1}，接下来每个位置i我们只要从 left 和 right 中选最大就行了。不过这里我们其实不用两个数组，一个数组更新两次即可，首先从左向后给数组 candyVec 赋值，然后再从右向左更新数组元素，每次赋值之前先比较一下取max即可。
解析 ;
class Solution {
public int candy(int[] ratings) {
int[] arr = new int[ratings.length];
arr[0] = 1;
for(int i = 1;i < ratings.length;i++){
if(ratings[i] > ratings[i - 1]){
arr[i] = arr[i - 1] + 1;
}else{
arr[i] = 1;
}
}
for(int i = ratings.length - 2;i >= 0 ;i--){
if(ratings[i] > ratings[i + 1]){
arr[i] = Math.max(arr[i],arr[i + 1] + 1);
}
}
int res = 0;
for(int a : arr){
res += a;
}
return res;
}
}
这期就到这里 , 下期见!