力扣(leetcode)每日一题 871 最低加油次数 | 贪心
871. 最低加油次数
题干
汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。
沿途有加油站,用数组 stations 表示。其中 stations[i] = [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处,并且有 fueli 升汽油。
假设汽车油箱的容量是无限的,其中最初有 startFuel 升燃料。它每行驶 1 英里就会用掉 1 升汽油。当汽车到达加油站时,它可能停下来加油,将所有汽油从加油站转移到汽车中。
为了到达目的地,汽车所必要的最低加油次数是多少?如果无法到达目的地,则返回 -1 。
注意:如果汽车到达加油站时剩余燃料为 0,它仍然可以在那里加油。如果汽车到达目的地时剩余燃料为 0,仍然认为它已经到达目的地。
示例 1:
**输入:**target = 1, startFuel = 1, stations = []
**输出:**0
**解释:**可以在不加油的情况下到达目的地。
示例 2:
**输入:**target = 100, startFuel = 1, stations = [[10,100]]
输出:-1
**解释:**无法抵达目的地,甚至无法到达第一个加油站。
示例 3:
**输入:**target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
**输出:**2
解释:
出发时有 10 升燃料。
开车来到距起点 10 英里处的加油站,消耗 10 升燃料。将汽油从 0 升加到 60 升。
然后,从 10 英里处的加油站开到 60 英里处的加油站(消耗 50 升燃料),
并将汽油从 10 升加到 50 升。然后开车抵达目的地。
沿途在两个加油站停靠,所以返回 2 。
题解
先把路过的加油站的油收集起来。当达到i加油站时候,发现不够。再弹出之前加油站收集的油(使用优先级队列),count数量+1。
然后经过所有加油站后,油依旧不够达到终点,再使用while弹出之前收集的油count数量+1
public static int minRefuelStops(int target, int startFuel, int[][] stations) { int total = startFuel; int count = 0; PriorityQueue<Integer> heap = new PriorityQueue<>((v1, v2) -> { return v2 - v1; }); for (int i = 0; i < stations.length; i++) { while (total - stations[i][0] < 0) { if (heap.isEmpty()) { return -1; } Integer poll = heap.poll(); count++; total += poll; if (target <= total) { return count; } } heap.add(stations[i][1]); } // 这里已经走到最后一战了 while (target > total) { if (heap.isEmpty()) { return -1; } Integer poll = heap.poll(); count++; total += poll; } return count;
}
总结
和滑动窗口的写法是一样的,但是这是属于贪心算法。滑动窗口也属于贪心这一类问题。
这个题目还是比较简单的,如果因为看到hard而没有做出来就太可惜了
官方题解用了一个while解决问题,本质是一样的,是多引入一个加油点 位置为终点,补充为0
相关文章:
力扣(leetcode)每日一题 871 最低加油次数 | 贪心
871. 最低加油次数 题干 汽车从起点出发驶向目的地,该目的地位于出发位置东面 target 英里处。 沿途有加油站,用数组 stations 表示。其中 stations[i] [positioni, fueli] 表示第 i 个加油站位于出发位置东面 positioni 英里处,并且有 f…...
ppt压缩文件怎么压缩?压缩PPT文件的多种压缩方法
ppt压缩文件怎么压缩?当文件体积过大时,分享和传输就会变得困难。许多电子邮件服务对附件的大小有限制,而在网络环境不佳时,上传和下载大文件可能耗时较长。此外,在不同设备上播放时,较大的PPT文件还可能导…...
2024.10月11日--- SpringMVC拦截器
拦截器 1 回顾过滤器: Servlet规范中的三大接口:Servlet接口,Filter接口、Listener接口。 过滤器接口,是Servlet2.3版本以来,定义的一种小型的,可插拔的Web组件,可以用来拦截和处理Servlet容…...
uniapp 锁屏显示插件 Ba-LockShow(可让vue直接具备锁屏显示能力)
简介 Ba-LockShow 是一款可以直接使uniapp的vue界面在锁屏页展示的插件。 支持使vue直接具备锁屏显示能力支持设置锁屏显示和不显示支持唤醒屏幕 截图展示(仅参考) 支持定制、本地包、源码等,有建议和需要,请点击文章结尾“Unia…...
CSS计数器
CSS 中的计数器类似于变量,可以实现简单的计数功能,并将结果显示在页面上,在早期的网站上应用比较广泛。要实现计数器需要用到以下几个属性: counter-reset:创建或者重置计数器;counter-increment…...
嵌入式Linux:信号集
目录 1、信号集初始化 2、向信号集中添加或删除信号 3、测试信号是否在信号集中 在 Linux 系统中,处理多个信号时常用到一种数据结构:信号集(sigset_t)。信号集允许我们将多个信号组织在一起,以便在系统调用中传递和…...
Linux 外设驱动 应用 1 IO口输出
从这里开始外设驱动介绍,这里使用的IMX8的芯片作为驱动介绍 开发流程: 修改设备树,配置 GPIO1_IO07 为 GPIO 输出。使用 sysfs 接口或编写驱动程序控制 GPIO 引脚。编译并测试。 这里假设设备树,已经配置好了。不在论述这个问题…...
基于SpringBoot+Vue+MySQL的留守儿童爱心网站
系统展示 用户前台界面 管理员后台界面 系统背景 随着现代社会的发展,留守儿童问题日益受到关注。传统的纸质管理方式已经无法满足现代人们对留守儿童爱心信息的需求。为了提高留守儿童爱心信息的管理效率,增加用户信息的安全性,并方便及时反…...
调用第三方接口
目录 一、分析给出的接口文档 二、请求体格式之间的区别 三、示例代码 一、分析给出的接口文档 一般的接口文档包括以下几大部分: 1、请求URL:http://{ip}:{port}/api/ec/dev/message/sendCustomMessageSingle 2、请求方式:POST、GET等 3、…...
JAVA 多线程入门例子:CountDownLatch
首先确定线程数量。如果数据集合的大小小于50,就只使用一个线程;否则使用5个线程。计算每个线程平均处理的数据数量sizePerThread以及余数remainder。在划分数据子集合时,对于每个线程的处理范围进行计算。如果有余数,就将余数依次…...
k8s jenkins 动态创建slave
k8s jenkins 动态创建slave 简述使用jenkins动态slave的优势:配置jenkins动态slave配置 Pod Template配置容器模板挂载卷 测试 简述 持续构建与发布是我们日常工作中必不可少的一个步骤,目前大多公司都采用 Jenkins 集群来搭建符合需求的 CI/CD 流程&am…...
MVS海康工业相机达不到标称最大帧率
文章目录 一、相机参数设置1、取消相机帧率限制2、修改相机图像格式3、调整相机曝光时间4、检查相机数据包大小(网口相机特有参数)5、 恢复相机默认参数6、 相机 ADC 输出位深调整 二、系统环境设置1、 网口相机设置2、 USB 相机设置 一、相机参数设置 …...
数据结构:用双栈实现一个队列
要用两个栈实现一个队列,可以利用“栈”的后进先出 (LIFO) 特性来模拟“队列”的先进先出 (FIFO) 操作。具体做法是使用两个栈:一个作为入栈栈,另一个作为出栈栈。 算法步骤 入队操作(enqueue): 将元素压…...
QScroller Class
Header:#include < QScroller > qmake:QT += widgets Since:Qt 5.0 Inherits:QObject This class was introduced in Qt 5.0. Public Types enum Input {InputPress, InputMove, InputRelease } enum ScrollerGestureType {TouchGesture, LeftMouseButtonGesture,…...
React高阶组件详解
React高阶组件(HOC)详解 定义 React高阶组件(HOC)是一个函数,该函数接受一个组件作为参数并返回一个新的组件。高阶组件本身不是一个组件,而是一个函数,它利用React的组合特性,对传入…...
TextView把其它控件挤出屏幕的处理办法
1.如果TextView后面的控件是紧挨着TextView的,可以给TextView添加maxWidth限制其最大长度 上有问题的布局代码 <?xml version"1.0" encoding"utf-8"?> <layout xmlns:android"http://schemas.android.com/apk/res/android&qu…...
长度为 K 的重复字符子串数目
长度为 K 的重复字符子串 给你一个由小写字母组成的长度为n的字符串 S ,找出所有长度为 k 且包含重复字符的子串,请你返回全部满足要求的子串的数目。 数据范围: 2≤k≤400 , 5≤n≤900 进阶: 时间复杂度O(n),空间复杂…...
html+css+js实现轮播图
实现效果: HTML部分 <div class"carousel"><div class"carousel-wrapper"><img src"./image/1.png" alt""></div><ul class"carousel-indictor"><li class"active"…...
Boost集成模型异同
一、常见Boost集成模型 AdaBoost、GBDT和XGBoost都是集成学习中的提升(Boosting)算法,它们通过组合多个弱学习器来构建一个强学习器。从经验上来说,XGBoost是诸多竞赛的大杀器,在实际业务工作中可能需要用到集成模型的…...
【系统架构设计师】案例专题四:嵌入式系统考点梳理
更多内容请见: 备考系统架构设计师-核心总结目录 摘要:本文主要梳理系统架构设计师 - 嵌入式系统 案例考点 ,主要包括嵌入式相关概念、软件和硬件可靠性、冗余技术、软件容错、集群技术、负载均衡、可维护性的评价指标、软件维护的分类等。 文章目录 一、相关概念二、软件可…...
零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?
一、核心优势:专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发,是一款收费低廉但功能全面的Windows NAS工具,主打“无学习成本部署” 。与其他NAS软件相比,其优势在于: 无需硬件改造:将任意W…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
Go 语言接口详解
Go 语言接口详解 核心概念 接口定义 在 Go 语言中,接口是一种抽象类型,它定义了一组方法的集合: // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的: // 矩形结构体…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
srs linux
下载编译运行 git clone https:///ossrs/srs.git ./configure --h265on make 编译完成后即可启动SRS # 启动 ./objs/srs -c conf/srs.conf # 查看日志 tail -n 30 -f ./objs/srs.log 开放端口 默认RTMP接收推流端口是1935,SRS管理页面端口是8080,可…...
【AI学习】三、AI算法中的向量
在人工智能(AI)算法中,向量(Vector)是一种将现实世界中的数据(如图像、文本、音频等)转化为计算机可处理的数值型特征表示的工具。它是连接人类认知(如语义、视觉特征)与…...
BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践
6月5日,2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席,并作《智能体在安全领域的应用实践》主题演讲,分享了在智能体在安全领域的突破性实践。他指出,百度通过将安全能力…...
9-Oracle 23 ai Vector Search 特性 知识准备
很多小伙伴是不是参加了 免费认证课程(限时至2025/5/15) Oracle AI Vector Search 1Z0-184-25考试,都顺利拿到certified了没。 各行各业的AI 大模型的到来,传统的数据库中的SQL还能不能打,结构化和非结构的话数据如何和…...
SpringAI实战:ChatModel智能对话全解
一、引言:Spring AI 与 Chat Model 的核心价值 🚀 在 Java 生态中集成大模型能力,Spring AI 提供了高效的解决方案 🤖。其中 Chat Model 作为核心交互组件,通过标准化接口简化了与大语言模型(LLM࿰…...
