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

发布时间:2024年01月04日

理论基础

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

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

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

?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天完结!!🎉

文章来源:https://blog.csdn.net/m0_57527624/article/details/135297976
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。