简单难度贪心算法实战

在 leetcode 上贪心算法相关的编程题比较多，本节以及接下来的一节都会选择使用 leetcode 习题来帮助我们巩固和实战贪心算法。本节会选择一些标签为简单的题目，而在下一节中会选择标签为中级和困难的编程题。

1. 分发饼干

这是 leetcode 上算法部分第 455 题，为简单编程题。题目描述如下：

你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 $i$ ，都有一个胃口值 $g_i $，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 $j$ ，都有一个尺寸 $s_j$ 。如果 $s_j >= g_i $，我们可以将这个饼干 $j$ 分配给孩子 $i$ ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。

注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。

示例1：

输入: [1,2,3], [1,1]
输出: 1
解释: 你有三个孩子和两块小饼干，3个孩子的胃口值分别是：1,2,3。虽然你有两块小饼干，由于他们的尺寸都是1，你只能让胃口值是1的孩子满足。所以你应该输出1。

示例2：

输入: [1,2], [1,2,3]
输出: 2
解释: 你有两个孩子和三块小饼干，2个孩子的胃口值分别是1,2。你拥有的饼干数量和尺寸都足以让所有孩子满足。所以你应该输出2。

这里的解题思路也是非常清晰的：**同样也是贪心的思路，我们将孩子和饼干的胃口分别从小到大进行排序，从最小的饼干和第一个孩子开始。饼干指针一直向后执行，找到一个饼干满足孩子胃口，则孩子指针向后移动一位，同时满足的孩子数加1，如此执行直到孩子或者饼干的指针走完即可。**这样的一个尽可能最小饼干满足最小胃口的策略其实就是贪心思路。

按照上面的思路，题解第一步就是对孩子的胃口和饼干分别进行排序，从小达到：

g.sort()
s.sort()

接下来就是实现饼干满足小孩，我们分别给小孩的胃口数组、饼干数组设置初始化指针，然后初始化一个满足小孩数的变量：

id1, id2, count = 0, 0, 0

接下来就是遍历饼干数组和移动小孩胃口数组指针。如果饼干尺寸大于等于当前小孩胃口，则满足小孩，count 数加1，同时饼干和小孩胃口数组指针分别后移一位；如果饼干尺寸小于小孩胃口，则只有饼干指针后移一位。如此，直到最后饼干或者小孩的指针指到最后循环结束：

# 循环，当其中一个列表扫描完毕后结束
while id1 < len(g) and id2 < len(s):
    if g[id1] <= s[id2]:
    # 满足孩子，孩子指针+1，同时结果+1
        id1 += 1
        count += 1
    # 饼干指针+1，无论是满足和不满足孩子，都要往后走一位
    id2 += 1

最后我们完整给出实现上述题解的方法，如下：

def findContentChildren(g, s):
    # 使用贪心策略，先排序，最小胃口孩子对应最小能满足的饼干
    g.sort()
    s.sort()
    id1, id2, count = 0, 0, 0
    while id1 < len(g) and id2 < len(s):
        # 一次循环，当其中一个列表扫描完毕后结束
        if g[id1] <= s[id2]:
            # 满足孩子，孩子指针+1，同时结果+1
            id1 += 1
            count += 1
        # 饼干指针+1，无论是满足和不满足孩子，都要往后走一位
        id2 += 1
    return count

2. 柠檬水找零

这是 leetcode 上算法部分第 860 题，为简单编程题。题目描述如下：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意：一开始你手头没有任何零钱。如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

示例1：

输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

示例2：

输入：[5,5,10]
输出：true

示例3：

输入：[10,10]
输出：false

示例4：

输入：[5,5,10,10,20]
输出：false
解释：前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。由于不是每位顾客都得到了正确的找零，所以答案是 false。

看到这题，没啥好说的。首先依次扫描收入的钞，此时会有如下三种情况：

• 如果收到的是 5 元，直接放入 5 元列表中；
• 如果收到的是 10 元，看看 5 元列表是否还有剩余；
• 如果没有 5 元则无法找零，返回 False；
• 否则找零 5 元，减少一个 5 元列表元素，增加1个10元列表的元素；
• 对于收到的是 20 元，必须先找 10 元，然后剩下的再找 5 元；

首先定义存放5元和10元的数组，20元不会用于找零，所以不用记录：

remain_5 = []
remain_10 = []

根据上面思路，我们可以简单写以下收到5元和10元的逻辑：

for i in range(len(bills)):
    # 假设遍历第i个钞票
    if bills[i] == 5:
        # 5元钱，直接收入
        remain_5.append(1)
    elif bills[i] == 10:
        # 对于10元找零，只需要找零5元即可
        if not remain_5:
           # 没有5元，直接返回False
            return False
        # 减去一个5元
        remain_5.pop()
        # 加上一个10元
        remain_10.append(1)
    else:
        # 对于20元的处理
        pass

对于20元的处理，我们只需要定义一个找零数：res = 15。首先找零10元，如果有10元，则减去一个10元，同时剩余找零也要减去10：

remain = 15
# 如果有10元，先用一个10元
if len(remain_10) >= 1:
    remain -= 10
    remain_10.pop()

接下来找5元，每找零一个5元，则5元数需要减一，同时剩余找零数也要减去5,，直到 remain_5 数组为空或者 remain<=0 结束：

while len(remain_5) > 0 and remain > 0:
    remain -= 5
    remain_5.pop()

如果能找零，则 remain 最后应该为0，那么我们可以判断，如果剩余的 remain > 0，则表明最后无法找零；否则找零成功

if remain > 0:
    return False

在 20 元找零那里之所以能用贪心思想是因为找零的 15 元减去 10 元正好等于 5 元，如果我先找 5 元则会出现这样的情况：**剩余 2 个 5 元和 1 个 10 元，如果先找 5 元，则有 2 个 5 元，最后的 10 元无法完成找零。**最后整个处理柃檬水找零问题的 Python 方法如下：

def lemonadeChange(bills):
    remain_5 = []
    remain_10 = []
    for i in range(len(bills)):
        if bills[i] == 5:
            # 5元钱，直接收入
            remain_5.append(1)
        elif bills[i] == 10:
            # 10元找零5元
            if not remain_5:
                return False
            remain_5.pop()
            remain_10.append(1)
        else:
            # 对于20元钱找零15元，贪心策略，尽可能找零10元，10元不够在找5元
            remain = 15
            # 如果有10元，先用一个10元
            if len(remain_10) >= 1:
                remain -= 10
                remain_10.pop()
            # 这里存在2种情况，上面找了10元，就剩下5元要找；没有10元，就会一直找5元
            while len(remain_5) > 0 and remain > 0:
                remain -= 5
                remain_5.pop()
            # 如果最后还没找完，且5元数组为空，则无法完成找零，直接返回False
            if remain > 0:
                return False
    # 走到这一步，可以返回True
    return True    

3. 两地调度

这是 leetcode 上算法部分第 1029 题，为简单编程题。题目描述如下：

公司计划面试 2N 人。第 i 人飞往 A 市的费用为 costs[i][0]，飞往 B 市的费用为 costs[i][1]。返回将每个人都飞到某座城市的最低费用，要求每个城市都有 N 人抵达。

示例：

输入：[[10,20],[30,200],[400,50],[30,20]]
输出：110
解释：
第一个人去 A 市，费用为 10。
第二个人去 A 市，费用为 30。
第三个人去 B 市，费用为 50。
第四个人去 B 市，费用为 20。

最低总费用为 10 + 30 + 50 + 20 = 110，每个城市都有一半的人在面试。

Tips：

1. 1 <= costs.length <= 100；
2. costs.length 为偶数；
3. 1 <= costs[i][0], costs[i][1] <= 1000。

这道题需要认真思考下，对于贪心的算法而言我们要首先确定贪心的值。

我们的值并不是拿去城市的费用值来做贪心，这里要非常注意，因为每个人必须两个城市中选择去一个，如果去了 A 市就不能去 B 市；反之，去了 B 市就不能去 A 市。

可以很容易想到我们贪心的值应该是候选人去 A 市和 B 市花费的差值，接着将列表元素按照相应的差值从小到大进行排列，前 N 个人去 A 市，后 N 个人去 B 市，这便是这道题最精妙的解题思路，是不是很有意思？有了上面的贪心过程，那么 Python 实现便呼之欲出：

def twoCitySchedCost(self, costs):
    min_costs = 0
    N = len(costs) // 2
    # 调用python的排序函数，排序值为相应差值
    costs.sort(key=lambda x:x[0]-x[1])
    # 排序后的前半部分人去A市
    min_costs += sum([costs[i][0] for i in range(N)])
    # 后半部分人去B市
    min_costs += sum(costs[i][1] for i in range(N, 2 * N))
    return min_costs

可以看到，这里算法的时间复杂度为 $O(nlogn)$，在问题规模 N 非常大时，主要的时间消耗在于快排方法 (sort) 那里。

4. 小结

本小节主要是进行贪心算法实战，在 leetcode 上选择 3 道简单题进行实战训练。这里的题目比较基础，贪心算法运用并不复杂。接下来我们将挑战中级和困难题，进一步应用贪心算法解决题目。