深圳哪个网站建设公司好,名雕装饰,重庆奉节网站建设公司,图片制作带字前言:贪心无套路 本质: 局部最优去推导全局最优 两个极端 贪心算法的难度一般要么特别简单,要么特别困难,所以我们只能多见识多做题,记住无需数学证明,因为两道贪心基本上毫无关系,我们只需要去思考局部最优即可 贪心的小例子 比如有一堆钞票#xff0c;你可以拿走十张#x… 前言:贪心无套路 本质: 局部最优去推导全局最优 两个极端 贪心算法的难度一般要么特别简单,要么特别困难,所以我们只能多见识多做题,记住无需数学证明,因为两道贪心基本上毫无关系,我们只需要去思考局部最优即可 贪心的小例子 比如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿 那肯定是每次拿最大的就行,局部最优就是每次拿最大数额的钞票,全局最优就是最后数额的总和是最大的. 贪心无套路!!! 这里贪心没有任何的模板总结,因为解决不同问题的贪心策略是完全不同的,我们不需要严格的数学证明,如果面对一道题你有这么一种贪心的策略,同时你找不到任何明显的反例,那么就可以照着这个思路来思考问题... LeetCode T455 分发饼干
题目链接:455. 分发饼干 - 力扣LeetCode 题目思路: 这题我们有两种思路可以解决问题 1.优先考虑胃口:大饼干喂饱大胃口 这里的局部最优就是充分利用大饼干来喂饱小孩,全局最优就是喂饱尽可能多的小孩 (尽可能让吃饱的人多) 2.优先考虑饼干:小饼干先喂饱小胃口 这里的局部最优是花费掉最小的饼干,让小饼干物尽其用,全局最优是使饼干的花费更有性价比. (尽可能让饼干发挥最大的效果) 题目代码
//解法一:
class Solution {int count 0;int start 0;public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);for(int i 0;is.length startg.length;i){if(s[i]g[start]){start;count;}}return count;}
}//解法2
class Solution {int count 0;int start ;public int findContentChildren(int[] g, int[] s) {start s.length-1;Arrays.sort(g);Arrays.sort(s);for(int i g.length-1;i0;i--){if(start 0 s[start]g[i]){start--;count;}}return count;}
} LeetCode T376 摆动序列 题目链接:376. 摆动序列 - 力扣LeetCode
前言 这题我们看到可以删除数组中的元素也可以不删除可能就吓到了,其实是这道题可以用动态规划或者贪心的策略去解决问题,这里我们还是用贪心的解法去解决问题,具体动态规划的思路可以参照网站:代码随想录 (programmercarl.com) 摆动数列的定义 做这题之前我们得明白什么是摆动序列,举个例子[2,6,1,9,3]这个数组,呈现一个波动变化的形态,就称为摆动序列 如果序列只有两个元素,这里就认为摆动序列的长度为2,默认有两个摆动 题目思路: 这题我们首先要考虑情况,我列出以下三种情况: 1.首末元素 2.上下有平坡 3.单调有平坡 变量定义 curDiff:记录当前差值 假设目前遍历到的元素为i ,curDiff nums[i1] - nums[i] preDiff:记录之前的差值 preDiff nums[i] - nums[i-1] count 记录结果,为了满足默认首尾元素的情况,我们默认count从1开始取值 我们只需要遍历一次数组,满足前后diff不同号即可 注意不能写成curDiff0这种情况,因为这样就表示从高或者低值到平坡,是不增加波动的 最后每次结束让pre更新为cur就可以了 这是一个错误的思路,我们是只有遇到了坡度变化才会让pre更新 for(int i 0;inums.length-1;i){curDiff nums[i1] - nums[i];if((curDiff0 preDiff0 ) || (curDiff0 preDiff0)){count;preDiff curDiff;}} 代码模板:
class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length1){return nums.length;}int preDiff 0;int count 1;int curDiff 0;for(int i 0;inums.length-1;i){curDiff nums[i1] - nums[i];if((curDiff0 preDiff0 ) || (curDiff0 preDiff0)){count;preDiff curDiff;}}return count;}
} LeetCode T53 最大子数组和
题目链接:53. 最大子数组和 - 力扣LeetCode 题目思路: 贪心贪的是哪里呢 如果 -2 1 在一起计算起点的时候一定是从 1 开始计算因为负数只会拉低总和这就是贪心贪的地方 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。 全局最优选取最大“连续和” 局部最优的情况下并记录最大的“连续和”可以推出全局最优。 从代码角度上来讲遍历 nums从头开始用 count 累积如果 count 一旦加上 nums[i]变为负数那么就应该从 nums[i1]开始从 0 累积 count 了因为已经变为负数的 count只会拖累总和。 这相当于是暴力解法中的不断调整最大子序和区间的起始位置。 定义变量: count:记录局部和 sum:记录目前出现的最大和 思路:一层for循环遍历数组,每次遇到连续子数组之和为负数的时候,就从下一个元素继续开始叠加,每次叠加一个元素对sum进行一次更新. 题目代码:
class Solution {public int maxSubArray(int[] nums) {int count 0;//目前值int sum Integer.MIN_VALUE;//目前出现的最大值for(int i 0;inums.length;i){countnums[i];sum Math.max(count,sum);if(count 0){count 0;}}return sum;}
}
