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