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

LeetCode刷题系列 -- 1094. 拼车

车上最初有 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 <= 1000

  • trips[i].length == 3

  • 1 <= numPassengersi <= 100

  • 0 <= fromi < toi <= 1000

  • 1 <= capacity <= 105

1094. 拼车 - 力扣(Leetcode)

思路小而美的算法技巧:差分数组 :: labuladong的算法小抄

本题也是可以利用 差分数组来求解

c++

class Solution {
public:vector<int> diff;void increment(vector<int>& diff, int i, int j, int val){diff[i] += val;if(j < diff.size()) {diff[j] -= val;}}bool carPooling(vector<vector<int>>& trips, int capacity) {diff = vector<int>(1001, 0);vector<int> result(1001, 0);int maxLen = 0;for(auto& trip:trips) {int numPassengers = trip[0];int from = trip[1];int to = trip[2];maxLen = max(maxLen, to);increment(diff, from, to, numPassengers);}result[0] = diff[0];for(int i=1; i<=maxLen; i++) {result[i] = result[i-1] + diff[i];}bool flag = true;for(int i=0; i<=maxLen; i++) {if(result[i] > capacity) {flag =  false;}}return flag;}
};

相关文章:

LeetCode刷题系列 -- 1094. 拼车

车上最初有 capacity 个空座位。车 只能 向一个方向行驶&#xff08;也就是说&#xff0c;不允许掉头或改变方向&#xff09;给定整数 capacity 和一个数组 trips , trip[i] [numPassengersi, fromi, toi] 表示第 i 次旅行有 numPassengersi 乘客&#xff0c;接他们和放他们的…...

二叉查找树的应用 —— K模型和KV模型

文章目录前言1. K模型2. KV模型&#x1f351; 构建KV模型的树&#x1f351; 英汉词典&#x1f351; 统计水果出现的次数3. 总结前言 在上一篇文章中&#xff0c;我们进行了二叉查找树的实现&#xff08;文章链接&#xff09;&#xff0c;那么今天主要探讨一下二叉查找树的应用…...

深度学习实战(11):使用多层感知器分类器对手写数字进行分类

使用多层感知器分类器对手写数字进行分类 1.简介 1.1 什么是多层感知器&#xff08;MLP&#xff09;&#xff1f; MLP 是一种监督机器学习 (ML) 算法&#xff0c;属于前馈人工神经网络 [1] 类。该算法本质上是在数据上进行训练以学习函数。给定一组特征和一个目标变量&#x…...

ThingsBoard-警报

1、使用 IoT 设备警报 ThingsBoard 提供了创建和管理与您的实体相关的警报的能力:设备、资产、客户等。例如,您可以将 ThingsBoard 配置为在温度传感器读数高于某个阈值时自动创建警报。当然,这是一个非常简化的案例,实际场景可能要复杂得多。 2、主要概念 下面让我们回…...

如何去阅读源码,我总结了18条心法

在聊如何去阅读源码之前&#xff0c;先来简单说一下为什么要去阅读源码&#xff0c;大致可分为以下几点原因&#xff1a;最直接的原因&#xff0c;就是面试需要&#xff0c;面试喜欢问源码&#xff0c;读完源码才可以跟面试官battle提升自己的编程水平&#xff0c;学习编程思想…...

排序:归并排序

一、归并 li[2,4,5,7,//1,3,6,8]#归并的前提是必须两部分排好序 def merge(li,low,mid,high):ilowjmid1ltmp[]while i<mid and j<high: #只要左右两边都有数if li[i]<li[j]:ltmp.append(li[i])i1else:ltmp.append(li[j])j1#while执行完&#xff0c;肯定有一部分没数…...

Allegro172版本线到铜皮不按照设定值避让的原因和解决办法

Allegro172版本线到铜皮不按照设定值避让的原因和解决办法 用Allegro做PCB设计的时候,有时会单独给某块铜皮附上线到铜皮额外再增加一个数值,如下图 在规则的基础上,额外再避让10mil 规则避让line到铜皮10.02mil 额外设置多避让10mil,避让的结果却是30.02mil,正确的是20.…...

小白该从哪方面入手学习大数据

大数据本质上是海量数据。 以往的数据开发&#xff0c;需要一定的Java基础和工作经验&#xff0c;门槛高&#xff0c;入门难。 如果零基础入门数据开发行业的小伙伴&#xff0c;可以从Python语言入手。 Python语言简单易懂&#xff0c;适合零基础入门&#xff0c;在编程语言…...

尚医通(十)数据字典加Redis缓存 | MongoDB

目录一、Redis介绍二、数据字典模块添加Redis缓存1、service_cmn模块&#xff0c;添加redis依赖2、service_cmn模块&#xff0c;添加Redis配置类3、在service_cmn模块&#xff0c;配置文件添加redis配置4、通过注解添加redis缓存5、查询数据字典列表添加Redis缓存6、bug&#x…...

为什么我们不再发明编程语言了?

上个世纪&#xff0c;数百种编程语言被发明出来&#xff0c;但是进入21世纪&#xff0c;当我们都进入互联网时代时&#xff0c;只剩那么寥寥几个了。 如果你翻一下TIOBE得编程语言排行榜&#xff0c;就会发现20年来&#xff0c;上蹿下跳的就是那几张老面孔&#xff1a;C , Java…...

预处理指令详解

预处理指令详解**1.预定义符号****2.#define****2.1 #define 定义标识符****2.2 #define 定义宏****2.3 #define 替换规则****2.4 #和##****#的作用****##的作用****2.5 带副作用的宏参数****2.6 宏和函数的对比****宏和函数对比图****2.7 命名约定****3.#undef**4.条件编译4.1…...

Redis

一.认识NoSQL 1.SQL 关系型数据库 结构化: 定义主键&#xff0c;无符号型数据等关联的&#xff1a;结构化表和表之间的关系通过外键进行关联&#xff0c;节省存储空间SQL查询&#xff1a;语法固定 SELECT id,name,age FROM tb_user WHERE id1 ACID 2.NoSQL 非关系型数据库 Re…...

Elasticsearch5.5.1 自定义评分插件开发

文本相似度插件开发&#xff0c;本文基于Elasticsearch5.5.1&#xff0c;Kibana5.5.1 下载地址为&#xff1a; Past Releases of Elastic Stack Software | Elastic 本地启动两个服务后&#xff0c;localhost:5601打开Kibana界面&#xff0c;点击devTools&#xff0c;效果图…...

4.4 序列化与反序列化

文章目录1.概述2.特点/应用场景3.涉及到的流对象4.代码实现序列化与反序列化4.1 步骤1&#xff1a;创建学生类Student24.2 步骤2&#xff1a;创建序列化测试类5.测试案例中常见的几种编译错误类型6.为什么反序列化版本号需要与序列化版本号一致&#xff1f;7.自动提示 生成UID …...

647. 回文子串 516. 最长回文子序列

647. 回文子串 方法一&#xff1a;动态规划 dp[i][j]:[i,j]范围的下标字符串s是否为回文子串 遍历字符串&#xff0c;每次判断s[i]与s[j]是否相等 ①若相等&#xff0c;j-i0 即单个字符串s[i]&#xff0c;那么一定为回文子串&#xff0c;赋值为1 ②若相等&#xff0c;j-i1…...

实用小妙招

记录一些实用小妙招&#xff0c;都是收藏夹里收藏的各种文章&#xff0c;总结在一起&#xff0c;持续更新 实用小妙招LinuxUbuntu修改终端语言安装 Node.js (nvm)git 记住账号密码WSL迁移默认用户修改Linux Ubuntu 修改终端语言 apt update apt install -y language-pack-zh…...

别让猴子跳回背上

1.管理者的贡献来自于他们的判断力与影响力&#xff0c;而非他们所投入的个人时间与埋头苦干 2.管理者的绩效表现则是许多人群策群力的结果 3.管理者的时间管理: 老板占用的时间;组织占用的时间;自己占用的时间;外界占用的时间; 4.管理者的策略在于增加自己的时间&#xff0c…...

数据结构 | 线性表

&#x1f525;Go for it!&#x1f525; &#x1f4dd;个人主页&#xff1a;按键难防 &#x1f4eb; 如果文章知识点有错误的地方&#xff0c;请指正&#xff01;和大家一起学习&#xff0c;一起进步&#x1f440; &#x1f4d6;系列专栏&#xff1a;数据结构与算法 &#x1f52…...

Deepwalk深度游走算法

主要思想 Deepwalk是一种将随机游走和word2vec两种算法相结合的图结构数据的挖掘算法。该算法可以学习网络的隐藏信息&#xff0c;能够将图中的节点表示为一个包含潜在信息的向量&#xff0c; Deepwalk算法 该算法主要分为随机游走和生成表示向量两个部分&#xff0c;首先…...

微服务项目【服务调用分布式session共享】

nginx动静分离 第1步&#xff1a;通过SwitchHosts新增二级域名&#xff1a;images.zmall.com 第2步&#xff1a;将本次项目的所有静态资源js/css/images复制到nginx中的html目录下 第3步&#xff1a;在nginx的核心配置文件nginx.conf中新增二级域名images.zmall.com访问映射…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql

智慧工地管理云平台系统&#xff0c;智慧工地全套源码&#xff0c;java版智慧工地源码&#xff0c;支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求&#xff0c;提供“平台网络终端”的整体解决方案&#xff0c;提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台

🎯 使用 Streamlit 构建支持主流大模型与 Ollama 的轻量级统一平台 📌 项目背景 随着大语言模型(LLM)的广泛应用,开发者常面临多个挑战: 各大模型(OpenAI、Claude、Gemini、Ollama)接口风格不统一;缺乏一个统一平台进行模型调用与测试;本地模型 Ollama 的集成与前…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

Web后端基础(基础知识)

BS架构&#xff1a;Browser/Server&#xff0c;浏览器/服务器架构模式。客户端只需要浏览器&#xff0c;应用程序的逻辑和数据都存储在服务端。 优点&#xff1a;维护方便缺点&#xff1a;体验一般 CS架构&#xff1a;Client/Server&#xff0c;客户端/服务器架构模式。需要单独…...

xmind转换为markdown

文章目录 解锁思维导图新姿势&#xff1a;将XMind转为结构化Markdown 一、认识Xmind结构二、核心转换流程详解1.解压XMind文件&#xff08;ZIP处理&#xff09;2.解析JSON数据结构3&#xff1a;递归转换树形结构4&#xff1a;Markdown层级生成逻辑 三、完整代码 解锁思维导图新…...

绕过 Xcode?使用 Appuploader和主流工具实现 iOS 上架自动化

iOS 应用的发布流程一直是开发链路中最“苹果味”的环节&#xff1a;强依赖 Xcode、必须使用 macOS、各种证书和描述文件配置……对很多跨平台开发者来说&#xff0c;这一套流程并不友好。 特别是当你的项目主要在 Windows 或 Linux 下开发&#xff08;例如 Flutter、React Na…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

算法250609 高精度

加法 #include<stdio.h> #include<iostream> #include<string.h> #include<math.h> #include<algorithm> using namespace std; char input1[205]; char input2[205]; int main(){while(scanf("%s%s",input1,input2)!EOF){int a[205]…...

「Java基本语法」变量的使用

变量定义 变量是程序中存储数据的容器&#xff0c;用于保存可变的数据值。在Java中&#xff0c;变量必须先声明后使用&#xff0c;声明时需指定变量的数据类型和变量名。 语法 数据类型 变量名 [ 初始值]; 示例&#xff1a;声明与初始化 public class VariableDemo {publi…...