简单难度贪心算法实战
在 leetcode 上贪心算法相关的编程题比较多，本节以及接下来的一节都会选择使用 leetcode 习题来帮助我们巩固和实战贪心算法。本节会选择一些标签为简单的题目，而在下一节中会选择标签为中级和困难的编程题。
1. 分发饼干
这是 leetcode 上算法部分第 455 题，为简单编程题。题目描述如下：
你是一位很棒的家长，想要给你的孩子们一些小饼干。但是，每个孩子最多只能给一块饼干。对每个孩子 iii ，都有一个胃口值 $g_i $，这是能让孩子们满足胃口的饼干的最小尺寸；并且每块饼干 jjj ，都有一个尺寸 sjs_jsj 。如果 $s_j >= g_i $，我们可以将这个饼干 jjj 分配给孩子 iii ，这个孩子会得到满足。你的目标是尽可能满足越多数量的孩子，并输出这个最大数值。
注意：你可以假设胃口值为正。一个小朋友最多只能拥有一块饼干。
示例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 <= costs.length <= 100；costs.length为偶数；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)O(nlogn)O(nlogn)，在问题规模 N 非常大时，主要的时间消耗在于快排方法 (sort) 那里。
4. 小结
本小节主要是进行贪心算法实战，在 leetcode 上选择 3 道简单题进行实战训练。这里的题目比较基础，贪心算法运用并不复杂。接下来我们将挑战中级和困难题，进一步应用贪心算法解决题目。