wordpress隐藏rss对seo的认识和理解
代码随想录刷题day27丨455.分发饼干 ,376. 摆动序列 ,53. 最大子序和
1.贪心算法理论基础
-
贪心的本质是选择每一阶段的局部最优，从而达到全局最优。
-
这么说有点抽象，来举一个例子：
例如，有一堆钞票，你可以拿走十张，如果想达到最大的金额，你要怎么拿？
指定每次拿最大的，最终结果就是拿走最大数额的钱。
每次拿最大的就是局部最优，最后拿走最大数额的钱就是推出全局最优。
-
再举一个例子如果是 有一堆盒子，你有一个背包体积为n，如何把背包尽可能装满，如果还每次选最大的盒子，就不行了。这时候就需要动态规划。
-
贪心算法并没有固定的套路。难点就是如何通过局部最优，推出整体最优。
-
靠自己手动模拟，如果模拟可行，就可以试一试贪心策略，如果不可行，可能需要动态规划。
-
如何验证可不可以用贪心算法呢？
- 最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。
-
贪心算法一般分为如下四步：
- 将问题分解为若干个子问题
- 找出适合的贪心策略
- 求解每一个子问题的最优解
- 将局部最优解堆叠成全局最优解
2.题目
2.1分发饼干
-
题目链接：455. 分发饼干 - 力扣（LeetCode）
-
视频讲解：贪心算法，你想先喂哪个小孩？| LeetCode：455.分发饼干_哔哩哔哩_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）
-
视频讲解：贪心算法，寻找摆动有细节！| LeetCode：376.摆动序列_哔哩哔哩_bilibili
-
文档讲解：https://programmercarl.com/0376.%E6%91%86%E5%8A%A8%E5%BA%8F%E5%88%97.html
-
解题思路：贪心
-
-
局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
整体最优：整个序列有最多的局部峰值，从而达到最长摆动序列。
-
在计算是否有峰值的时候，大家知道遍历的下标 i ，计算 prediff（nums[i] - nums[i-1]） 和 curdiff（nums[i+1] - nums[i]），如果
prediff < 0 && curdiff > 0或者prediff > 0 && curdiff < 0此时就有波动就需要统计。 -
本题要考虑三种情况：
-
情况一：上下坡中有平坡
-
情况二：数组首尾两端
-
针对序列[2,5]，可以假设为[2,2,5]，这样它就有坡度了即 preDiff = 0，result 初始为 1（默认最右面有一个峰值）
-
-
情况三：单调坡中有平坡
- 我们应该什么时候更新 prediff 呢？
- 我们只需要在 这个坡度 摆动变化的时候，更新 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）
-
视频讲解：贪心算法的巧妙需要慢慢体会！LeetCode：53. 最大子序和_哔哩哔哩_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;} } -
总结：
- 遇到连续和为负数才更新起始位置。并不是遇到负数就更新。