贪心算法实战1

前言

上文带大家学习了贪心算法的理论基础，如果没看过的点这去回顾下 ，今天带大家进行贪心算法的实战篇1，本章注意来解答一些运用贪心算法的比较简单的问题，大家好好体会，怎么从构建局部最优到全局最优的。一文带大家弄懂。本文用于记录自己的学习过程，同时向大家进行分享相关的内容。本文内容参考于代码随想录同时包含了自己的许多学习思考过程，如果有错误的地方欢迎批评指正！

分发饼干

455. 分发饼干 - 力扣（LeetCode）

**相关技巧：**首先我们先抽象出问题，我们想要尽可能的让更多的孩子满足，那么什么情况下能够让更多的孩子满足呢？那么是不是就是我们让大尺寸的饼干尽可能的给能够满足的大胃口的孩子，这样是不是就是抽象出了我们的贪心策略。如果一个大尺寸的饼干给了小胃口的孩子是不是就会造成浪费。所以我们需要的就是将大尺寸饼干给大胃口孩子。其实逆向想一下，让大尺寸饼干给大胃口孩子也就是相当于让小尺寸饼干给小胃口孩子呢？其实都是贪心的策略，但是角度不同。这里我们就以大胃口饼干给大胃口孩子为例。

让大尺寸的给大胃口的，我们首先肯定要两者排序。然后我们遍历的是胃口哈，因为我们要满足更多的孩子胃口，但是我们不一定每个孩子都能满足到的，满足一个孩子就消耗一个饼干，再比较下一个饼干。所以原理就很清楚了，我们直接写代码就行了，如下所示。

class Solution:
    def findContentChildren(self, g, s):
        g.sort()  # 将孩子的贪心因子排序
        s.sort()  # 将饼干的尺寸排序
        index = len(s) - 1  # 饼干数组的下标，从最后一个饼干开始
        result = 0  # 满足孩子的数量
        for i in range(len(g)-1, -1, -1):  # 遍历胃口，从最后一个孩子开始
            if index >= 0 and s[index] >= g[i]:  # 遍历饼干
                result += 1
                index -= 1
        return result

K次取反后最大化的数组和

1005. K 次取反后最大化的数组和 - 力扣（LeetCode）

**相关技巧：**首先我们先抽象出问题，我们想要K次取反后最大化的数组和，那么什么情况下能够实现呢？首先数组中可能有正有负，那么我们希望最大，是不是就是希望能够首先将绝对值大的负的取反，然后在将绝对值小的负的取反，这里是不是很明显的贪心策略来了，我们每次通过将绝对值大的负的取反，最终得到的结果是不是就是最大的数组和呢？当遍历完整个数组后，我们就将绝对值最小的值再去取反即可。

思路和代码都是很容易想通理解的。首先就是将数组排序，这里注意我们按绝对值的大小排序，方便我们到时候可以选择绝对值大的负的。然后遍历即可，当k还有的时候遍历取反。遍历结束如果k值还有再判定其是奇数还是偶数，从而决定是否对绝对值最小的值取反。

class Solution:
    def largestSumAfterKNegations(self, A: List[int], K: int) -> int:
        A.sort(key=lambda x: abs(x), reverse=True)  # 第一步：按照绝对值降序排序数组A

        for i in range(len(A)):  # 第二步：执行K次取反操作
            if A[i] < 0 and K > 0:
                A[i] *= -1
                K -= 1

        if K % 2 == 1:  # 第三步：如果K还有剩余次数，将绝对值最小的元素取反
            A[-1] *= -1

        result = sum(A)  # 第四步：计算数组A的元素和
        return result

柠檬水找零

860. 柠檬水找零 - 力扣（LeetCode）

**相关技巧：**首先我们先抽象出问题，我们找零会遇到哪些情况

• 收到5元，直接收下
• 收到10元，需要找5元
• 收到20元，需要找一个10元和一个5元或者三个5元

其实前两个情况都是定了的，直接处理即可，但是收到20的时候，我们有两种不同的情况。那么优先选择哪个找零策略呢？这里就会用到贪心的思想了。当然肯定优先找一个10元和一个5元，尽可能自己手里多的留着5元的，因为5元不仅能用于20元的找零，也能用于10元的找零，使用范围更广。

那么就是代码实现了，看下列代码即可，还是很好理解的。

class Solution:
    def lemonadeChange(self, bills: List[int]) -> bool:
        five = 0
        ten = 0
        twenty = 0
        
        for bill in bills:
            # 情况一：收到5美元
            if bill == 5:
                five += 1
            
            # 情况二：收到10美元
            if bill == 10:
                if five <= 0:
                    return False
                ten += 1
                five -= 1
            
            # 情况三：收到20美元
            if bill == 20:
                # 先尝试使用10美元和5美元找零
                if five > 0 and ten > 0:
                    five -= 1
                    ten -= 1
                    #twenty += 1
                # 如果无法使用10美元找零，则尝试使用三张5美元找零
                elif five >= 3:
                    five -= 3
                    #twenty += 1
                else:
                    return False
        
        return True