• 老卫带你学---leetcode刷题(406. 根据身高重建队列)


    406. 根据身高重建队列

    问题:

    假设有打乱顺序的一群人站成一个队列,数组 people 表示队列中一些人的属性(不一定按顺序)。每个 people[i] = [hi, ki] 表示第 i 个人的身高为 hi ,前面 正好 有 ki 个身高大于或等于 hi 的人。

    请你重新构造并返回输入数组 people 所表示的队列。返回的队列应该格式化为数组 queue ,其中 queue[j] = [hj, kj] 是队列中第 j 个人的属性(queue[0] 是排在队列前面的人)。

    示例 1:
    
    输入:people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
    输出:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
    解释:
    编号为 0 的人身高为 5 ,没有身高更高或者相同的人排在他前面。
    编号为 1 的人身高为 7 ,没有身高更高或者相同的人排在他前面。
    编号为 2 的人身高为 5 ,有 2 个身高更高或者相同的人排在他前面,即编号为 01 的人。
    编号为 3 的人身高为 6 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
    编号为 4 的人身高为 4 ,有 4 个身高更高或者相同的人排在他前面,即编号为 0、1、2、3 的人。
    编号为 5 的人身高为 7 ,有 1 个身高更高或者相同的人排在他前面,即编号为 1 的人。
    因此 [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] 是重新构造后的队列。
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    示例 2:
    
    输入:people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
    输出:[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
    
    • 1
    • 2
    • 3
    • 4
    提示:
    
    1 <= people.length <= 2000
    0 <= hi <= 106
    0 <= ki < people.length
    
    • 1
    • 2
    • 3
    • 4
    • 5

    解决:

    排序+重建

    class Solution:
        def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
            res=[]
            people=sorted(people,key=lambda x:(-x[0],x[1])) ##排序,先根据第一个元素从大到小,再根据第二个元素从小到大
            print(people)
            for p in people:
                if len(res)<=p[1]:
                    res.append(p) ## 如果当前res长度小于等于元素的本应位置,那就append
                elif len(res)>p[1]:
                    res.insert(p[1],p) ## 如果当前res长度大于元素的本应位置,那就insert
            return res
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
  • 相关阅读:
    车牌识别定位 matlab基本方法和操作
    putty SSH免密码登录
    (70)Verilog读文件函数【readmemb】
    mapboxgl 渲染热力图并动态更新
    黑马全套Java教程(十一)
    吴恩达深度学习笔记——神经网络与深度学习(Neural Networks and Deep Learning)
    智慧城市建设的原则及规划目标
    可以用来制作硬模空心耳机壳的胶粘剂有哪些种类?
    windows USB设备驱动开发-双角色驱动
    从力扣[203]理解递归思想
  • 原文地址:https://blog.csdn.net/yixieling4397/article/details/133991181