当前位置: 首页 > 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访问映射…...

iOS 26 携众系统重磅更新,但“苹果智能”仍与国行无缘

美国西海岸的夏天&#xff0c;再次被苹果点燃。一年一度的全球开发者大会 WWDC25 如期而至&#xff0c;这不仅是开发者的盛宴&#xff0c;更是全球数亿苹果用户翘首以盼的科技春晚。今年&#xff0c;苹果依旧为我们带来了全家桶式的系统更新&#xff0c;包括 iOS 26、iPadOS 26…...

Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?

Golang 面试经典题&#xff1a;map 的 key 可以是什么类型&#xff1f;哪些不可以&#xff1f; 在 Golang 的面试中&#xff0c;map 类型的使用是一个常见的考点&#xff0c;其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

QMC5883L的驱动

简介 本篇文章的代码已经上传到了github上面&#xff0c;开源代码 作为一个电子罗盘模块&#xff0c;我们可以通过I2C从中获取偏航角yaw&#xff0c;相对于六轴陀螺仪的yaw&#xff0c;qmc5883l几乎不会零飘并且成本较低。 参考资料 QMC5883L磁场传感器驱动 QMC5883L磁力计…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

Cinnamon修改面板小工具图标

Cinnamon开始菜单-CSDN博客 设置模块都是做好的&#xff0c;比GNOME简单得多&#xff01; 在 applet.js 里增加 const Settings imports.ui.settings;this.settings new Settings.AppletSettings(this, HTYMenusonichy, instance_id); this.settings.bind(menu-icon, menu…...

linux 下常用变更-8

1、删除普通用户 查询用户初始UID和GIDls -l /home/ ###家目录中查看UID cat /etc/group ###此文件查看GID删除用户1.编辑文件 /etc/passwd 找到对应的行&#xff0c;YW343:x:0:0::/home/YW343:/bin/bash 2.将标红的位置修改为用户对应初始UID和GID&#xff1a; YW3…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

【JavaWeb】Docker项目部署

引言 之前学习了Linux操作系统的常见命令&#xff0c;在Linux上安装软件&#xff0c;以及如何在Linux上部署一个单体项目&#xff0c;大多数同学都会有相同的感受&#xff0c;那就是麻烦。 核心体现在三点&#xff1a; 命令太多了&#xff0c;记不住 软件安装包名字复杂&…...