简单难度贪心算法实战

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

1. 分发饼干

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

你是一位很棒的家长,想要给你的孩子们一些小饼干。但是,每个孩子最多只能给一块饼干。对每个孩子 $i$i ,都有一个胃口值 $g_i ,ドル这是能让孩子们满足胃口的饼干的最小尺寸;并且每块饼干 $j$j ,都有一个尺寸 $s_j$sj​ 。如果 $s_j >= g_i ,ドル我们可以将这个饼干 $j$j 分配给孩子 $i$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)$O(nlogn),在问题规模 N 非常大时,主要的时间消耗在于快排方法 (sort) 那里。

4. 小结

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