代码随想录27期|Pthon|Day31|贪心算法|理论基础|455.分发饼干|376. 摆动序列|53. 最大子序和

理论基础

首先，贪心算法基本靠“做题感觉”，所以没有规范的总结和做题技巧，只能说见到过之后还能想起来。

一般情况可以看成是对于一个大的问题的子问题的局部最优的求解，然后可以推导出全局的最优。

这个过程没有证明，只能说在“认为没有反例”的情况下“试一试”。

?455.?分发饼干

从大饼干开始：先喂饱大的，然后再喂饱小的

都从最大的值开始遍历，for控制胃口，idx指向饼干，当且仅当找到小于饼干的胃口的时候idx往前移动，否则持续找更小的胃口。

从小饼干开始：先找到能满足第一个人的饼干

都从小的开始遍历，for控制饼干，idx指向胃口，找到一个满足的胃口之后idx再向后移动。

class Solution(object):
    def findContentChildren(self, g, s):
        """
        :type g: List[int]
        :type s: List[int]
        :rtype: int
        """
        if len(g) == 0 or len(s) == 0:
            return 0
        g.sort()
        s.sort()

        # 小饼干开始
        idx = 0
        for i in range(len(s)):
            if idx < len(g) and s[i] >= g[idx]:
                idx += 1
        return idx

        # 大饼干开始
        num_fed = 0
        idx = len(s)  - 1
        # 固定饼干idx找合适的胃口
        for i in range(len(g)-1, -1, -1):
            if g[i] <= s[idx] and idx >= 0:
                num_fed += 1
                idx -= 1
        return num_fed

376.?摆动序列

本题需要考虑的是多种情况的平坡（也就是差值不发生变化的时候）。

基本想法是比较前后两个差值和0的大小：

（1）第一种需要考虑差值为0，也就是遇到平坡的时候；
（2）另外一种是在上升的时候遇到平坡。

所以选择双指针的方法，使用一个cur和一个pre分别指向当前和之前的差值，和0进行比较。当且仅当差值出现波动（也就是更新了res）的时候更新pre的值。

class Solution(object):
    def wiggleMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = 1
        cur_diff = 0
        pre_diff = 0
        if len(nums) <= 1:
            return len(nums)
        for i in range(len(nums) - 1):
            cur_diff = nums[i + 1] - nums[i]
            if (cur_diff > 0 and pre_diff <= 0) or (cur_diff < 0 and pre_diff >= 0):
                res += 1
                pre_diff = cur_diff  # 当且仅当res更新的时候才让pre向前走
        return res

53.?最大子数组和

思路：遍历 nums，从头开始用 count 累积，如果 count 一旦加上 nums[i]变为负数，那么就应该从 nums[i+1]开始从 0 累积 count 了，因为已经变为负数的 count，只会拖累总和。使用res记录当前最大值即可。

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        res = - float('inf')
        count = 0
        for i in range(len(nums)):
            count += nums[i]
            if count > res:
                res = count
            if count <= 0:
                count = 0
        return res

有一个误区：是遇到负数就从头开始还是和为负数就从头开始？

比如，4，-1，3这个序列，4 - 1 = 3是正数，对于后面的3起到增益的作用，所以应该被保留，但是由于最大值一直都存在res里面，所以即使3比4要小，对于结果并不会产生影响。

第31天完结！！🎉