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…...
[特殊字符] 智能合约中的数据是如何在区块链中保持一致的?
🧠 智能合约中的数据是如何在区块链中保持一致的? 为什么所有区块链节点都能得出相同结果?合约调用这么复杂,状态真能保持一致吗?本篇带你从底层视角理解“状态一致性”的真相。 一、智能合约的数据存储在哪里…...
Lombok 的 @Data 注解失效,未生成 getter/setter 方法引发的HTTP 406 错误
HTTP 状态码 406 (Not Acceptable) 和 500 (Internal Server Error) 是两类完全不同的错误,它们的含义、原因和解决方法都有显著区别。以下是详细对比: 1. HTTP 406 (Not Acceptable) 含义: 客户端请求的内容类型与服务器支持的内容类型不匹…...
前端倒计时误差!
提示:记录工作中遇到的需求及解决办法 文章目录 前言一、误差从何而来?二、五大解决方案1. 动态校准法(基础版)2. Web Worker 计时3. 服务器时间同步4. Performance API 高精度计时5. 页面可见性API优化三、生产环境最佳实践四、终极解决方案架构前言 前几天听说公司某个项…...
【JavaWeb】Docker项目部署
引言 之前学习了Linux操作系统的常见命令,在Linux上安装软件,以及如何在Linux上部署一个单体项目,大多数同学都会有相同的感受,那就是麻烦。 核心体现在三点: 命令太多了,记不住 软件安装包名字复杂&…...
今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存
文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...
听写流程自动化实践,轻量级教育辅助
随着智能教育工具的发展,越来越多的传统学习方式正在被数字化、自动化所优化。听写作为语文、英语等学科中重要的基础训练形式,也迎来了更高效的解决方案。 这是一款轻量但功能强大的听写辅助工具。它是基于本地词库与可选在线语音引擎构建,…...
深度学习习题2
1.如果增加神经网络的宽度,精确度会增加到一个特定阈值后,便开始降低。造成这一现象的可能原因是什么? A、即使增加卷积核的数量,只有少部分的核会被用作预测 B、当卷积核数量增加时,神经网络的预测能力会降低 C、当卷…...
网站指纹识别
网站指纹识别 网站的最基本组成:服务器(操作系统)、中间件(web容器)、脚本语言、数据厍 为什么要了解这些?举个例子:发现了一个文件读取漏洞,我们需要读/etc/passwd,如…...
云原生安全实战:API网关Kong的鉴权与限流详解
🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 一、基础概念 1. API网关(API Gateway) API网关是微服务架构中的核心组件,负责统一管理所有API的流量入口。它像一座…...
站群服务器的应用场景都有哪些?
站群服务器主要是为了多个网站的托管和管理所设计的,可以通过集中管理和高效资源的分配,来支持多个独立的网站同时运行,让每一个网站都可以分配到独立的IP地址,避免出现IP关联的风险,用户还可以通过控制面板进行管理功…...
