【算法思考记录】力扣1094.拼车 C++【树状数组】
拼车问题(LeetCode 1094)的解析与C++实现
Problem: 1094. 拼车
题目背景
在本题中,我们需要处理一个拼车的问题。假设一辆车有固定的座位容量,我们需要根据乘客的上车和下车地点,判断车辆是否能够在整个行程中满足不超过最大容量的要求。
题目描述
给定一个整数 capacity
表示车的座位数,和一个数组 trips
。trips[i]
表示第 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 <= 1000
trips[i].length == 3
1 <= numPassengersi <= 100
0 <= fromi < toi <= 1000
1 <= capacity <= 10^5
解题思路
为解决这个问题,我们可以使用树状数组(Fenwick Tree)来处理区间的增加操作。对于每次旅行,我们将乘客数量加到上车点,并在下车点之后减去相同的乘客数。然后,我们检查每个点的乘客总数是否超过车辆容量。
C++ 代码实现
#include <vector>
#include <iostream>
using namespace std;class Solution {
public:bool carPooling(vector<vector<int>>& trips, int capacity) {vector<int> tree(1002, 0);// 树状数组的lowbit,返回x的二进制中的最右侧的1对应的数值auto lowbit = [&](int x) -> int {return x & -x;};// 对[idx, 1000]这个区间增加valauto add = [&](int idx, int val) {for (int i = idx; i < 1001; i += lowbit(i)) {tree[i] += val;}};// 查询[0, idx]的和auto query = [&](int idx) -> int {int res = 0;for (int i = idx; i; i -= lowbit(i)) {res += tree[i];}return res;};for (auto& t : trips) {int num = t[0], from = t[1], to = t[2];add(from + 1, num); // 给[from, 1000]加上numadd(to + 1, -num); // 给[to, 1000]减去num}for (int i = 0; i < 1001; ++i) {if (query(i) > capacity) {return false;}}return true;}
};
测试用例
int main() {Solution solution;vector<vector<int>> trips1 = {{2, 1, 5}, {3, 3, 7}};int capacity1 = 4;cout << "Test Case 1: " << (solution.carPooling(trips1, capacity1) ? "True" : "False") << endl;vector<vector<int>> trips2 = {{2, 1, 5}, {3, 3, 7}};int capacity2 = 5;cout << "Test Case 2: " << (solution.carPooling(trips2, capacity2) ? "True" : "False") << endl;return 0;
}
在这个C++实现中,我们利用树状数组的特性来优化区间更新和查询操作,从而有效处理拼车问题的乘客统计。
相关文章:
【算法思考记录】力扣1094.拼车 C++【树状数组】
拼车问题(LeetCode 1094)的解析与C实现 Problem: 1094. 拼车 题目背景 在本题中,我们需要处理一个拼车的问题。假设一辆车有固定的座位容量,我们需要根据乘客的上车和下车地点,判断车辆是否能够在整个行程中满足不超过…...

业务场景中Hive解析Json常用案例
业务场景中Hive解析Json常用案例 json在线工具 json格式转换在线工具 https://tool.lu/json/format格式互转: // 格式化可以合并整行显示 {"name":"John Doe","age":35,"email":"johnexample.com"}// 格式化…...

垃圾回收与内存泄漏
前端面试大全JavaScript垃圾回收与内存泄漏 🌟经典真题 🌟什么是内存泄露 🌟JavaScript 中的垃圾回收 🌟标记清除 🌟引用计数 🌟真题解答 🌟总结 🌟经典真题 请介绍一下 Jav…...

SQL Server 2016(创建数据表)
1、需求描述。 在名为“class”的数据库中创建表,表名称为“course”,其中要包含序号、课程、课程编号、学分、任课教师、上课地点、开始时间、结束时间、备注等列。 设置各个字段的数据类型。其中,"序号"列为标识列,从…...
mysql配置文件低于8.0版本慎用(头部声明的路径请自行替换或删减)(干货)
[mysqld] character-set-server utf8mb4 collation-server utf8mb4_general_ci init_connectSET NAMES utf8mb4datadir/data/mysql/data socket/data/mysql/mysql.socklog-error/data/mysql/log/mysql_error.log pid-file/data/mysql/mysqld.pidserver_id1 #如果做集群不同my…...
给WordPress文章添加广告位
/* * WordPress 在文章内容中间插入广告//由www.wwttl.com提供学习 */ //在文章内容的第二段后面插入广告 add_filter( the_content, prefix_insert_post_ads ); function prefix_insert_post_ads( $content ) { $ad_code <div>广告代码放这里</div>;if ( is_sing…...

[GPT-1]论文实现:Improving Language Understanding by Generative Pre-Training
Efficient Graph-Based Image Segmentation 一、完整代码二、论文解读2.1 GPT架构2.2 GPT的训练方式Unsupervised pre_trainingSupervised fine_training 三、过程实现3.1 导包3.2 数据处理3.3 模型构建3.4 模型配置 四、整体总结 论文:Improving Language Understa…...

23种设计模式之C++实践(一)
23种设计模式之C++实践 1. 简介2. 基础知识3. 设计模式(一)创建型模式1. 单例模式——确保对象的唯一性1.2 饿汉式单例模式1.3 懒汉式单例模式比较IoDH单例模式总结2. 简单工厂模式——集中式工厂的实现简单工厂模式总结3. 工厂方法模式——多态工厂的实现工厂方法模式总结4.…...

华为OD机试 - 园区参观路径(Java JS Python C)
题目描述 园区某部门举办了Family Day,邀请员工及其家属参加; 将公司园区视为一个矩形,起始园区设置在左上角,终点园区设置在右下角; 家属参观园区时,只能向右和向下园区前进,求从起始园区到终点园区会有多少条不同的参观路径。 输入描述 第一行为园区的长和宽; 后…...

【ARM Trace32(劳特巴赫) 使用介绍 12 -- Trace32 常用命令之 d.dump | data.dump 介绍】
文章目录 Trace32 常用命令之 d.dump | data.dump 介绍1 字节显示 (Byte)4 字节显示(word)8 字节显示(通常long)十进制显示显示指定列数显示地址范围内的值 Trace32 常用命令之 d.dump | data.dump 介绍 在 TRACE32 调试环境中&a…...
【Git】Git撤销操作
记录一下,方便后续查找,不全,后续再做补充。 丢弃当前工作区未提交的修改 # 丢弃所有修改 git checkout .# 丢弃某个文件修改 git checkout 文件名丢弃本地已经提交的代码 (1)撤销最近一次提交 如果我们在最近一次提…...

改造python3中的http.server为简单的文件上传下载服务
改造 修改python3中的http.server.SimpleHTTPRequestHandler,实现简单的文件上传下载服务 simple_http_file_server.py: # !/usr/bin/env python3import datetime import email import html import http.server import io import mimetypes import os …...

Fiddler抓包工具之fiddler的composer可以简单发送http协议的请求
一,composer的详解 右侧Composer区域,是测试接口的界面: 相关说明: 1.请求方式:点开可以勾选请求协议是get、post等 2.url地址栏:输入请求的url地址 3.请求头:第三块区域可以输入请求头信息…...

14、pytest像用参数一样使用fixture
官方实例 # content of test_fruit.py import pytestclass Fruit:def __init__(self, name):self.name nameself.cubed Falsedef cube(self):self.cubed Trueclass FruitSalad:def __init__(self, *fruit_bowl):self.fruit fruit_bowlself._cube_fruit()def _cube_fruit(s…...
C++ Primer Plus第十三章笔记
目录 基类 构造函数:访问权限的考虑 1.2 派生类和基类之间的特殊关系 继承:is-a关系 多态公有继承 静态联编和动态联编 指针和引用类型的兼容性 虚成员函数和动态联编 虚函数的注意事项 构造函数 析构函数 友元 没有重新定义 重新定义将隐…...

【JavaEE】单例模式
作者主页:paper jie_博客 本文作者:大家好,我是paper jie,感谢你阅读本文,欢迎一建三连哦。 本文于《JavaEE》专栏,本专栏是针对于大学生,编程小白精心打造的。笔者用重金(时间和精力)打造&…...
第十五届蓝桥杯模拟赛(第二期 C++)
俺自己做的噢,还未核实答案,若有差错,望斧正。 第一题 小蓝要在屏幕上放置一行文字,每个字的宽度相同。小蓝发现,如果每个字的宽为 36 像素,一行正好放下 30 个字,字符之间和前后都没有任何空隙…...

关于Unity中字典在Inspector的显示
字典在Inspector的显示 方法一:实现ISerializationCallbackReceiver接口 《unity3D游戏开发第二版》记录 在编辑面板中可以利用序列化监听接口特性对字典进行序列化。 主要继承ISerializationCallbackReceiver接口 实现OnAfterDeserialize() OnBeforeSerialize() …...

使用Plex结合cpolar搭建本地私人媒体站并实现远程访问
文章目录 1.前言2. Plex网站搭建2.1 Plex下载和安装2.2 Plex网页测试2.3 cpolar的安装和注册 3. 本地网页发布3.1 Cpolar云端设置3.2 Cpolar本地设置 4. 公网访问测试5. 结语 1.前言 用手机或者平板电脑看视频,已经算是生活中稀松平常的场景了,特别是各…...

svn合并冲突时每个选项的含义
合并冲突时每个选项的含义 - 这个图片是 TortoiseSVN(一个Subversion(SVN)客户端)的合并冲突解决对话框。当你尝试合并两个版本的文件并且出现差异时,你需要解决这些差异。这个对话框提供了几个选项来处理合并冲突&…...
DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径
目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

理解 MCP 工作流:使用 Ollama 和 LangChain 构建本地 MCP 客户端
🌟 什么是 MCP? 模型控制协议 (MCP) 是一种创新的协议,旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议,它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?
在建筑行业,项目管理的重要性不言而喻。随着工程规模的扩大、技术复杂度的提升,传统的管理模式已经难以满足现代工程的需求。过去,许多企业依赖手工记录、口头沟通和分散的信息管理,导致效率低下、成本失控、风险频发。例如&#…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3
一,概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本:2014.07; Kernel版本:Linux-3.10; 二,Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01),并让boo…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”
2025年#高考 将在近日拉开帷幕,#AI 监考一度冲上热搜。当AI深度融入高考,#时间同步 不再是辅助功能,而是决定AI监考系统成败的“生命线”。 AI亮相2025高考,40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕,江西、…...
IP如何挑?2025年海外专线IP如何购买?
你花了时间和预算买了IP,结果IP质量不佳,项目效率低下不说,还可能带来莫名的网络问题,是不是太闹心了?尤其是在面对海外专线IP时,到底怎么才能买到适合自己的呢?所以,挑IP绝对是个技…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】
大家好,我是java1234_小锋老师,看到一个不错的微信小程序问卷调查系统(SpringBoot后端Vue管理端)【论文源码SQL脚本】,分享下哈。 项目视频演示 【免费】微信小程序问卷调查系统(SpringBoot后端Vue管理端) Java毕业设计_哔哩哔哩_bilibili 项…...

搭建DNS域名解析服务器(正向解析资源文件)
正向解析资源文件 1)准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2)服务端安装软件:bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

GO协程(Goroutine)问题总结
在使用Go语言来编写代码时,遇到的一些问题总结一下 [参考文档]:https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现: 今天在看到这个教程的时候,在自己的电…...
在 Spring Boot 项目里,MYSQL中json类型字段使用
前言: 因为程序特殊需求导致,需要mysql数据库存储json类型数据,因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...