当前位置: 首页 > news >正文

【算法思考记录】力扣1094.拼车 C++【树状数组】

拼车问题(LeetCode 1094)的解析与C++实现

Problem: 1094. 拼车

题目背景

在本题中,我们需要处理一个拼车的问题。假设一辆车有固定的座位容量,我们需要根据乘客的上车和下车地点,判断车辆是否能够在整个行程中满足不超过最大容量的要求。

题目描述

给定一个整数 capacity 表示车的座位数,和一个数组 tripstrips[i] 表示第 i 次旅行有 numPassengersi 乘客,乘客上车和下车的位置分别是 fromitoi。若车辆能在所有行程中接送所有乘客,则返回 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++【树状数组】

拼车问题&#xff08;LeetCode 1094&#xff09;的解析与C实现 Problem: 1094. 拼车 题目背景 在本题中&#xff0c;我们需要处理一个拼车的问题。假设一辆车有固定的座位容量&#xff0c;我们需要根据乘客的上车和下车地点&#xff0c;判断车辆是否能够在整个行程中满足不超过…...

业务场景中Hive解析Json常用案例

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

垃圾回收与内存泄漏

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

SQL Server 2016(创建数据表)

1、需求描述。 在名为“class”的数据库中创建表&#xff0c;表名称为“course”&#xff0c;其中要包含序号、课程、课程编号、学分、任课教师、上课地点、开始时间、结束时间、备注等列。 设置各个字段的数据类型。其中&#xff0c;"序号"列为标识列&#xff0c;从…...

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 模型配置 四、整体总结 论文&#xff1a;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 字节显示&#xff08;word&#xff09;8 字节显示&#xff08;通常long&#xff09;十进制显示显示指定列数显示地址范围内的值 Trace32 常用命令之 d.dump | data.dump 介绍 在 TRACE32 调试环境中&a…...

【Git】Git撤销操作

记录一下&#xff0c;方便后续查找&#xff0c;不全&#xff0c;后续再做补充。 丢弃当前工作区未提交的修改 # 丢弃所有修改 git checkout .# 丢弃某个文件修改 git checkout 文件名丢弃本地已经提交的代码 &#xff08;1&#xff09;撤销最近一次提交 如果我们在最近一次提…...

改造python3中的http.server为简单的文件上传下载服务

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

Fiddler抓包工具之fiddler的composer可以简单发送http协议的请求

一&#xff0c;composer的详解 右侧Composer区域&#xff0c;是测试接口的界面&#xff1a; 相关说明&#xff1a; 1.请求方式&#xff1a;点开可以勾选请求协议是get、post等 2.url地址栏&#xff1a;输入请求的url地址 3.请求头&#xff1a;第三块区域可以输入请求头信息…...

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第十三章笔记

目录 基类 构造函数&#xff1a;访问权限的考虑 1.2 派生类和基类之间的特殊关系 继承&#xff1a;is-a关系 多态公有继承 静态联编和动态联编 指针和引用类型的兼容性 虚成员函数和动态联编 虚函数的注意事项 构造函数 析构函数 友元 没有重新定义 重新定义将隐…...

【JavaEE】单例模式

作者主页&#xff1a;paper jie_博客 本文作者&#xff1a;大家好&#xff0c;我是paper jie&#xff0c;感谢你阅读本文&#xff0c;欢迎一建三连哦。 本文于《JavaEE》专栏&#xff0c;本专栏是针对于大学生&#xff0c;编程小白精心打造的。笔者用重金(时间和精力)打造&…...

第十五届蓝桥杯模拟赛(第二期 C++)

俺自己做的噢&#xff0c;还未核实答案&#xff0c;若有差错&#xff0c;望斧正。 第一题 小蓝要在屏幕上放置一行文字&#xff0c;每个字的宽度相同。小蓝发现&#xff0c;如果每个字的宽为 36 像素&#xff0c;一行正好放下 30 个字&#xff0c;字符之间和前后都没有任何空隙…...

关于Unity中字典在Inspector的显示

字典在Inspector的显示 方法一&#xff1a;实现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.前言 用手机或者平板电脑看视频&#xff0c;已经算是生活中稀松平常的场景了&#xff0c;特别是各…...

svn合并冲突时每个选项的含义

合并冲突时每个选项的含义 - 这个图片是 TortoiseSVN&#xff08;一个Subversion&#xff08;SVN&#xff09;客户端&#xff09;的合并冲突解决对话框。当你尝试合并两个版本的文件并且出现差异时&#xff0c;你需要解决这些差异。这个对话框提供了几个选项来处理合并冲突&…...

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 客户端

&#x1f31f; 什么是 MCP&#xff1f; 模型控制协议 (MCP) 是一种创新的协议&#xff0c;旨在无缝连接 AI 模型与应用程序。 MCP 是一个开源协议&#xff0c;它标准化了我们的 LLM 应用程序连接所需工具和数据源并与之协作的方式。 可以把它想象成你的 AI 模型 和想要使用它…...

为什么需要建设工程项目管理?工程项目管理有哪些亮点功能?

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

全志A40i android7.1 调试信息打印串口由uart0改为uart3

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

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

IP如何挑?2025年海外专线IP如何购买?

你花了时间和预算买了IP&#xff0c;结果IP质量不佳&#xff0c;项目效率低下不说&#xff0c;还可能带来莫名的网络问题&#xff0c;是不是太闹心了&#xff1f;尤其是在面对海外专线IP时&#xff0c;到底怎么才能买到适合自己的呢&#xff1f;所以&#xff0c;挑IP绝对是个技…...

[免费]微信小程序问卷调查系统(SpringBoot后端+Vue管理端)【论文+源码+SQL脚本】

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

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

GO协程(Goroutine)问题总结

在使用Go语言来编写代码时&#xff0c;遇到的一些问题总结一下 [参考文档]&#xff1a;https://www.topgoer.com/%E5%B9%B6%E5%8F%91%E7%BC%96%E7%A8%8B/goroutine.html 1. main()函数默认的Goroutine 场景再现&#xff1a; 今天在看到这个教程的时候&#xff0c;在自己的电…...

在 Spring Boot 项目里,MYSQL中json类型字段使用

前言&#xff1a; 因为程序特殊需求导致&#xff0c;需要mysql数据库存储json类型数据&#xff0c;因此记录一下使用流程 1.java实体中新增字段 private List<User> users 2.增加mybatis-plus注解 TableField(typeHandler FastjsonTypeHandler.class) private Lis…...