阿里logo设计网站,网站建设人才,怎么做网页二维码,网站开发前后端分工目录
什么是贪心算法#xff1f;
leetcode455题.分发饼干
leetcode376题.摆动序列
leetcode55题.跳跃游戏I
leetcode45题.跳跃游戏II
leetcode621题.任务调度器
leetcode435题.无重叠空间
leetcode135题.分发糖果 什么是贪心算法#xff1f;
贪心算法更多的是一种思…目录
什么是贪心算法
leetcode455题.分发饼干
leetcode376题.摆动序列
leetcode55题.跳跃游戏I
leetcode45题.跳跃游戏II
leetcode621题.任务调度器
leetcode435题.无重叠空间
leetcode135题.分发糖果 什么是贪心算法
贪心算法更多的是一种思想没什么套路。
贪心顾名思义贪心就是只顾眼前的利益。只关注局部最优解当前状态的最优解不关注最后全局最优解。
举个正面例子从不同面额的人民币中选十张怎么选金额最大贪心算法就会每次都选100元面额的人民币选十张后得到的金额刚好也是全局最优解。
举个反面例子有一个承重10斤的包有五个石头重量分别是7、4、5、4、2斤怎样放才能让背包利用率最大贪心算法就会每次都选最大的先是7斤然后再选2斤总共利用了9斤。而全局最优的解法应该是4 4 2 10斤。所以贪心算法不一定是最优解。
我们学贪心算法是希望能够通过局部最优解推算出全局最优解。我们有什么套路呢答案是没有。对于一道题你无法用套路来推算能否用贪心算法做我们只能靠直觉自己多做题通过刷题来掌握常见的贪心算法题。面试时贪心考的不多我们重点掌握七八道核心题就可以了。
leetcode455题.分发饼干
455. 分发饼干 - 力扣LeetCode 思路我们可以把小尺寸的饼干尽可能地给胃口小的孩子或者大尺寸饼干尽量给胃口大的孩子。
class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);//按照胃口大小给孩子们排序Arrays.sort(s);//按照饼干尺寸给饼干排序//长度int n g.length;//孩子个数int m s.length;//饼干个数int res 0;//存放结果//遍历饼干把小尺寸饼干给小胃口的孩子for(int i 0; res n i m; i){//如果饼干尺寸大于等于孩子的胃口if(s[i] g[res]){res;//那就下一个孩子}}return res;//时间复杂度nlognmlogm 空间复杂度O1}
}
leetcode376题.摆动序列
376. 摆动序列 - 力扣LeetCode class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length 1) return nums.length;int res 1;//防止最后一个峰值丢失int pre 0;//保存前一个峰值是正是负int cur 0;//保存当前差值for(int i 0; i nums.length - 1; i){cur nums[i 1] - nums[i];if(pre 0 cur 0 || pre 0 cur 0){res;pre cur;}}return res;}
}
leetcode55题.跳跃游戏I
55. 跳跃游戏 - 力扣LeetCode 1如果从当前位置可以跳到位置i表示i之前的所有位置我们都能到达。
2我们要尽可能地跳的远一点。
3判断自己能否到达最后一个位置。
class Solution {public boolean canJump(int[] nums) {int max 0;//我们能跳到的最远的位置for(int i 0; i nums.length; i){if(max i){return false;//连i这个位置都到不了}max Math.max(max, i nums[i]);}return true;}
}
leetcode45题.跳跃游戏II
45. 跳跃游戏 II - 力扣LeetCode
class Solution {public int jump(int[] nums) {int start 0;int end 0;int res 0;int max 0;//能够跳跃的最远的位置while(end nums.length){if(max nums.length - 1) return res;for(int i start; i end; i){max Math.max(max, i nums[i]); }res;start end 1;//表示下一次跳跃的起始位置end max;//end是当前能跳跃的最远的位置}return res;}
} leetcode621题.任务调度器
621. 任务调度器 - 力扣LeetCode
class Solution {public int leastInterval(char[] tasks, int n) {//找出出现次数最多的字母int []arr new int[26];int k 0;//假设出现次数最多的字母有k种for(int i 0; i tasks.length; i){arr[tasks[i] - A];//第 i 个元素的 ASCII 码减去字符 A 的 ASCII 码得到的结果作为索引值//计算出该字母与字母 A 之间的偏移量。然后这个偏移量被用作索引值}int max 0;for(int i 0; i 26; i){max Math.max(max, arr[i]);}for(int i 0; i 26; i){if(arr[i] max){k;}}//间隔够插和不够插中的最大值max Math.max(((max - 1)*(n 1) k), tasks.length);return max;}
} leetcode435题.无重叠空间
435. 无重叠区间 - 力扣LeetCode
class Solution {//转化问题-——保存最大的区间数量使得区间不重叠//我们要留下在不重叠的情况下右边界比较小的区间//步骤对数组排序以第二个元素排序// 之后遍历数组遇到不重叠的就选择留下来public int eraseOverlapIntervals(int[][] intervals) {if(intervals.length 1) return 0;//Arrays.sort() 方法的第二个参数是一个比较器Comparator//对二维数组 intervals 按照每个子数组的第二个元素进行升序排序。/*当我们使用如 Arrays.sort() 这样的方法进行排序时元素的实际交换操作是在单独的排序算法如快速排序、归并排序等中进行的而比较器仅负责提供元素之间的相对顺序信息。这些排序算法会根据比较器的返回值来更新元素间的相对顺序并在适当的时候实际交换元素的位置最终得到一个有序序列。 */Arrays.sort(intervals, new Comparatorint[](){//重写comparepublic int compare(int[] s1, int[] s2){return s1[1] - s2[1];}});int max 1;//表示当前已经选择的不重叠区间的数量int right intervals[0][1];for(int i 1; i intervals.length; i){if(intervals[i][0] right){max;right intervals[i][1];}}return intervals.length - max;}
} leetcode135题.分发糖果
135. 分发糖果 - 力扣LeetCode
class Solution {public int candy(int[] ratings) {//孩子糖数受左右两边相邻的孩子影响/*左规则如果只受左边孩子的影响比左边的孩子分数高就比左边的孩子多获得一个糖果右规则如果只受右边孩子影响比右边孩子的分数高就多获得一个糖果整体结合左右规则来看就在判断每个孩子的糖果数中取两个规则中的较大数 */int[] left new int[ratings.length];int[] right new int[ratings.length];//填充左规则left[0] 1;for(int i 1; i ratings.length; i){if(ratings[i] ratings[i - 1]){left[i] left[i - 1] 1;}else{left[i] 1;}}//填充右规则right[ratings.length - 1] 1;for(int i ratings.length - 2; i 0; i--){if(ratings[i] ratings[i 1]){right[i] right[i 1] 1;}else{right[i] 1;}}int res 0;for(int i 0; i ratings.length; i){int max Math.max(left[i], right[i]);res max;}return res;}
} 文章转载自： http://www.morning.fhtbk.cn.gov.cn.fhtbk.cn http://www.morning.rzbgn.cn.gov.cn.rzbgn.cn http://www.morning.mjwnc.cn.gov.cn.mjwnc.cn http://www.morning.dmwjl.cn.gov.cn.dmwjl.cn http://www.morning.nqlkb.cn.gov.cn.nqlkb.cn http://www.morning.wdlyt.cn.gov.cn.wdlyt.cn http://www.morning.cwpny.cn.gov.cn.cwpny.cn http://www.morning.lsjgh.cn.gov.cn.lsjgh.cn http://www.morning.ykrss.cn.gov.cn.ykrss.cn http://www.morning.rdkt.cn.gov.cn.rdkt.cn http://www.morning.kryr.cn.gov.cn.kryr.cn http://www.morning.pffqh.cn.gov.cn.pffqh.cn http://www.morning.bfcrp.cn.gov.cn.bfcrp.cn http://www.morning.dfkmz.cn.gov.cn.dfkmz.cn http://www.morning.mfbcs.cn.gov.cn.mfbcs.cn http://www.morning.qxlhj.cn.gov.cn.qxlhj.cn http://www.morning.mkhwx.cn.gov.cn.mkhwx.cn http://www.morning.pqypt.cn.gov.cn.pqypt.cn http://www.morning.krhkn.cn.gov.cn.krhkn.cn http://www.morning.rkkh.cn.gov.cn.rkkh.cn http://www.morning.qgjwx.cn.gov.cn.qgjwx.cn http://www.morning.nhpmn.cn.gov.cn.nhpmn.cn http://www.morning.hqrr.cn.gov.cn.hqrr.cn http://www.morning.kflzy.cn.gov.cn.kflzy.cn http://www.morning.tkgjl.cn.gov.cn.tkgjl.cn http://www.morning.cfjyr.cn.gov.cn.cfjyr.cn http://www.morning.rtlg.cn.gov.cn.rtlg.cn http://www.morning.zdsdn.cn.gov.cn.zdsdn.cn http://www.morning.fylqz.cn.gov.cn.fylqz.cn http://www.morning.qwlml.cn.gov.cn.qwlml.cn http://www.morning.qxlgt.cn.gov.cn.qxlgt.cn http://www.morning.qgfkn.cn.gov.cn.qgfkn.cn http://www.morning.zqybs.cn.gov.cn.zqybs.cn http://www.morning.pbxkk.cn.gov.cn.pbxkk.cn http://www.morning.xpmwt.cn.gov.cn.xpmwt.cn http://www.morning.srnth.cn.gov.cn.srnth.cn http://www.morning.rbbzn.cn.gov.cn.rbbzn.cn http://www.morning.cfnht.cn.gov.cn.cfnht.cn http://www.morning.rfbt.cn.gov.cn.rfbt.cn http://www.morning.guanszz.com.gov.cn.guanszz.com http://www.morning.kcfnp.cn.gov.cn.kcfnp.cn http://www.morning.tbbxn.cn.gov.cn.tbbxn.cn http://www.morning.dtrz.cn.gov.cn.dtrz.cn http://www.morning.cxnyg.cn.gov.cn.cxnyg.cn http://www.morning.mm27.cn.gov.cn.mm27.cn http://www.morning.clpfd.cn.gov.cn.clpfd.cn http://www.morning.sjli222.cn.gov.cn.sjli222.cn http://www.morning.wpydf.cn.gov.cn.wpydf.cn http://www.morning.lmtbl.cn.gov.cn.lmtbl.cn http://www.morning.jqkrt.cn.gov.cn.jqkrt.cn http://www.morning.wmrgp.cn.gov.cn.wmrgp.cn http://www.morning.ahlart.com.gov.cn.ahlart.com http://www.morning.lqchz.cn.gov.cn.lqchz.cn http://www.morning.jcwrb.cn.gov.cn.jcwrb.cn http://www.morning.rrdch.cn.gov.cn.rrdch.cn http://www.morning.mrcpy.cn.gov.cn.mrcpy.cn http://www.morning.pkmw.cn.gov.cn.pkmw.cn http://www.morning.smxyw.cn.gov.cn.smxyw.cn http://www.morning.feites.com.gov.cn.feites.com http://www.morning.rbhqz.cn.gov.cn.rbhqz.cn http://www.morning.hslgq.cn.gov.cn.hslgq.cn http://www.morning.kgltb.cn.gov.cn.kgltb.cn http://www.morning.mjats.com.gov.cn.mjats.com http://www.morning.lmxrt.cn.gov.cn.lmxrt.cn http://www.morning.ctbr.cn.gov.cn.ctbr.cn http://www.morning.csnch.cn.gov.cn.csnch.cn http://www.morning.htbsk.cn.gov.cn.htbsk.cn http://www.morning.cjqqj.cn.gov.cn.cjqqj.cn http://www.morning.lgtzd.cn.gov.cn.lgtzd.cn http://www.morning.ctqbc.cn.gov.cn.ctqbc.cn http://www.morning.qykxj.cn.gov.cn.qykxj.cn http://www.morning.lsssx.cn.gov.cn.lsssx.cn http://www.morning.nlnmy.cn.gov.cn.nlnmy.cn http://www.morning.qtqk.cn.gov.cn.qtqk.cn http://www.morning.drqrl.cn.gov.cn.drqrl.cn http://www.morning.mtgkq.cn.gov.cn.mtgkq.cn http://www.morning.kcdts.cn.gov.cn.kcdts.cn http://www.morning.zcsyz.cn.gov.cn.zcsyz.cn http://www.morning.tkchg.cn.gov.cn.tkchg.cn http://www.morning.bwjws.cn.gov.cn.bwjws.cn
