Python 刷题笔记：贪心算法专题三
Python 刷题笔记：贪心算法专题三
今天仍旧是贪心算法的题目，加上之前两篇的四道题，对贪心算法的应用也大致有些印象了，明天换个其它类型题目来继续刷。
时间关系只记录了一道，题目虽少，但这次过程记得较为详细，而且这题目确实还挺有意思。
题目
「第 406 题：根据身高重建队列」
难度：中等
假设有打乱顺序的一群人站成一个队列。每个人由一个整数对(h, k)表示，其中h是这个人的身高，k是排在这个人前面且身高大于或等于h的人数。编写一个算法来重建这个队列。
「注意：」总人数少于1100人。
「示例：」
输入:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]
输出:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]
#来源：力扣（LeetCode）
#链接：https://leetcode-cn.com/problems/queue-reconstruction-by-height题目分析
初接触这题，我是以找规律的方法来尝试分析题目的：整数对 (h,k) 中 k 是排在前面身高大于等于 h 的人数，也就是说 k 值大的是排在后面的，首位肯定是 k 为 0、身高最低的人。
结合着示例列表，我们的操作如下：
思路尝试
按照 [h,k] 中首先 k 要由小到大、其次 h 由小到大的原则将所有成员排序。接下来按这顺序向结果列表中添加成员：若添加时结果中的排布与成员的 k 值无冲突、则正常添加；若结果列表中的成员身高排布超出 k，将该成员插入到满足 k 条件的最末位置。
代码实现
代码中并没有按身高来排序，只按 k 来排的，那么身高的排序可以通过判断 k 是否满足条件来解决。
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 将列表按照 k 排序
tmp = sorted(people,key = lambda x: x[1])
# 结果列表
record = []
# 成员是否正常加在结尾
adding = True
# 对所有人遍历
for i in range(len(people)):
# 先加入第一个
if record==[]:
record.append(tmp[i])
# 对其后加入的，要判断身高排布与 k 值
else:
# 记录身高大于等于的数目
count = 0
# 对之前排好的人遍历
for j in range(i):
# 如果排布好的身高大于等于当前 h，count+1
if record[j][0]>=tmp[i][0]:
count+=1
# 如果此位置 count 数开始大于 k
if count>tmp[i][1]:
# 将新成员插入到当前位置
record.insert(j,tmp[i])
# 成员插入，后续无需再添加
adding = False
# 跳出遍历循环
break
# 如果正常添加
if adding:
# 将成员添加在结果列表中
record.append(tmp[i])
# 将标志重置
adding = True
# 返回结果列表
return record提交测试结果：
执行用时 : 680 ms, 在所有 Python3 提交中击败了 8.49% 的用户
内存消耗 : 14.1 MB, 在所有 Python3 提交中击败了 16.67% 的用户优化
我这版代码中，最初没有对身高排序，之后在对已添加成员遍历比较时通过比较身高与 k 值完成的身高排布。可以看到，for 循环中嵌套着对之前成员的遍历 for 循环，效率较低。且这题贪心算法标签，感觉以上解法和贪心算法也没啥关系，看下题解。
刚我们的解法中，主要是按照 k 的顺序来向结果中添加成员；题解中换了个「船新」思路，按照身高由高到低来添加成员，当身高不同时，先加入的成员 k 值是不会受到之后的小个子们影响，而新加入的小个子会发现其插入位置之前的所有人都不比他矮、换言之他的 k 值就是他的坐标！
看完题解，不得不说：卧槽无情！我们之前代码中繁杂的检查 k 是否满足的情况就这么被规避、而且是利用起来了！
优化代码
按此思路，重新修改代码如下：
class Solution:
def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
# 按首先身高降序、再k值升序的原则对列表排序
tmp = sorted(people,key = lambda x: (-x[0],x[1]))
record = []
# 遍历排序后列表
for item in tmp:
# 向结果中插入，索引为 k 值
record.insert(item[1],item)
return record提交测试表现：
执行用时 : 112 ms, 在所有 Python3 提交中击败了 78.47% 的用户
内存消耗 : 14.3 MB, 在所有 Python3 提交中击败了 16.67% 的用户之前代码中我只会借助 k = lambda x: x[1] 对 k 值这一个元素进行升序排列，这里学到了可以通过 k = lambda x: (-x[0],x[1]) 先对身高 h 降序、再对 k 值升序排列。
同时不服不行，这一调整，不忍心看自己之前写的那坨了。
结论
可能解完题目会有疑问：这解法和贪心算法有什么关联吗？
我们再回头瞧瞧贪心算法的基本思路：
- 建立数学模型来描述问题
- 把求解的问题分成若干个子问题
- 对每一子问题求解，得到子问题的局部最优解
- 把子问题的局部最优解合并成原来问题的一个解
这就又能对应上了。再遇到新问题时，可能很难直接应用这贪心算法的模型，但这贪心算法更多时候像一种思路的方向，要分解、局部最优再组合，最终求出结果。可能这就是为何那么多题目标着贪心算法的标签，可结果却体现不出有多贪心吧！