代码随想录算法训练营第27天 | 第八章 贪心算法 part01:455.分发饼干、376. 摆动序列、53. 最大子序和

第八章 贪心算法 part01

贪心算法其实就是没有什么规律可言,所以大家了解贪心算法 就了解它没有规律的本质就够了。
不用花心思去研究其规律, 没有思路就立刻看题解。
基本贪心的题目 有两个极端,要不就是特简单,要不就是死活想不出来。
学完贪心之后再去看动态规划,就会了解贪心和动规的区别。


理论基础

贪心算法理论基础篇

  • 贪心的本质是选择每一阶段的局部最优,从而达到全局最优。
  • 如何验证可不可以用贪心算法呢?:最好用的策略就是举反例,如果想不到反例,那么就试一试贪心吧。

简单题目

455.分发饼干

文章讲解

  • 用小饼干先喂饱小胃口的思路
  • 自己一开始写的
class Solution {
    public int findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int index = 0;
        int result = 0;
        for(int i = 0; i < s.length; i++){
            if(index < g.length && g[index] <= s[i]){  
                index++;
                result++;
            }
        }
        return result;
    }
}

代码随想录的

for (int i = 0; i < s.length && start < g.length; i++) {
            if (s[i] >= g[start]) {
                start++;
                count++;
            }
        }
  • 在 for 循环条件中同时检查数组长度限制,避免了在每次循环中重复检查条件。
  • 另外注意应该用index访问g,g[index] <= s[i],而不是g[i] <= s[i]

376. 摆动序列

文章讲解

思路

  • 尽量保留峰值,删除单一坡度上的节点。已知遍历的下标 i ,计算 prediff(nums[i] - nums[i-1])curdiff(nums[i+1] - nums[i]),如果prediff < 0 && curdiff > 0或者 prediff > 0 && curdiff < 0此时就有波动就需要统计。
  • 三个特殊情况
    • 情况一:上下坡中有平坡
      考虑删掉靠左边相同的节点 (preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff < 0)
    • 情况二:数组首尾两端
      为了规则统一,针对序列[2,5],可以假设为[2,2,5],这样它就有坡度了即 preDiff = 0。result初始值为1
    • 情况三:单调坡中有平坡
      只在坡度有变化时更新 prediff ,就是把preDiff = curDiff;放在if条件判断里面
class Solution {
    public int wiggleMaxLength(int[] nums) {
        if(nums.length <= 1) return nums.length;
        int result = 1;
        int preDiff = 0;
        int curDiff = 0;
        for(int i = 1; i < nums.length; i++){  //注意这里i=1,或者i=0;i<nums.length -1
            curDiff = nums[i] - nums[i-1];
            if((preDiff <= 0 && curDiff > 0) || (preDiff >= 0 && curDiff <0)){
                result++;
                preDiff = curDiff;
            }
        }
        return result;
    }
}

53. 最大子序和

文章讲解

思路

  • 当前“连续和”为负数的时候立刻放弃,从下一个元素重新计算“连续和”,因为负数加上下一个元素 “连续和”只会越来越小。
class Solution {
    public int maxSubArray(int[] nums) {
        if(nums.length == 1) return nums[0];
        int sum = Integer.MIN_VALUE;
        int count = 0;
        for(int i = 0; i < nums.length; i++){
            count += nums[i];
            sum = Math.max(sum, count);
            if(count <= 0) count = 0;
        }
        return sum;
    }
}
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容