LeetCode406:根据身高重建队列

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

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

在这里插入图片描述
解题思想
先根据身高进行降序排序,然后在根据k的值进行插入。
排序完的people: [[7,0], [7,1], [6,1], [5,0], [5,2],[4,4]]

插入的过程:
插入[7,0]:[[7,0]]
插入[7,1]:[[7,0],[7,1]]
插入[6,1]:[[7,0],[6,1],[7,1]]
插入[5,0]:[[5,0],[7,0],[6,1],[7,1]]
插入[5,2]:[[5,0],[7,0],[5,2],[6,1],[7,1]]
插入[4,4]:[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

代码

class Solution {
public:
    static bool cmp(vector<int> &a, vector<int> &b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        vector<vector<int>> que; 
        
        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            que.insert(que.begin() + position, people[i]);
        }
        return que;
    }
};

使用链表插入效率更高

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        if (a[0] == b[0]) return a[1] < b[1];
        return a[0] > b[0];
    }

    vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
        sort(people.begin(), people.end(), cmp);
        list<vector<int>> que; // list底层是链表实现,插入效率比vector高的多

        for (int i = 0; i < people.size(); i++) {
            int position = people[i][1];
            list<vector<int>>::iterator it = que.begin();
            while (position--) {
                it++;
            }
            que.insert(it, people[i]);
        }
        return vector<vector<int>>(que.begin(),que.end());
    }
};

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/591851.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

初学python记录:力扣1235. 规划兼职工作

题目&#xff1a; 你打算利用空闲时间来做兼职工作赚些零花钱。 这里有 n 份兼职工作&#xff0c;每份工作预计从 startTime[i] 开始到 endTime[i] 结束&#xff0c;报酬为 profit[i]。 给你一份兼职工作表&#xff0c;包含开始时间 startTime&#xff0c;结束时间 endTime …

[嵌入式AI从0开始到入土]17_Ascend C算子开发

[嵌入式AI从0开始到入土]嵌入式AI系列教程 注&#xff1a;等我摸完鱼再把链接补上 可以关注我的B站号工具人呵呵的个人空间&#xff0c;后期会考虑出视频教程&#xff0c;务必催更&#xff0c;以防我变身鸽王。 第1期 昇腾Altas 200 DK上手 第2期 下载昇腾案例并运行 第3期 官…

JDK14特性

JDK14 1 概述2 语法层面的变化1_instanceof的模式匹配(预览)2_switch表达式(标准)3_文本块改进(第二次预览)4_Records 记录类型(预览 JEP359) 3 API层面的变化4 关于GC1_G1的NUMA内存分配优化2_弃用SerialCMS,ParNewSerial Old3_删除CMS4_ZGC on macOS and Windows 4 其他变化1…

PPT基础

5种ppt仅可读形式 Ⅰ 开始选项卡 1.【幻灯片】组中&#xff1a;新建幻灯片&#xff0c;从大纲中导入幻灯片&#xff1b;修改幻灯片的版式&#xff1b;节&#xff08;新增节&#xff0c;重命名节&#xff09;。 2.【字体】组中&#xff1a;设置字体&#xff0c;字体大小&…

ctfshow web入门 sql注入 web224--web233

web224 扫描后台&#xff0c;发现robots.txt&#xff0c;访问发现/pwdreset.php &#xff0c;再访问可以重置密码 &#xff0c;登录之后发现上传文件 检查发现没有限制诶 上传txt,png,zip发现文件错误了 后面知道群里有个文件能上传 <? _$GET[1]_?>就是0x3c3f3d60245…

海外仓系统与跨境电商平台集成:有什么意义,为什么重要

跨境电商的发展趋势并没有丝毫放缓的迹象&#xff0c;这使得对高效率、综合性的海外仓的需求变得比以往任何时间都要多。 预测表明&#xff0c;未来一年跨境电商的市场份额将继续扩大。这一切都要求海外仓企业尽快提升仓储管理效率&#xff0c;在这个过程中&#xff0c;海外仓系…

小苹果

题目描述 小的桌子上放着几个苹果从左到右排成一列&#xff0c;编号为从1 到 。小苞是小的好朋友&#xff0c;每天她都会从中拿走一些苹果。每天在拿的时候&#xff0c;小苞都是从左侧第1个苹果开始、每隔2个苹果拿走1个苹果。随后小苞会将剩下的苹果按原先的顺序重新排成一列…

扩展学习|本体研究进展

文献来源&#xff1a; 王向前,张宝隆,李慧宗.本体研究综述[J].情报杂志,2016,35(06):163-170. 一、本体的定义 本体概念被引入人工智能、知识工程等领域后被赋予了新的含义。然而不同的专家学者对本体的理解不同,所给出的定义也有所差异。 人工智能领域的学者Neches(1991)等人对…

StampedLock(戳记锁)源码解读与使用

&#x1f3f7;️个人主页&#xff1a;牵着猫散步的鼠鼠 &#x1f3f7;️系列专栏&#xff1a;Java源码解读-专栏 &#x1f3f7;️个人学习笔记&#xff0c;若有缺误&#xff0c;欢迎评论区指正 1. 前言 我们在上一篇写ReentrantReadWriteLock读写锁的末尾留了一个小坑&#…

这书不错,古琴乐理实用教程(尹溧新编),有课学得通透。

通篇阅读后&#xff0c;发现这本书以古琴初习者、未系统接触过现代乐理的读者为对象&#xff0c;将复杂的古琴音乐理论简单化、通俗化。书中采用参照比较的方法、通俗易懂的语言、言简意赅的文字&#xff0c;并结合具体音乐作品将古琴研习中最主要的、最核心的理论知识进行简明…

进程间通信(3)信号量初识

我最近开了几个专栏&#xff0c;诚信互三&#xff01; > |||《算法专栏》&#xff1a;&#xff1a;刷题教程来自网站《代码随想录》。||| > |||《C专栏》&#xff1a;&#xff1a;记录我学习C的经历&#xff0c;看完你一定会有收获。||| > |||《Linux专栏》&#xff1…

72.网络游戏逆向分析与漏洞攻防-角色与怪物信息的更新-完善利用角色与怪物创建的功能

免责声明&#xff1a;内容仅供学习参考&#xff0c;请合法利用知识&#xff0c;禁止进行违法犯罪活动&#xff01; 如果看不懂、不知道现在做的什么&#xff0c;那就跟着做完看效果 现在的代码都是依据数据包来写的&#xff0c;如果看不懂代码&#xff0c;就说明没看懂数据包…

开源模型应用落地-LangChain高阶-Tools工具-集成agents(四)

一、前言 LangChain 的 tools 是一系列关键组件&#xff0c;它们提供了与外部世界进行交互的能力。通过适当的使用这些组件&#xff0c;可以简单实现如执行网络搜索以获取最新信息、调用特定的 API 来获取数据或执行特定的操作、与数据库进行交互以获取存储的信息等需求。 本章…

MATLAB - 自定义惯性矩阵

系列文章目录 前言 一、关键惯性约定 Simscape 多体软件在惯性定义中采用了一系列约定。请注意这些约定&#xff0c;因为如果手动进行惯性计算&#xff0c;这些约定可能会影响计算结果。如果您的惯性数据来自 CAD 应用程序或其他第三方软件&#xff0c;这些约定还可能影响到您需…

TranslatePress Pro插件下载:一键国际化,让您的网站走向世界

在全球化的今天&#xff0c;一个多语言的网站是连接不同文化和市场的桥梁。TranslatePress Pro插件&#xff0c;作为一款专为WordPress用户设计的多语言解决方案&#xff0c;以其简便的操作和强大的功能&#xff0c;帮助您的网站跨越语言障碍&#xff0c;吸引全球用户。 [Tran…

vector 的模拟实现

目录 1. vector 的核心框架 2. size 和 capacity 以及 empty 3. reserve 和 push_back 4. insert 5. erase 6. copy constructor 6.1. 第一个版本 6.2. 第二个版本 6.3. 第三个版本 7. operator 7.1. 第一个版本 7.2. 第二个版本 7.3. 第三个版本 8. constructor…

用自然语言即可完全控制用户界面;无需调整的文本至图片生成的ID定制方法;OpenAI构建应用指南

✨ 1: PyWinAssistant 用自然语言即可完全控制用户界面 PyWinAssistant是一个突破性的项目&#xff0c;它基于2023年12月31日发布的技术&#xff0c;代表了首个大型行为模型、开源Windows 10/11人工智能框架。这个框架的主要亮点在于它能够通过利用思维可视化&#xff08;Vis…

Java复习第十九天学习笔记(Cookie、Session登录),附有道云笔记链接

【有道云笔记】十九 4.7 Cookie、Session登录 https://note.youdao.com/s/VwpxfEim 一、会话技术简介 生活中会话 我&#xff1a; 小张&#xff0c;你会跳小苹果码&#xff1f; 小张&#xff1a; 会&#xff0c;怎么了&#xff1f; 我&#xff1a; 公司年会上要表演节目&a…

HTML_CSS学习:常用文本属性

一、文本颜色 相关代码&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>文本颜色</title><style>div{font-size: 90px;}.atguigu1{color: #238c20;}.atguigu2{color: rgb(2…

AI文章框架分析

大家在文章写作的时候结构难免会有点凌乱&#xff0c;但是自己可能无法发现问题所在&#xff0c;那么有没有一款工具可以帮你自动分析你写的文章框架存在的问题&#xff0c;然后并给你详细的分析报告呢&#xff1f;今天给大家介绍一下文件框架分析助手&#xff01; 使用说明 打…