代码随想录27天|贪心

455.分发饼干

代码随想录

第一想法

将孩子胃口值g[i] 按从小到达的顺序排列，饼干尺寸也按照从小到大的顺序去排列。

优先将大尺寸喂给大胃口孩子。如果满足不了胃口那么久试着分给下一个孩子。

要尽量满足更多的孩子，那么大尺寸的饼干就不能喂给小胃口的孩子

这里的局部最优就是大饼干喂给胃口大的，充分利用饼干尺寸喂饱一个，全局最优就是喂饱尽可能多的小孩

代码

虽然知道倒着分配的基本思路，但是还是非常出错。关键在于遍历孩子作为主体。

遍历孩子还是遍历饼干要在纸上模拟一遍。

class Solution {     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.摆动序列

代码随想录

代码随想录

preddiff =  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

首尾元素: 首尾元素不相同算两个摆动，因此直接用i = 0 || i = nums.leng()-1 判断是否为首尾元素直接加摆动是错误的。

        比如数组 [1 2] , 在左边延长 1 即[1 1 2],因此真正的首元素第二个1 可以通过计算prediff 和 curdiff 判断得出，而默认右侧就是有一个摆动序列，即count初始值为1

prediff和curdiff 的计算：当前元素判断完后逻辑上已经移动到下一个元素，那么curdiff就可以赋值给prediff，而prediff初始值为0，但是这样在单调有平坡时会出现问题/

单调坡中有平坡 [1 2 2 2 3 4]，摆动为2，prediff不是跟着curdiff实时摆动，而是在摆动出现时只记录坡度的初始方向，也就是prediff = curdiff 写在if逻辑里，那么当碰到 [1 2]段时prediff = 1 ,而后两个 2 时prediff都不会变化。

代码

class Solution {     public int wiggleMaxLength(int[] nums) {         if(nums.length==1)return 1;         int result = 1; //默认最右侧有摆动，初始值为1         int prediff = 0;//默认延长首元素         int curdiff = 0;         for(int i = 0;i<nums.length-1;i++){             curdiff = nums[i+1]-nums[i];             if((prediff<=0&&curdiff>0)||(prediff>=0&&curdiff<0)){                 result++;                 prediff = curdiff;             }         }         return result;     } }

 53.最大子序和

第一想法

从起始开始加，如果比原来更大则接收，并同时记录数组长度，如果一旦变小那么就归零重新计算。想法是找到一个连续子序和大的，那么基于它应该能找到更大的。

但是例如数组 [5,4,-1,7,8] ，需要短暂接收 -1 ，最终最大子序和是所有数值相加 即23.

或者双层for循环，枚举所有的子序和，时间复杂度为 n^2

代码随想录

遍历数组时会累加连续和 ，如果连续和是负数 ，加后面的数只会让后面的数更小，对求值不利。例如 -2 1 ,-2 +1 < 1，那么不如使用1作为新起点。

局部最优：当连续和为负数的时候，立即抛弃它，选择下一个数作为新的起点

全局最优：子序和最大 

贪在哪里

这题贪心的核心就是，以当前的子序和为视角，每次选择时都可能让子序和更大： 当子序和负数时，替换新子序和，因为无论如何加下一个数都不如直接选下一个数成为新子序和大 当子序和正数时，直接加新数字，因为无论如何替换下一个数都不如当前子序和加数字大 很经典地体现了 “贪” 的特点，目标就是要让子序和尽可能大！

——B友 杏吧阿伟 

从编程到哲学

我我我悟到了一个道理！当我们遇到困难的时候（负数）不要逃避（跳过负数），我们试着去接受它（加入连续和），然后尝试更好地未来；如果遇到了太多的伤心事（连续和变成负数了），那都是些没有办法改变的事情，我们不如卸下包袱（连续和归0），然后奔赴一个新的起点（新的连续和起点）

——B友 猫猫灵机一动时

代码

class Solution {     public int maxSubArray(int[] nums) {         int result = Integer.MIN_VALUE;//求解最大子序和，先将比较结果初始为最小值         int sum = 0;         for(int i = 0;i<nums.length;i++){             sum +=  nums[i];             if(sum>result)result = sum;             if(sum<0) sum = 0;//如果当前子序和为负数，立即归零，选择下一个数作为新起点         }         return result;     } }