代码随想录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; //默认最右侧有摆动，初始值为1int 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;}
}