淮安网站开发,被禁止访问网站怎么办,距离我最近的装修公司电话,做塑料的网站有哪些代码随想录刷题day27丨455.分发饼干 ,376. 摆动序列 ,53. 最大子序和
1.贪心算法理论基础 贪心的本质是选择每一阶段的局部最优#xff0c;从而达到全局最优。 这么说有点抽象#xff0c;来举一个例子#xff1a; 例如#xff0c;有一堆钞票#xff0c;你可以拿走十张从而达到全局最优。 这么说有点抽象来举一个例子 例如有一堆钞票你可以拿走十张如果想达到最大的金额你要怎么拿 指定每次拿最大的最终结果就是拿走最大数额的钱。 每次拿最大的就是局部最优最后拿走最大数额的钱就是推出全局最优。 再举一个例子如果是 有一堆盒子你有一个背包体积为n如何把背包尽可能装满如果还每次选最大的盒子就不行了。这时候就需要动态规划。 贪心算法并没有固定的套路。难点就是如何通过局部最优推出整体最优。 靠自己手动模拟如果模拟可行就可以试一试贪心策略如果不可行可能需要动态规划。 如何验证可不可以用贪心算法呢 最好用的策略就是举反例如果想不到反例那么就试一试贪心吧。 贪心算法一般分为如下四步 将问题分解为若干个子问题找出适合的贪心策略求解每一个子问题的最优解将局部最优解堆叠成全局最优解
2.题目
2.1分发饼干 题目链接455. 分发饼干 - 力扣LeetCode 视频讲解贪心算法你想先喂哪个小孩| LeetCode455.分发饼干_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0455.%E5%88%86%E5%8F%91%E9%A5%BC%E5%B9%B2.html 解题思路贪心 为了满足更多的小孩就不要造成饼干尺寸的浪费。 大尺寸的饼干既可以满足胃口大的孩子也可以满足胃口小的孩子那么就应该优先满足胃口大的。 这里的局部最优就是大饼干喂给胃口大的充分利用饼干尺寸喂饱一个全局最优就是喂饱尽可能多的小孩。 代码 class Solution {public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int result 0;int index s.length -1;for(int i g.length - 1;i 0;i--){if(index 0 s[index] g[i]){result;index--;}}return result;}
}总结 小饼干先喂饱小胃口也可以
2.2摆动序列 题目链接376. 摆动序列 - 力扣LeetCode 视频讲解贪心算法寻找摆动有细节| LeetCode376.摆动序列_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html 解题思路贪心 局部最优删除单调坡度上的节点不包括单调坡度两端的节点那么这个坡度就可以有两个局部峰值。 整体最优整个序列有最多的局部峰值从而达到最长摆动序列。 在计算是否有峰值的时候大家知道遍历的下标 i 计算 prediffnums[i] - nums[i-1] 和 curdiffnums[i1] - nums[i]如果prediff 0 curdiff 0 或者 prediff 0 curdiff 0 此时就有波动就需要统计。 本题要考虑三种情况 情况一上下坡中有平坡 情况二数组首尾两端 针对序列[2,5]可以假设为[2,2,5]这样它就有坡度了即 preDiff 0result 初始为 1默认最右面有一个峰值 情况三单调坡中有平坡 我们应该什么时候更新 prediff 呢 我们只需要在 这个坡度 摆动变化的时候更新 prediff 就行这样 prediff 在 单调区间有平坡的时候 就不会发生变化造成我们的误判。 代码 class Solution {public int wiggleMaxLength(int[] nums) {if(nums.length 1){return nums.length;}//当前差值int curDiff 0;//上一个差值int preDiff 0;//默认最右边有一个峰值int count 1;//遍历到倒数第二个就行最右边的已经默认了for(int i 0;i nums.length -1;i){curDiff nums[i 1] - nums[i];if((curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)){count;preDiff curDiff;}}return count;}
}总结 为什么 preDiff curDiff 放在条件判断内部这个位置 为了保证只有在波动方向改变时才更新 preDiff。如果波动方向没有变化即不满足 (curDiff 0 preDiff 0) || (curDiff 0 preDiff 0)那么 preDiff 保持不变等待下一次有效的波动。
2.3最大子序和 题目链接53. 最大子数组和 - 力扣LeetCode 视频讲解贪心算法的巧妙需要慢慢体会LeetCode53. 最大子序和_哔哩哔哩_bilibili 文档讲解https://programmercarl.com/0053.%E6%9C%80%E5%A4%A7%E5%AD%90%E5%BA%8F%E5%92%8C.html 解题思路贪心 局部最优当前“连续和”为负数的时候立刻放弃从下一个元素重新计算“连续和”因为负数加上下一个元素 “连续和”只会越来越小。全局最优选取最大“连续和”局部最优的情况下并记录最大的“连续和”可以推出全局最优。 代码 class Solution {public int maxSubArray(int[] nums) {int result Integer.MIN_VALUE;int count 0;for(int i 0;i nums.length;i){count nums[i];if(count result){result count;}if(count 0){count 0;}}return result;}
}总结 遇到连续和为负数才更新起始位置。并不是遇到负数就更新。
