代码训练营 Day 27|455.分发饼干 | 376. 摆动序列 | 53. 最大子序和
455.分发饼干
1. 用大饼干去喂胃口大的小孩
2. 这样就是局部最优解了
1. 局部最优解就是全局最优了
class Solution(object):def findContentChildren(self, g, s):""":type g: List[int]:type s: List[int]:rtype: int"""# sort cookie and children arrayg.sort()s.sort()# result is record how many children has been feed by cookieresult = 0# index is record where is largest cookieindex = len(s)-1# iterate g array, which is children first[children size,-1)for i in range(len(g)-1,-1,-1):# only when the cookie match with children if index >= 0 and s[index] >= g[i]:result += 1index -= 1return result376. 摆动序列
1. 摆动： 一正一负算是摆动
2. 数组的两端是默认个有一个摆动的
3. 删除单调坡度的元素，这样原序例保证峰值保留，每个峰值都是一个摆动
4. 局部最优解： 删除单调坡的元素
5. 全局最优解： 整个序列变成摆动最长的序列
6. 遇到摆动把该数值保存下来，遇到坡度单调元素不去保存
7. 判断摆动：
1. prediff: nums[i] - nums[i-1]; 前一个坡度
2. curdiff: nums[i+1] - nums[i]; 当前坡度
3. 如果prediff和curdiff一个正一个负，说明找到了峰值也就是摆动
8. 上下坡有平坡
1. 靠左边的删除，保留最右边的那个数字
2. 靠右边一样思路
9. 首尾元素
1. 在两个元素中，首尾元素不相同代表两个摆动
10. 单调有平坡
1. 摆动只有2，只有头跟尾有摆动
2. prediff只有在坡度有变化记录一下初始值，后面坡度没有变化prediff没有必要跟着curdiff去变化
3. 除非坡度方向改变了也就是遇到摆动了，从正到负了prediff采取改变
4. 好处是遇到平坡中prediff不回去改变的
prediff去记录坡度改变的方向
class Solution(object):def wiggleMaxLength(self, nums):""":type nums: List[int]:rtype: int"""# when nums size is 1, only has one wiggleif len(nums) <= 1:return len(nums)# use pre and cur record which way the number goesprediff = 0curdiff = 0# result record how many wiggleresult = 1for i in range(len(nums)-1):# calcualte curdiffcurdiff = nums[i+1] - nums[i]# determine if the number has wiggleif(prediff <= 0 and curdiff > 0) or (prediff >= 0 and curdiff < 0):result += 1prediff = curdiffreturn result
53. 最大子序和
1. 遍历数组的时候会累假连续和
1. 如过连续和为负数的话；加后面的输只会让当前的和变小
2. 选择下一个数作为起点，重新遍历
2. 局部最优： 当连续和为负数，抛弃当前的数字，把下一个数字作为新的起点，重新计算和
3. 用resutl数组记录连续和的最大值
class Solution(object):def maxSubArray(self, nums):""":type nums: List[int]:rtype: int"""# use result to find maximum subarrayresult = float('-inf')# count is sum of subarraycount = 0 for i in range(len(nums)):# update count valuecount += nums[i]# if our count > result, update countif count > result:result = count# if our count is negative, abandon current sum, use next number be our fresh startif count < 0:count = 0return result