医院网站加快建设方案,广州网络平台,视频网站 移动 模板,淄博刚刚发布紧急通知大家好我是苏麟 , 今天说说贪心算法 . 贪心思想很难用理论解释#xff0c;本文我们先通过案例来感受一下贪心是如何解决问题的 大纲 难以理解的贪心算法贪心问题举例分发饼干柠檬水找零分发糖果 难以理解的贪心算法
贪心的思想非常不好解释#xff0c;而且越使用权威的语言解…大家好我是苏麟 , 今天说说贪心算法 . 贪心思想很难用理论解释本文我们先通过案例来感受一下贪心是如何解决问题的 大纲 难以理解的贪心算法贪心问题举例分发饼干柠檬水找零分发糖果 难以理解的贪心算法
贪心的思想非常不好解释而且越使用权威的语言解释越难懂。而且做题的时候根据自己的理解直接做可能能做出来而非要解释一下怎么使用的贪心的话反而懵圈了
更郁闷的是贪心的题目没有固定的套路一题一样好在大部分的贪心算法题不是特别难因此公认的贪心学习法则是”直接做题不考虑贪不贪心“本竟我们就从一些经典题目中寻找一些“哲学规律”
贪婪算法(贪心算法)是指在对问题进行求解时在每一步选择中都采取最好或者最优(即最有利)的选择从而希望能够导致结果是最好或者最优的算法贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)但是都是相对近似(接近)最优解的结果
那贪心是否一定能得到最优解呢?《算法导论》给出了最明确的答案一一贪心算法不能保证一定能得到最优解但是对很多问题确实可以得到最优解。
我们看一个小例子 :
教室调度问题 假设有如下课程表你希望将尽可能多的课程安排在某间教室上。 你没法让这些课都在这间教室上因为有些课的上课时间有冲突。 你希望在这间教室上尽可能多的课。如何选出尽可能多且时间不冲突的课程呢
这个问题好像很难不是吗实际上算法可能简单得让你大吃一惊。具体做法如下。 (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 但是得到的糖果却是一样的那怎么办呢?
很简单我们在上面的基础上再从右向左走一轮。如果左边的比右边的小则不管。如果左边的比右边的大则不是简单的加一而是要在fi1的基础上先加1再赋值给你。看例子:
最后四个评分为{5 4 3 2 }第一轮结束之后应该发的糖果为left2,1,1,1。
如果当我们只考虑从右向左的时候很显然
最后一个评分为2得到1个糖果倒数第二个评分为3得到2个糖果倒数第三个评分为4得到213个糖果倒数第四个评分为5得到314个糖果
因此最后四个的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;}
}这期就到这里 , 下期见!
