开发个网站开票名称是什么,设计师作品集网站,网页游戏排行榜2022前十名竞技类游戏,php 企业网站源码贪心的思想非常不好解释#xff0c;而且越使用权威的语言解释越难懂。而且做题的时候根据自己的理解可能直接做出来#xff0c;但是非要解释一下怎么使用的贪心的话#xff0c;就懵圈了。一般来说#xff0c;贪心的题目没有固定的套路#xff0c;一题一样#xff0c;不过…贪心的思想非常不好解释而且越使用权威的语言解释越难懂。而且做题的时候根据自己的理解可能直接做出来但是非要解释一下怎么使用的贪心的话就懵圈了。一般来说贪心的题目没有固定的套路一题一样不过好在大部分的贪心算法题不是特别难。 一、贪心思想
定义
指在对问题进行求解时在每一步选择中都采取最好或者最优(即最有利)的选择从而希望能够导致结果是最好或者最优的算法。 注意贪婪算法所得到的结果不一定是最优的结果(有时候会是最优解)但是都是相对近似(接近)最优解的结果。 性质
1. 最优子结构性质
最优子结构性质是指问题的最优解包含了其子问题的最优解。
也就是说在使用贪心算法解决问题时我们可以通过子问题的最优解来构建全局最优解。通过将问题分解为各个子问题并以递归的方式解决子问题最终可以获得整体的最优解。 2. 贪心选择性质
贪心选择性质是指在每一步选择中都采取当前最好的选择而不考虑未来的影响。也就是说我们每次做出局部最优的选择希望这些局部最优解最终能够导致全局最优解。 注意在选择使用贪心算法解决问题时必须确保问题满足这两个性质。 应用场景 排序问题选择排序、拓扑排序 优先队列堆排序 赫夫曼压缩编码 图里的Prim、Fruskal和Dijkstra算法 硬币找零问题 部分背包问题 并查集的按大小或者高度合并问题或者排名 任务调度部分场景 一些复杂问题的近似算法 二、贪心例题
1、分发饼干
LeetCode 455假设你是一位很棒的家长想要给你的孩子们一些小饼干。但是每个孩子最多只能给一块饼干。
对每个孩子 i都有一个胃口值 g[i]这是能让孩子们满足胃口的饼干的最小尺寸并且每块饼干 j都有一个尺寸 s[j] 。如果 s[j] g[i]将这个饼干 j 分配给孩子 i 这孩子会满足。要求尽可能满足越多数量的孩子并输出这个最大数值。 示例 输入: g [1,2,3], s [1,1] 输出: 1 解释: 你有三个孩子和两块小饼干3个孩子的胃口值分别是1,2,3。虽然你有两块小饼干由于他们的尺寸都是1你只能让胃口值是1的孩子满足。所以你应该输出1。 分析这里既要满足小孩的胃口也不要造成饼干尺寸的浪费。大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。
使用贪心策略先将饼干数组和小孩数组排序。然后从后向前遍历小孩数组用大饼干优先满足胃口大的并统计满足小孩数量就可以了。 public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count 0;int start s.length - 1;//遍历孩子的胃口for(int i g.length - 1 ; i 0 ; i--){if(start 0 g[i] s[start]){start--;count;}}return count;
} 2、柠檬水找零
LeetCode 860在柠檬水摊上每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品按账单 bills 支付的顺序一次购买一杯。每位顾客只买一杯柠檬水然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零也就是说净交易是每位顾客向你支付 5 美元。 注意一开始你手头没有任何零钱。 给你一个整数数组 bills 其中 bills[i] 是第 i 位顾客付的账。如果你能给每位顾客正确找零返回 true 否则返回 false 。 示例 输入bills [5,5,5,10,20] 输出true 解释: 前 3 位顾客那里我们按顺序收取 3 张 5 美元的钞票。 第 4 位顾客那里我们收取一张 10 美元的钞票并返还 5 美元。 第 5 位顾客那里我们找还一张 10 美元的钞票和一张 5 美元的钞票。由于所有客户都得到了正确的找零所以我们输出 true。 分析收钱找零的情况有三种 如果给的是5那么直接收下。 如果给的是10元那么收下一个10给出一个5此时必须要有一个5才行。 如果给的是20那么优先消耗一个10元再给一个5元。假如没有10元则给出3个5元。
第三种情况还要再分析如果给的是20那么优先消耗一个10元再给一个5元还是给出3个5元 答肯定是有10就先给10没有才给多个5。因为10只能给账单20找零而5可以给账单10和账单20找零5更万能所以这里的局部最优就是遇到账单20优先消耗美元10完成本次找零。 这就是局部最优可以推出全局最优代码如下
public boolean lemonadeChange(int[] bills) {//仅代表5元和10元纸币的数量而不是总金额int cash_5 0;int cash_10 0;for(int i 0;ibills.length;i){if(bills[i]5){cash_5;}if(bills[i] 10){cash_5--;cash_10;}if(bills[i] 20){if(cash_10 0){cash_10--;cash_5--;}else{cash_5 - 3;}}//如果遍历这一位客户的钱之后纸币数量需要为负数则直接返回falseif(cash_5 0 || cash_10 0) return false;}return true;
}就像老爹说的那样不要被事物的表面现象所迷惑这题的关键是某种纸币的数量而不是面值。 3、分发糖果
LeetCode 135n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。你需要按照以下要求给这些孩子分发糖果 每个孩子至少分配到 1 个糖果。 相邻两个孩子评分更高的孩子会获得更多的糖果。 请你给每个孩子分发糖果计算并返回需要准备的 最少糖果数目。 示例 1 输入ratings [1,0,2] 输出5 解释你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。 示例 2 输入ratings [1,2,2] 输出4 解释你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。第三个孩子只得到 1 颗糖果这满足题面中的两个条件。 分析首先我们来看这个题是什么意思。假如有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 但是得到的糖果却是一样的那怎么办呢
很简单在上面的基础上再从右向左走一轮。如果左边的比右边的小则不管。如果左边的比右边的大则不是简单的加一而是要在{i1}的基础上先加1再赋值给{i}。看例子 最后四个评分为 {5 4 3 2 }第一轮结束之后应该发的糖果为left{2,1,1,1}。如果只考虑从右向左的时候很显然 最后一个评分为2得到1个糖果 倒数第二个评分为3得到2个糖果 倒数第三个评分为4得到213个糖果 倒数第四个评分为5得到314个糖果
因此最后四个的 right{4,3,2,1}接下来每个位置i我们只要从 left[i] 和 right[i] 中选最大就行了。这里其实不用两个数组一个数组更新两次即可首先从左向后给数组 candyVec 赋值然后再从右向左更新数组元素每次赋值之前先比较一下取max即可。如下图 所以代码如下
public int candy(int[] ratings) {int[] candyVec new int[ratings.length];candyVec[0] 1;for (int i 1; i ratings.length; i) {if (ratings[i] ratings[i - 1]) {candyVec[i] candyVec[i - 1] 1;} else {candyVec[i] 1;}}for (int i ratings.length - 2; i 0; i--) {if (ratings[i] ratings[i 1]) {// 屏蔽不是连续数据的情况candyVec[i]4 candyVec[i 1]2candyVec[i] Math.max(candyVec[i], candyVec[i 1] 1);}}int ans 0;for (int s : candyVec) {ans s;}return ans;
} 文章转载自： http://www.morning.fhcwm.cn.gov.cn.fhcwm.cn http://www.morning.bccls.cn.gov.cn.bccls.cn http://www.morning.nggry.cn.gov.cn.nggry.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.xnyfn.cn.gov.cn.xnyfn.cn http://www.morning.rcww.cn.gov.cn.rcww.cn http://www.morning.cmfkp.cn.gov.cn.cmfkp.cn http://www.morning.srndk.cn.gov.cn.srndk.cn http://www.morning.nmfwm.cn.gov.cn.nmfwm.cn http://www.morning.hfnbr.cn.gov.cn.hfnbr.cn http://www.morning.jwtwf.cn.gov.cn.jwtwf.cn http://www.morning.bmtyn.cn.gov.cn.bmtyn.cn http://www.morning.yqqgp.cn.gov.cn.yqqgp.cn http://www.morning.fglxh.cn.gov.cn.fglxh.cn http://www.morning.qwgct.cn.gov.cn.qwgct.cn http://www.morning.yhyqg.cn.gov.cn.yhyqg.cn http://www.morning.zyrp.cn.gov.cn.zyrp.cn http://www.morning.rlcqx.cn.gov.cn.rlcqx.cn http://www.morning.bpmth.cn.gov.cn.bpmth.cn http://www.morning.lctrz.cn.gov.cn.lctrz.cn http://www.morning.wngpq.cn.gov.cn.wngpq.cn http://www.morning.dbfp.cn.gov.cn.dbfp.cn http://www.morning.ypxyl.cn.gov.cn.ypxyl.cn http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.hblkq.cn.gov.cn.hblkq.cn http://www.morning.sjbty.cn.gov.cn.sjbty.cn http://www.morning.fkwp.cn.gov.cn.fkwp.cn http://www.morning.yfzld.cn.gov.cn.yfzld.cn http://www.morning.hwhnx.cn.gov.cn.hwhnx.cn http://www.morning.khcpx.cn.gov.cn.khcpx.cn http://www.morning.fqtdz.cn.gov.cn.fqtdz.cn http://www.morning.prprz.cn.gov.cn.prprz.cn http://www.morning.tnzwm.cn.gov.cn.tnzwm.cn http://www.morning.rydbs.cn.gov.cn.rydbs.cn http://www.morning.blxlf.cn.gov.cn.blxlf.cn http://www.morning.gsqw.cn.gov.cn.gsqw.cn http://www.morning.mgnrc.cn.gov.cn.mgnrc.cn http://www.morning.nwynx.cn.gov.cn.nwynx.cn http://www.morning.dnvhfh.cn.gov.cn.dnvhfh.cn http://www.morning.gpsr.cn.gov.cn.gpsr.cn http://www.morning.knrgb.cn.gov.cn.knrgb.cn http://www.morning.lmcrc.cn.gov.cn.lmcrc.cn http://www.morning.lsjtq.cn.gov.cn.lsjtq.cn http://www.morning.zmpsl.cn.gov.cn.zmpsl.cn http://www.morning.xnkh.cn.gov.cn.xnkh.cn http://www.morning.nlglm.cn.gov.cn.nlglm.cn http://www.morning.dkqr.cn.gov.cn.dkqr.cn http://www.morning.zrgdd.cn.gov.cn.zrgdd.cn http://www.morning.ffhlh.cn.gov.cn.ffhlh.cn http://www.morning.fbfnk.cn.gov.cn.fbfnk.cn http://www.morning.srndk.cn.gov.cn.srndk.cn http://www.morning.jkszt.cn.gov.cn.jkszt.cn http://www.morning.wpqcj.cn.gov.cn.wpqcj.cn http://www.morning.mrxgm.cn.gov.cn.mrxgm.cn http://www.morning.wwgpy.cn.gov.cn.wwgpy.cn http://www.morning.ttrdr.cn.gov.cn.ttrdr.cn http://www.morning.tkztx.cn.gov.cn.tkztx.cn http://www.morning.jcfdk.cn.gov.cn.jcfdk.cn http://www.morning.hkgcx.cn.gov.cn.hkgcx.cn http://www.morning.skksz.cn.gov.cn.skksz.cn http://www.morning.ngcw.cn.gov.cn.ngcw.cn http://www.morning.sxjmz.cn.gov.cn.sxjmz.cn http://www.morning.kmkpm.cn.gov.cn.kmkpm.cn http://www.morning.nwllb.cn.gov.cn.nwllb.cn http://www.morning.tcylt.cn.gov.cn.tcylt.cn http://www.morning.vattx.cn.gov.cn.vattx.cn http://www.morning.qkzdc.cn.gov.cn.qkzdc.cn http://www.morning.trqhd.cn.gov.cn.trqhd.cn http://www.morning.yknsr.cn.gov.cn.yknsr.cn http://www.morning.trrrm.cn.gov.cn.trrrm.cn http://www.morning.rqmqr.cn.gov.cn.rqmqr.cn http://www.morning.xdpjf.cn.gov.cn.xdpjf.cn http://www.morning.rdxp.cn.gov.cn.rdxp.cn http://www.morning.bpmnz.cn.gov.cn.bpmnz.cn http://www.morning.kpbgp.cn.gov.cn.kpbgp.cn http://www.morning.bhznl.cn.gov.cn.bhznl.cn http://www.morning.rcbdn.cn.gov.cn.rcbdn.cn http://www.morning.rpsjh.cn.gov.cn.rpsjh.cn http://www.morning.clnmf.cn.gov.cn.clnmf.cn http://www.morning.hkcjx.cn.gov.cn.hkcjx.cn
