专栏首页用户6811391的专栏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 值升序排列。

同时不服不行,这一调整,不忍心看自己之前写的那坨了。

结论

可能解完题目会有疑问:这解法和贪心算法有什么关联吗?

我们再回头瞧瞧贪心算法的基本思路:

  1. 建立数学模型来描述问题
  2. 把求解的问题分成若干个子问题
  3. 对每一子问题求解,得到子问题的局部最优解
  4. 把子问题的局部最优解合并成原来问题的一个解

这就又能对应上了。再遇到新问题时,可能很难直接应用这贪心算法的模型,但这贪心算法更多时候像一种思路的方向,要分解、局部最优再组合,最终求出结果。可能这就是为何那么多题目标着贪心算法的标签,可结果却体现不出有多贪心吧!

本文分享自微信公众号 - TTTEED(TEDxPY),作者:TED

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-05-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • Python 刷题笔记:贪心算法专题一

    LeetCode 每月都会搞每日一题活动,昨天的题目是贪心算法类型,折腾好久才做出来,索性今天就围绕贪心算法多看几道。

    TTTEED
  • Python 刷题笔记:贪心算法专题二

    最近我们开始练习贪心算法的题目,昨天因为卡在其中一道简单级别的题目上没能更新,今天补更,正好也借着卡的点分享下经验。关于贪心算法的介绍,如果想回顾,可以点上篇来...

    TTTEED
  • 【LeetCode】贪心算法--买卖股票的最佳时机 II(122)

    为什么要在LeetCode刷题?大家都知道不管是校招还是社招算法题是必考题,而这一部分恰巧是大多数人的短板,所以刷题首先是为了提高自身的编程能力,能够在算法面试...

    PM小王
  • Python 刷题笔记:位运算专题一

    学 Python 初接触 &、| 等运算符时,只大概了解它们被称为位运算符,并不同于逻辑运算符 and、or,今天就通过基础知识点和几道题目来熟悉下。

    TTTEED
  • Python 刷题笔记:位运算专题二

    正数三码相同,负数的反码才会除了首位符号位不变、其余位取反。位运算都是基于数字的补码来进行运算的。

    TTTEED
  • 算法笔记(0002) - 【贪心算法】活动安排问题

    在对问题求解时,总是做出在当前看来是最好的选择。也就是说,不从整体最优上加以考虑,他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优...

    YINUXY
  • Python 刷题笔记:二叉树专题一

    今天来看二叉树专题,首先我们先整理下基础知识点;基于在 LeetCode 推荐题解中发现的一个适用于二叉树遍历的套路解法,我们今天也会连刷三道关于前序、中序和后...

    TTTEED
  • Python 刷题笔记:二叉树专题二

    给你一个二叉树,请你返回其按 层序遍历 得到的节点值。(即逐层地,从左到右访问所有节点)。

    TTTEED
  • 聊聊刷题,让你事半功倍的编程笔记!

    所以大家在准备校招、社招,或者闲暇的时候,都可以刷刷 Leetcode,保持良好的手感。

    Jack_Cui
  • Python 刷题笔记:深度优先搜索专题

    今天来接触下专业术语——深度优先搜索算法(英语:Depth-First-Search,DFS)

    TTTEED
  • Python 刷题笔记:广度优先搜索专题

    昨天看过了简单题汇聚的深度优先搜索专题,今天来体验下简单级别的广度优先搜索专题。老样子,先熟悉下术语概念:

    TTTEED
  • 他喵的,BAT 大佬的这份刷题笔记太强了!

    大家应该都知道,现在的互联网公司面试,只要是研发岗位,基本上都跑不了算法题的折磨,所以大家在准备校招和社招的时候,或者业余时间,还是要多刷刷 LeetCode,...

    沉默王二
  • Python 刷题笔记:数组专项练习一

    昨天是刷题的第 25 天,基本保持了每天一两道,同步分享了其中前 35 题的记录。通过二十多天的摸索,慢慢熟悉 LeetCode 平台,为了提高刷题学习效率,我...

    TTTEED
  • 10分钟用 Python 编写一个贪吃蛇小游戏

    贪吃蛇,大家应该都玩过。当初第一次接触贪吃蛇的时候 ,还是能砸核桃的诺基亚上,当时玩的不亦乐乎。今天,我们用Python编程一个贪吃蛇游戏,下面我们先看看效果:

    逆锋起笔
  • 掌握这些核心算法,拿不到10+个offer你来找我,我锤飞你个不争气的

    不得不说现在算法岗的热门程度已经到了一个空前绝后的程度,所以这一岗位的就业形势也是非常严峻。

    北游
  • LeetCode刷题DAY 4:整数转罗马数字

    昨天刷的是罗马数字转整数(➡LeetCode刷题DAY 3:罗马数字转整数),今天反过来刷一下如何将整数转为罗马数字。第一反应还是建立哈希表,看了其他人的答案才...

    三猫
  • 算法工程师:双非渣硕是如何获得百度、京东双SP

    本人本科硕士皆双非,和牛客大佬们没得比,目前拿到的还可以的offer就是百度SP和京东SP,都是做的推荐算法,其他的不说了。 先说一下个人经历吧,学校比较水,实...

    牛客网
  • 贪心算法-活动选择问题(Python实现)

    TrueDei
  • 贪心算法-分数背包问题(Python实现)

    TrueDei

扫码关注云+社区

领取腾讯云代金券