Python 刷题笔记：贪心算法专题二
最近我们开始练习贪心算法的题目，昨天因为卡在其中一道简单级别的题目上没能更新，今天补更，正好也借着卡的点分享下经验。关于贪心算法的介绍，如果想回顾，可以点上篇来看。
当时的介绍基本引用自诸多官方描述，这两天的相关题目做下来，对贪心算法的感觉却是这更归为一种设计解法的思想，有点拆分步骤或子问题，然后逐个击破的意思。而且这贪心算法的应用，跨度比较大的题目应用起来关联性又不大，还挺麻烦的。
刷这几道题目时，有些刻意练习贪心解法，比较耗时，之后还是要提高效率，先解题，再学习掌握更优算法。来看今儿的题目吧～
题目一
「第 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，每个城市都有一半的人在面试。
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/two-city-scheduling题目分析
昨天我就是卡在了这道题，先说下我最初分析：既然要用贪心算法，这里有 2N 个人即 N 对人，那么我们一对对来分析，只要保证每新增一对，花费是最低的，那么最终也将是最低费用。
我们用一张图来展示题目中示例分析过程：
思路尝试
按照刚的设想，每增加一对人，我们先对他们俩的费用分析，其中一个分配去 A、另一个去 B。
但这时，要去 A 的人还要和已经被安排去 B 的所有人来进行比较，看有没有更便宜的组合来对调；同理，要去 B 的这位也要在被安排去 A 的人里进行比较一番，若有更便宜组合则对调，没有的话就按此分配。
这样，每一对人，我们都拿到了最低的分配费用，那么累计 N 对后的 2N 个人，其价格也是最低的。
代码实现
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
# 分配去 A 的名单
list_A=[]
# 分配去 B 的名单
list_B=[]
# 总人数
length = len(costs)
# 人数分成 n 对
n = length//2
# 是否要与分配好的人对调
swap = False
# 定义一个判断目前去AB的组合是否价格最优
def check_AB(p,q):
# 若 p 去 A、q 去 B 的价格 低于 q 去 A、p 去 B 的价格
if costs[p][0]+costs[q][1]<=costs[q][0]+costs[p][1]:
# 返回 (p,q)
return (p,q)
# 否则返回 (q,p)
else:
return (q,p)
# for 循环遍历 n 对人
for i in range(n):
# n 对人中第一人索引值
first = i*2
# 第二人索引值
second = i*2+1
# 获取二人去 A、B 的最优分配
a,b = check_AB(first,second)
# 复制下去 B 的列表
copy_B = list_B[:]
# 遍历去 B 的人
for x in copy_B:
# 如果去 B 的人现在和要去 A 的 a 有更优的价格组合
if check_AB(a,x)!=(a,x):
# 将这个原本去 B 的 x 和 a 对调
list_B.remove(x)
list_B.append(a)
a = x
# 同理，遍历去 A 的人来和要去 B 的 b 来比较分析
copy_A = list_A[:]
for y in copy_A:
if check_AB(y,b)!=(y,b):
list_A.remove(y)
list_A.append(b)
b = y
# 将对调后的或没有对调过的 a b 分配
list_A.append(a)
list_B.append(b)
# 计算去 A 地人总费用
cost_a = sum([costs[i][0] for i in list_A])
# 计算去 B 地人总费用
cost_b = sum([costs[j][1] for j in list_B])
# 返回二者之和
return cost_a+cost_b提交代码测试：
执行用时 : 64 ms, 在所有 Python3 提交中击败了 26.97% 的用户
内存消耗 : 13.8 MB, 在所有 Python3 提交中击败了 25.00% 的用户过程比较繁琐，但是本着贪心算法来设计的，我昨天卡在了对去 A、B 两地的人遍历上，当时我没有复制列表，直接在列表上来遍历的，导致如果有人对调，那么 list_A 和 list_B 就变化影响遍历循环，导致数据差异。
同时，自定义判断去 A、B 的函数，也略显复杂，但若变下形，便能打开新思路：
costs[p][0]+costs[q][1]<=costs[q][0]+costs[p][1]
# 等效于
# p 去 A 的费用减去 B 的费用
costs[p][0]-costs[p][1]<=costs[q][0]-costs[q][1]谁去 A 的费用减去 B 的费用更低，谁就更应该被安排去 A。掌握到这点，便能很容易理解题解里其它更直接了当的解法了。
观摩题解
题解虽然简单，但是比较坑，虽然打着贪心算法的标签，但没几个真用这算法来设计的答案。一般都是假设所有人都去 A，那么得到总费用，这时候要选 N 个人去 B，无论谁去 B 都可能会产生差价，计算每个人 B-A 的价格，价格有正负大小，当然是越小越好，挑出 N 个 B-A 最小的值，与之前总费用求和，即最终答案。
根据这思路，我的代码如下：
class Solution:
def twoCitySchedCost(self, costs: List[List[int]]) -> int:
n = len(costs)//2
# 全部人去 A 市，总费用
all_a_cost = sum([item[0] for item in costs])
# 每个人去 B 的话，差价
b_a_diff = [item[1]-item[0] for item in costs]
b_a_diff.sort()
return all_a_cost+sum(b_a_diff[:n])这里提到的挑出 B-A 值最小的人去 B，和我们之前代码里分析的 A-B 的值最小的人去 A 是一个道理，掌握了这点就能抓住计算的关键。
这样纯列表计算，就规避了繁杂的比较过程，提交测试表现：
执行用时 : 48 ms, 在所有 Python3 提交中击败了 72.29% 的用户
内存消耗 : 13.7 MB, 在所有 Python3 提交中击败了 25.00% 的用户题目二
「第 135 题：分发糖果」
难度：困难
老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
- 每个孩子至少分配到 1 个糖果。
- 相邻的孩子中，评分高的孩子必须获得更多的糖果。
那么这样下来，老师至少需要准备多少颗糖果呢？
示例 1:
输入: [1,0,2]
输出: 5
解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。
示例 2:
输入: [1,2,2]
输出: 4
解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。
第三个孩子只得到 1 颗糖果，这已满足上述两个条件。
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/candy题目分析
题做多了，会先被难度级别唬住，看到困难题就会有即使做不出、看题解也理所当然的想法。这里摘录这道题的原因是，它这个解法的思路不再是针对 N 个孩子每人如何如何逐步分，而是按照规则来整体正反两个方向来做处理。
这里我是参考的题解中一份阐述非常明确解法：按照规则每人先分一个糖，从左向右遍历孩子们的分数，若右侧孩子分高于左侧，那么高分的孩子是低分孩子糖数 + 1，这里只处理右侧高于左侧的情况。这么过一遍后，正向来看，规则满足了。
如图，假设孩子们分数 [5,7,8,3,4,2,1]，正向分糖：
图片、解法链接：
https://leetcode-cn.com/problems/candy/solution/candy-cong-zuo-zhi-you-cong-you-zhi-zuo-qu-zui-da-/还有可能，左侧分数高于右侧，这个如果从左向右正向看的话，不好为它们设置分数，因为右侧还有更多孩子没有分配，所以这种情况就从右往左看，就转化成了刚刚问题、只不过调换了方向而已。
但要注意的是，若左侧分数高于右边、且糖数已经多于右边时，不要减少左侧糖数，因为它的数目是由从左到右正向累计上去的。
代码实现
class Solution:
def candy(self, ratings: List[int]) -> int:
# 获取人数长度
length = len(ratings)
if length<2:
return 1
# 每人分一个糖
candy_list = [1]*length
# 正向遍历
for i in range(1,length):
# 若右侧比左侧分数高
if ratings[i]>ratings[i-1]:
# 右侧分糖比左侧多 1 个
candy_list[i] = candy_list[i-1]+1
# 逆向遍历，还是用的原索引，但倒序
for j in range(length-2,-1,-1):
# 如果左侧比右侧分数高
if ratings[j]>ratings[j+1]:
# 如果左侧糖不比右侧高的话
if candy_list[j]<=candy_list[j+1]:
# 左侧糖提高到右侧 +1
candy_list[j] = candy_list[j+1]+1
# 返回糖数列表求和
return sum(candy_list)提交测试表现：
执行用时 : 80 ms, 在所有 Python3 提交中击败了 85.68% 的用户
内存消耗 : 15.7 MB, 在所有 Python3 提交中击败了 25.00% 的用户看，困难级别的题目，代码却很简单，关键就是算法思路的设计。
结论
当然，还有几道题目，时间关系来不及记录了，选这两个题目的原因：贪心算法并不局限于分步骤优化解决问题，像第二题中正反两个方向能涵盖所有问题要求、那么再逐个击破就可以了；第一题贪心算法设计起来很麻烦，但却能挖掘出简单算法里核心点，有了这种铺垫，设计简单算法会更容易些。
很多标着贪心算法标签的题目题解却是其它众多精巧解法，可能第一时间觉得挺坑，但分析下来也是有些关联的。可能我们初次接触掌握不来，但多练练也就把它们拿下了。
腾讯云开发者
