首页 > 其他分享 >Leetcode 406. 根据身高重建队列

Leetcode 406. 根据身高重建队列

时间:2024-09-21 14:28:07浏览次数:9  
标签:遍历 person 队列 people 406 length result Leetcode

1.题目基本信息

1.1.题目描述

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

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

题目意思: 原本有个排列正确的队列,现在被打乱成了people,现在需要我们根据打乱的people数列恢复之前正确的队列

1.2.题目地址

https://leetcode.cn/problems/queue-reconstruction-by-height/description/

2.解题方法

2.1.解题思路

本题只看官方题目,比较不太好理解。但是通过案例理解就很好理解。本质就是:原本有个排列正确的队列,现在被打乱成了people,现在需要我们根据打乱的people数列恢复之前正确的队列。 理解题意后,直接排序、遍历就很容易了

2.2.解题步骤

第一步,将people按身高升序、高于人数降序进行排列

第二步,初始化返回数组。并遍历people,每遍历一次的结果是在result中填上一个空位。对于遍历的第一个person,其余的length-1的人身高均大于或等于其,所以只需填到peroson[1]+1个空位处即可;对于后面person,第person[1]+1个空位也是合法位置(注意:对于当前遍历的person,前面的部分坑已经被前面遍历的填了)。最后,对于一种特殊情况的解释,就是相同身高但是person[1]不同的人,这种通过person[1]多的人先遍历,避免了对person[1]少的人的填坑的影响。

3.解题代码

Python代码

# 题目意思: 原本有个排列正确的队列,现在被乱成了people,现在需要我们根据打乱的people数列恢复之前正确的队列
class Solution:
    def reconstructQueue(self, people: List[List[int]]) -> List[List[int]]:
        length=len(people)
        # 第一步,将people按身高升序、高于人数降序进行排列
        people.sort(key=lambda person:[person[0],-person[1]])
        # 第二步,初始化返回数组。并遍历people,每遍历一次的结果是在result中填上一个空位。对于遍历的第一个person,其余的length-1的人身高均大于或等于其,所以只需填到peroson[1]+1个空位处即可;对于后面person,第person[1]+1个空位也是合法位置(注意:对于当前遍历的person,前面的部分坑已经被前面遍历的填了)。最后,对于一种特殊情况的解释,就是相同身高但是person[1]不同的人,这种通过person[1]多的人先遍历,避免了对person[1]少的人的填坑的影响。
        result=[[] for _ in range(length)]
        for person in people:
            blankPosCnt=person[1]+1
            for i in range(length):
                if not result[i]:
                    blankPosCnt-=1
                    if blankPosCnt==0:
                        result[i]=person
                        break
        return result                

C++代码

class Solution {
public:
    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        int length=people.size();
        sort(people.begin(),people.end(),[](const vector<int>& u,const vector<int>& v){
            return u[0]<v[0] || (u[0]==v[0] && u[1]>v[1]);
        });
        vector<vector<int>> result(length);
        for(auto person:people){
            int blankPosCnt=person[1]+1;
            for(int i=0;i<length;++i){
                if(result[i].empty()){
                    blankPosCnt--;
                    if(blankPosCnt==0){
                        result[i]=person;
                        break;
                    }
                }
            }
        }
        return result;
    }
};

4.执行结果

在这里插入图片描述

标签:遍历,person,队列,people,406,length,result,Leetcode
From: https://www.cnblogs.com/geek0070/p/18423970

相关文章

  • Leetcode 378. 有序矩阵中第 K 小的元素
    1.题目基本信息1.1.题目描述给你一个nxn矩阵matrix,其中每行和每列元素均按升序排序,找到矩阵中第k小的元素。请注意,它是排序后的第k小元素,而不是第k个不同的元素。你必须找到一个内存复杂度优于O(n^2)的解决方案。1.2.题目地址https://leetcode.cn/problem......
  • 中国电子学会202406青少年软件编程(Python)等级考试试卷(四级)真题
    青少年软件编程(Python)等级考试试卷(四级)2024-6一、单选题(共25题,共50分)1.执行以下程序后所输出的结果是?()A   20   B   41   C   21   D   912.以下说法错误的是?()A  python中可以在不同的自定义函数中声明相同名字的变量,使用时不会造成数据混乱B......
  • (LeetCode 热题 100) 199. 二叉树的右视图(递归、深度优先搜索dfs)
    199.二叉树的右视图思路:递归每次都优先右边子树,然后才是左子树。/***Definitionforabinarytreenode.*structTreeNode{*intval;*TreeNode*left;*TreeNode*right;*TreeNode():val(0),left(nullptr),right(nullptr){}......
  • [leetcode刷题]面试经典150题之3删除有序数组中的重复项(简单)
    题目 删除有序数组中的重复项给你一个 非严格递增排列 的数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。考虑 nums 的唯一元素的数量为 k ,你......
  • LeetCode 876
    题目:LeetCode876解法一:快慢指针注意:while循环条件,以链表(1,2,3,4,null)为例:当条件为fast!=null&&fast.next!=null时,若链表元素为偶数个,则返回中间的后一个节点(3)当条件为fast.next!=null&&fast.next.next!=null时,若链表元素为偶数个,则返回中间的前一个节......
  • [leetcode刷题]面试经典150题之5多数元素元素(简单)【附Boyer-Moore 投票算法(摩尔投票法
    很有意思的一个题,想了半天没想出来,最后发现两行代码就做出来了。写完后学习到还可以用Boyer-Moore投票算法,能减小空间复杂度,我把它写在后面,可以进一步学习。题目  多数元素给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊......
  • 【LeetCode Hot 100】11. 盛最多水的容器
    题目描述首先记录一下题目的解法。使用双指针记录容器的边界,从边界最大的容器开始,i位于最左侧,j位于最右侧。每次向中间移动高度较小的那个指针,并使用一个变量res记录容器最大的容积(即最终的答案)。//C++classSolution{public:intmaxArea(vector<int>&height){......
  • leetcode关于a++>等运算符优先级知识点辨析
    我偶然发现巧用++a>i可以大大缩减版面,方便检查。但对于相关优先级的知识点,我却有点模糊,所以对这个知识点进行辨析。1++a>i;a先加1,再与i比较2a++>i;a先与i比较再加13i<a++;a先比较再加14i<++a;a先加1再比较5--a>ia先减1再比较6a-->ia先比较再减17i<a--先......
  • Leetcode:交替合并字符串
    问题陈述1768.交替合并字符串给定两个字符串,word1和word2,任务是通过交替字符来合并它们。该过程从word1开始,一直持续到一个字符串用完为止。较长字符串中的任何剩余字符都将附加到合并字符串的末尾。我的思考过程考虑到问题的简单性,我立即认识到两指针方法是最合适的......
  • Leetcode #允许一个函数调用
    给定一个函数fn,返回一个与原始函数相同的新函数,除了它确保fn最多被调用一次。第一次调用返回的函数时,它应该返回与fn相同的结果。随后每次调用它时,它都应该返回未定义。示例1:输入:fn=(a,b,c)=>(a+b+c),调用=[[1,2,3],[2,3,6]]输出:**explanation:**登录后复制const......