【算法思考记录】力扣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)客户端)的合并冲突解决对话框。当你尝试合并两个版本的文件并且出现差异时,你需要解决这些差异。这个对话框提供了几个选项来处理合并冲突&…...

【入坑系列】TiDB 强制索引在不同库下不生效问题
文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

Java面试专项一-准备篇
一、企业简历筛选规则 一般企业的简历筛选流程:首先由HR先筛选一部分简历后,在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如:Boss直聘(招聘方平台) 直接按照条件进行筛选 例如:…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2
每日一言 今天的每一份坚持,都是在为未来积攒底气。 案例:OLED显示一个A 这边观察到一个点,怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 : 如果代码里信号切换太快(比如 SDA 刚变,SCL 立刻变&#…...

算法岗面试经验分享-大模型篇
文章目录 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…...
uniapp 字符包含的相关方法
在uniapp中,如果你想检查一个字符串是否包含另一个子字符串,你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的,但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

FFmpeg avformat_open_input函数分析
函数内部的总体流程如下: avformat_open_input 精简后的代码如下: int avformat_open_input(AVFormatContext **ps, const char *filename,ff_const59 AVInputFormat *fmt, AVDictionary **options) {AVFormatContext *s *ps;int i, ret 0;AVDictio…...

何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡
何谓AI编程【02】AI编程官网以优雅草星云智控为例建设实践-完善顶部-建立各项子页-调整排版-优雅草卓伊凡 背景 我们以建设星云智控官网来做AI编程实践,很多人以为AI已经强大到不需要程序员了,其实不是,AI更加需要程序员,普通人…...

归并排序:分治思想的高效排序
目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法,由约翰冯诺伊曼在1945年提出。其核心思想包括: 分割(Divide):将待排序数组递归地分成两个子…...
HTML中各种标签的作用
一、HTML文件主要标签结构及说明 1. <!DOCTYPE html> 作用:声明文档类型,告知浏览器这是 HTML5 文档。 必须:是。 2. <html lang“zh”>. </html> 作用:包裹整个网页内容,lang"z…...

Element-Plus:popconfirm与tooltip一起使用不生效?
你们好,我是金金金。 场景 我正在使用Element-plus组件库当中的el-popconfirm和el-tooltip,产品要求是两个需要结合一起使用,也就是鼠标悬浮上去有提示文字,并且点击之后需要出现气泡确认框 代码 <el-popconfirm title"是…...