代码随想录算法训练营第三十一天| 理论基础 、455.分发饼干 、376. 摆动序列、53. 最大子序和

491.理论基础

• 链接:代码随想录

• 解题思路：

  通过局部最优，推出整体最优

• 如何验证贪心算法的正确性

  最好用的策略就是举反例，如果想不到反例，那么就试一试贪心吧。

455.分发饼干

• 链接:代码随想录

大饼干配大胃口

• 解题思路：
  让饼干不浪费即可
  这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩。

//思路一：小饼干喂给小胃口
public int findContentChildren(int[] g, int[] s) {int sum = 0;//结果int j = 0;//排序Arrays.sort(g);Arrays.sort(s);for (int i = 0; i < g.length; i++) {//遍历饼干while(j < s.length && s[j] < g[i]){//这个饼干不符合孩子肚量，直到找到符合胃口的j++;}//满足条件if(j < s.length){sum++;j++;}//超出范围if(j == s.length){break;}}return sum;
}

// 思路2：优先考虑胃口，先喂饱大胃口
public int findContentChildren(int[] g, int[] s) {Arrays.sort(g);Arrays.sort(s);int count = 0;int start = s.length - 1;// 遍历胃口for (int index = g.length - 1; index >= 0; index--) {if(start >= 0 && g[index] <= s[start]) { //优先喂饱大胃口的start--;count++;}}return count;
}

376. 摆动序列⭐️

• 题目链接:代码随想录

摆动序列看一个元素的前后元素的差值的符号，小范围满足，则大范围也满足

• 解题思路：
  局部最优：删除单调坡度上的节点（不包括单调坡度两端的节点），那么这个坡度就可以有两个局部峰值。
  **整体最优：**整个序列有最多的局部峰值，从而达到最长摆动序列。
  **贪心：**实际操作上，其实连删除的操作都不用做，因为题目要求的是最长摆动子序列的长度，所以只需要统计数组的峰值数量就可以了
  本题设置一个preDiff和curDiff记录操作元素和前后元素的差值
  本题需要注意三点

• 注意三点

  • 上下坡中有平坡

    

  • 数组长度不够，在首尾两端

    

  • 单调坡有平坡 —> 多记录冗余值

    

*/public int wiggleMaxLength(int[] nums) {if(nums.length <= 1){return nums.length;}//记录当前差值int curDiff = 0;//记录先前差值int preDiff = 0;//初始值为0，解决数组长度为2的状况int res = 1;//记录结果，数组长度为2，默认为2//遍历for (int i = 1; i < nums.length; i++) {//i从1开始curDiff = nums[i] - nums[i - 1];//这里一定要从i开始，否则会越界if((preDiff >= 0 && curDiff < 0 ) || (preDiff <=0 && curDiff > 0)){//等于0是为了解决数组长度为2和中间平坡问题res++;//记录上下坡的值preDiff = curDiff;//这才更新数值，防止出现递增中间平坡问题}}return res;
}

53. 最大子序和⭐️

局部最优：

1. 只要当前子序列和值为正数，那么就会对下一个元素起到正的反馈，这个子序列会越积越大，也就继续可以用这个序列
2. 当前“连续和”为负数的时候立刻放弃**(将部分和置为0)**，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。

• 题目链接:代码随想录

• 解题思路：
  局部最优：只要当前子序列和值为正数，那么就会对下一个元素起到正的反馈，这个子序列会越积越大，也就继续可以用这个序列
  当前“连续和”为负数的时候立刻放弃，从下一个元素重新计算“连续和”，因为负数加上下一个元素 “连续和”只会越来越小。
  结果集：每次比较sum和count[i]谁更大，从而决定返回哪个

   * 贪心算法：一次遍历即出结果，大大降低时间复杂度
  

• 图像理解：

  

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;
}