LeetCode 1094. 拼车:优先队列
【LetMeFly】1094.拼车:优先队列
力扣题目链接:https://leetcode.cn/problems/car-pooling/
车上最初有 capacity 个空座位。车 只能 向一个方向行驶(也就是说,不允许掉头或改变方向)
给定整数 capacity 和一个数组 trips , trip[i] = [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客,接他们和放他们的位置分别是 fromi 和 toi 。这些位置是从汽车的初始位置向东的公里数。
当且仅当你可以在所有给定的行程中接送所有乘客时,返回 true,否则请返回 false。
示例 1:
输入:trips = [[2,1,5],[3,3,7]], capacity = 4 输出:false
示例 2:
输入:trips = [[2,1,5],[3,3,7]], capacity = 5 输出:true
提示:
1 <= trips.length <= 1000trips[i].length == 31 <= numPassengersi <= 1000 <= fromi < toi <= 10001 <= capacity <= 105
方法一:优先队列
首先二话不说对trips按“上车地点”为依据从小到大排个序。
接着创建一个优先队列,用于存放“已上车的人”。优先队列的排序依据是“先下车的人优先”。
使用一个变量记录当前车上的人数,遍历trips数组:
让优先队列中,不晚于此位置的人下车;
让这批人上车。
期间若出现超载的情况则返回false,否则返回true。
- 时间复杂度 O ( n log n ) O(n\log n) O(nlogn),其中 n = l e n ( t r i p s ) n=len(trips) n=len(trips)
- 空间复杂度 O ( n ) O(n) O(n)
AC代码
C++
class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {sort(trips.begin(), trips.end(), [](const vector<int>& a, const vector<int>& b) {return a[1] < b[1];});int nowPeopleCnt = 0;auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {return a.second > b.second;};priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> nowPeople(cmp);for (vector<int>& trip : trips) {int num = trip[0], from = trip[1], to = trip[2];while (nowPeople.size() && nowPeople.top().second <= from) {nowPeopleCnt -= nowPeople.top().first;nowPeople.pop();}nowPeopleCnt += num;if (nowPeopleCnt > capacity) {return false;}nowPeople.push({num, to});}return true;}
};
Python
# from typing import List
# import heapqclass Solution:def carPooling(self, trips: List[List[int]], capacity: int) -> bool:trips.sort(key=lambda x: x[1])nowPeopleCnt = 0nowPeople = []for num, from_, to in trips:while nowPeople and nowPeople[0][0] <= from_:nowPeopleCnt -= nowPeople[0][1]heapq.heappop(nowPeople)nowPeopleCnt += numif nowPeopleCnt > capacity:return Falseheapq.heappush(nowPeople, (to, num))return True
同步发文于CSDN,原创不易,转载经作者同意后请附上原文链接哦~
Tisfy:https://letmefly.blog.csdn.net/article/details/134751973
相关文章:
LeetCode 1094. 拼车:优先队列
【LetMeFly】1094.拼车:优先队列 力扣题目链接:https://leetcode.cn/problems/car-pooling/ 车上最初有 capacity 个空座位。车 只能 向一个方向行驶(也就是说,不允许掉头或改变方向) 给定整数 capacity 和一个数组…...
项目开发维护技术文档(总结梳理)
目录 一、项目背景 二、架构设计 1.技术栈 2.架构图 3.代码结构 三、模块划分 1.用户模块 2.商品模块 四、开发规范 1.命名规范 2.代码格式 3.版本控制 五、部署流程 1.环境要求 2.部署流程 六、问题解决 1.数据库连接异常 2.Redis缓存失效 七、参考资料 项…...
01_学习使用javax_ws_rs_上传文件
文章目录 1 前言2 Maven 依赖3 上传接口4 如何解析 MultipartFormDataInput5 结语 1 前言 使用 Spring MVC 来处理文件上传,想必是大家耳熟能详的了,如下代码: ResponseBody PostMapping("/upload") public String upload(Request…...
MFC 发布CLXHHandleEngine动态库1.0.0.0版本
第一版发布以下功能,此项目使用VS2013创建,项目配置包括Unicode的Mdd,md与多字节版本: //MFC Grid表格 #include "../MFCGridCtrl/GridCtrl.h" //使用AES与Base64加密解密可以与java中的AES加解密衔接 //AES加密解密 #include &q…...
MicroPython 基于microdot框架搭建网页服务器
MicroPython 基于microdot框架搭建网页服务器 简介简单demo 简介 Microdot是一个极简的Python web框架,灵感来自于Flask,它被设计用来运行在资源有限的系统上,如微控制器。它运行在标准的Python和MicroPython上。 API参考microdot 资源下载m…...
FL Studio21.2汉化永久中文语言包
FL Studio21.2这款软件在国内被广泛使用,因此又被称为"水果"。它提供音符编辑器,可以针对作曲者的要求编辑出不同音律的节奏,例如鼓、镲、锣、钢琴、笛、大提琴、筝、扬琴等等任何乐器的节奏律动。此外,它还提供了方便快…...
Glide结合OkHttp保证短信验证接口携带图形验证码接口返回Cookie值去做网络请求
一、实现效果 二、步骤 注意:仅展示核心部分代码 1、导入依赖 api com.github.bumptech.glide:glide:4.10.0 kapt com.github.bumptech.glide:compiler:4.10.0 api com.squareup.okhttp3:okhttp:3.11.0 api com.squareup.okhttp3:logging-interceptor:3.11.02、自…...
怎样用Ajax提交from表单并接收其中的json数据
怎样用Ajax提交表单并接收其中的json数据 需求:实现点击按钮后,数据以表单形式提交至服务器,并接收来自服务器的返回数据。过程中页面不刷新。 AJAX 不是新的编程语言,而是一种使用现有标准的新方法。AJAX 是与服务器交换数据并…...
【动态规划】LeetCode-746LCR 088.使用最小花费爬楼梯
🎈算法那些事专栏说明:这是一个记录刷题日常的专栏,每个文章标题前都会写明这道题使用的算法。专栏每日计划至少更新1道题目,在这立下Flag🚩 🏠个人主页:Jammingpro 📕专栏链接&…...
Unity 接入TapADN播放广告时闪退 LZ4JavaSafeCompressor
通过跟踪安卓日志,发现报如下错误 Didnt find class "com.tapadn.lz4.LZ4JavaSafeCompressor" 解决方案: 去掉Minify这边的勾选,再打包即可。...
【九】linux下部署frp客户端服务端实践(内网穿透)
linux下部署frp客户端服务端实践 简介: 今天有一个这样的需求,部署在公司内部局域网虚拟机上的服务需要在外网能够访问到,这不就是内网穿透的需求吗,之前通过路由器实现过,现在公司这块路由器不具备这个功能了&#x…...
华为1+x网络系统建设与运维(中级)-练习题2
一.设备命令 LSW1 [Huawei]sys LSW1 同理可得,给所有设备改名 二.VLAN LSW1 [LSW1]vlan ba 10 20 [LSW1]int g0/0/1 [LSW1-GigabitEthernet0/0/1]port link-type trunk [LSW1-GigabitEthernet0/0/1]port trunk allow-pass vlan 10 20 [LSW1-GigabitEthernet0/0/1]in…...
自定义类型-结构体,联合体和枚举-C语言
引言 能看到结构体,说明C语言想必学习的时间也不少了,在之前肯定也学习过基本数据类型,包括整型int,浮点型float等等。可是在日常生活中,想要描述一个事物并没有那么简单。比如,你要描述一本书,…...
Windows 安装redis,设置开机自启动
Windows 安装redis,设置开机自启动 文章目录 Windows 安装redis,设置开机自启动下载, 解压到指定目录设置redis密码启动redis服务端停止redis服务端设置自启动 下载, 解压到指定目录 官网地址: https://redis.io/ 安装包下载地址: https://github.com/tporadowski/redis/relea…...
Windows安装Mysql Workbench及常用操作
Mysql Workbench是mysql自带的可视化操作界面,功能是强大的,但界面和navicat比,就是觉得别扭,但其实用惯了也还好,各有特色吧。这里记录一下常用的操作。 官方手册:MySQL Workbench 一、安装 1. 下载 官方…...
【计算机网络】15、NAT、NAPT 网络地址转换、打洞
文章目录 一、概念二、分类(主要是传统 NAT)2.1 基本 NAT2.2 NAPT 三、访问NAT下的内网设备的方式3.1 多拨3.2 端口转发、DMZ3.3 UPnP IGD、NAT-PMP3.4 服务器中转:frp 内网穿透3.4.1 NAT 打洞3.4.2 NAT 类型与打洞成功率3.4.2.1 完全圆锥形 …...
【送书活动三期】解决docker服务假死问题
工作中使用docker-compose部署容器,有时候会出现使用docker-compose stop或docker-compose down命令想停掉容器,但是依然无法停止或者一直卡顿在停止中的阶段,这种问题很让人头疼啊! 目录 问题描述问题排查问题解决终极杀招-最粗暴…...
【每日一题】拼车+【差分数组】
文章目录 Tag题目来源解题思路方法一:差分 写在最后 Tag 【差分数组】【数组】【2023-12-02】 题目来源 1094. 拼车 解题思路 本题朴素的解题思路是统计题目中提到的每一个站点的车上人数,如果某个站点的车上人数大于车上的座位数直接返回 false&…...
【开源】基于JAVA的农村物流配送系统
项目编号: S 024 ,文末获取源码。 \color{red}{项目编号:S024,文末获取源码。} 项目编号:S024,文末获取源码。 目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 系统登录、注册界面2.2 系统功能2.2…...
7、Jenkins+Nexus3+Docker+K8s实现CICD
文章目录 基本环境配置一、Jenkins安装必要插件二、Jenkins系统配置三、新建流水线四、在项目工程里添加Jenkinsfile、deploy.yml五、在项目工程里添加Dockerfile在这里插入图片描述 总结 提示:本章主要记录各基本环境搭建好后如何配置Jenkins流水线部署微服务到K8s…...
2024年赣州旅游投资集团社会招聘笔试真
2024年赣州旅游投资集团社会招聘笔试真 题 ( 满 分 1 0 0 分 时 间 1 2 0 分 钟 ) 一、单选题(每题只有一个正确答案,答错、不答或多答均不得分) 1.纪要的特点不包括()。 A.概括重点 B.指导传达 C. 客观纪实 D.有言必录 【答案】: D 2.1864年,()预言了电磁波的存在,并指出…...
基于Uniapp开发HarmonyOS 5.0旅游应用技术实践
一、技术选型背景 1.跨平台优势 Uniapp采用Vue.js框架,支持"一次开发,多端部署",可同步生成HarmonyOS、iOS、Android等多平台应用。 2.鸿蒙特性融合 HarmonyOS 5.0的分布式能力与原子化服务,为旅游应用带来…...
在四层代理中还原真实客户端ngx_stream_realip_module
一、模块原理与价值 PROXY Protocol 回溯 第三方负载均衡(如 HAProxy、AWS NLB、阿里 SLB)发起上游连接时,将真实客户端 IP/Port 写入 PROXY Protocol v1/v2 头。Stream 层接收到头部后,ngx_stream_realip_module 从中提取原始信息…...
[Java恶补day16] 238.除自身以外数组的乘积
给你一个整数数组 nums,返回 数组 answer ,其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。 题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。 请 不要使用除法,且在 O(n) 时间复杂度…...
Android第十三次面试总结(四大 组件基础)
Activity生命周期和四大启动模式详解 一、Activity 生命周期 Activity 的生命周期由一系列回调方法组成,用于管理其创建、可见性、焦点和销毁过程。以下是核心方法及其调用时机: onCreate() 调用时机:Activity 首次创建时调用。…...
算法岗面试经验分享-大模型篇
文章目录 A 基础语言模型A.1 TransformerA.2 Bert B 大语言模型结构B.1 GPTB.2 LLamaB.3 ChatGLMB.4 Qwen C 大语言模型微调C.1 Fine-tuningC.2 Adapter-tuningC.3 Prefix-tuningC.4 P-tuningC.5 LoRA A 基础语言模型 A.1 Transformer (1)资源 论文&a…...
【C++进阶篇】智能指针
C内存管理终极指南:智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...
Linux nano命令的基本使用
参考资料 GNU nanoを使いこなすnano基础 目录 一. 简介二. 文件打开2.1 普通方式打开文件2.2 只读方式打开文件 三. 文件查看3.1 打开文件时,显示行号3.2 翻页查看 四. 文件编辑4.1 Ctrl K 复制 和 Ctrl U 粘贴4.2 Alt/Esc U 撤回 五. 文件保存与退出5.1 Ctrl …...
【Elasticsearch】Elasticsearch 在大数据生态圈的地位 实践经验
Elasticsearch 在大数据生态圈的地位 & 实践经验 1.Elasticsearch 的优势1.1 Elasticsearch 解决的核心问题1.1.1 传统方案的短板1.1.2 Elasticsearch 的解决方案 1.2 与大数据组件的对比优势1.3 关键优势技术支撑1.4 Elasticsearch 的竞品1.4.1 全文搜索领域1.4.2 日志分析…...
基于鸿蒙(HarmonyOS5)的打车小程序
1. 开发环境准备 安装DevEco Studio (鸿蒙官方IDE)配置HarmonyOS SDK申请开发者账号和必要的API密钥 2. 项目结构设计 ├── entry │ ├── src │ │ ├── main │ │ │ ├── ets │ │ │ │ ├── pages │ │ │ │ │ ├── H…...
