当前位置: 首页 > 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;你需要解决这些差异。这个对话框提供了几个选项来处理合并冲突&…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

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

Java面试专项一-准备篇

一、企业简历筛选规则 一般企业的简历筛选流程&#xff1a;首先由HR先筛选一部分简历后&#xff0c;在将简历给到对应的项目负责人后再进行下一步的操作。 HR如何筛选简历 例如&#xff1a;Boss直聘&#xff08;招聘方平台&#xff09; 直接按照条件进行筛选 例如&#xff1a…...

学习STC51单片机32(芯片为STC89C52RCRC)OLED显示屏2

每日一言 今天的每一份坚持&#xff0c;都是在为未来积攒底气。 案例&#xff1a;OLED显示一个A 这边观察到一个点&#xff0c;怎么雪花了就是都是乱七八糟的占满了屏幕。。 解释 &#xff1a; 如果代码里信号切换太快&#xff08;比如 SDA 刚变&#xff0c;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 &#xff08;1&#xff09;资源 论文&a…...

uniapp 字符包含的相关方法

在uniapp中&#xff0c;如果你想检查一个字符串是否包含另一个子字符串&#xff0c;你可以使用JavaScript中的includes()方法或者indexOf()方法。这两种方法都可以达到目的&#xff0c;但它们在处理方式和返回值上有所不同。 使用includes()方法 includes()方法用于判断一个字…...

FFmpeg avformat_open_input函数分析

函数内部的总体流程如下&#xff1a; avformat_open_input 精简后的代码如下&#xff1a; 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编程实践&#xff0c;很多人以为AI已经强大到不需要程序员了&#xff0c;其实不是&#xff0c;AI更加需要程序员&#xff0c;普通人…...

归并排序:分治思想的高效排序

目录 基本原理 流程图解 实现方法 递归实现 非递归实现 演示过程 时间复杂度 基本原理 归并排序(Merge Sort)是一种基于分治思想的排序算法&#xff0c;由约翰冯诺伊曼在1945年提出。其核心思想包括&#xff1a; 分割(Divide)&#xff1a;将待排序数组递归地分成两个子…...

HTML中各种标签的作用

一、HTML文件主要标签结构及说明 1. <&#xff01;DOCTYPE html> 作用&#xff1a;声明文档类型&#xff0c;告知浏览器这是 HTML5 文档。 必须&#xff1a;是。 2. <html lang“zh”>. </html> 作用&#xff1a;包裹整个网页内容&#xff0c;lang"z…...

Element-Plus:popconfirm与tooltip一起使用不生效?

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