LeetCode-871 最低加油次数
重启力扣每日一题系列!
因为过去两个月里掉粉掉的好严重,我想大抵是因为更新的频率不如上半年了,如果我重启了每日一题系列那岂不是至少是每日一更☝🤓?
也不是每天都更,我有两不更,特难的就不更了,打算去算法岗的小伙伴自己琢磨去;特简单的也不更了,那么简单更出来岂不是拉低我的平均水准;麻烦的不更,太麻烦了费我时间;方便的也不更,直接调库就好了……
这次重启跟之前的也不一样了,之前几乎每一题我都会自己作图,包括动图,这很花时间,通常是从早上做到下午,做完累了休息一下就到晚上了,一天下来光力扣了。
所以这次化简了,指提供思路和C++示例代码,咱来个力扣每日一题极速版。
废话说多了,我们直接看看今天的题目。

这题其实跟昨天的题是同一个系列的,但是做法上面天差地别。
先做个阅读理解,简单来说就是我们一开始有一些汽油,每升汽油可以走一公里,某些公里处有加油站,我们可以加一次油,问我们最少加几次油可以走到目的地。
比较容易想到的是暴力解法,我们直接模拟,每到一个加油站我们都开两个分叉,也就是加油或者不加油,每个能到目的地的分支我们都记录下加了几次油,选着最少的加油数返回即可。
不过这是困难题,想都不用想也可以知道会超时(没试过,说不准呢?)
看看这可怕的数据范围。

不过知道暴力解法之后就是成功的第一步了,我们要做的就是优化暴力解法,这也是正常的解题过程。
因为我们要最少的加油数,所以我们要尽可能的少加油,但是少加油之后错过加油站了怎么办呢?
现实中你会错过她,但是在代码里我们不会再错过了,没有对象咱就new一个嘛。
我们每经过一个加油站,我们都把油搬上车,等到没油了我们再加一次油,因为要尽可能少加油,所以每次我们都加油数最多的那一桶油,这样就不会错过了。
代码中实现就是我们先行驶,能跑多远跑多远,然后把经过的加油站的汽油都先放到一个容器里,因为我们每次要取的是最大的值,所以这个容器我选择优先队列,也就是大顶堆。
如果我们没跑过目的地,那么我们从大顶堆里掏出一个汽油,然后再接着跑,反复循环,直到我们跑到了目的地或者是没油了,一滴都没有了。
具体可以参考下面的代码。
class Solution {
public:int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {priority_queue<int> cache; // 存放沿途的汽油int res = 0; // 加油次数int cur = 0, index = 0; // 当前路程,stations索引(途径加油站个数)while(cur < target && startFuel > 0){ // 不到目的地 && 还有汽油cur += startFuel; // 前进startFuel = 0; // 清零汽油while(index < stations.size() && stations[index][0] <= cur){ // 将经过的汽油记录在大顶堆中cache.push(stations[index][1]);index++;}if(cur < target && !cache.empty()){ // 还没到目的地,那就取一次汽油,取经过的汽油中最多的 startFuel = cache.top(); cache.pop();++res;}}if(cur >= target) return res;return -1;}
};

相关文章:
LeetCode-871 最低加油次数
重启力扣每日一题系列! 因为过去两个月里掉粉掉的好严重,我想大抵是因为更新的频率不如上半年了,如果我重启了每日一题系列那岂不是至少是每日一更☝🤓? 也不是每天都更,我有两不更,特难的就不…...
OpenCV-OCR
文章目录 一、OCR技术的基本原理二、OpenCV在OCR识别中的应用1.图像预处理2.文字区域检测3.OCR识别:4.后处理: 三、OCR识别示例代码四、注意事项 OpenCV-OCR主要涉及使用OpenCV库进行光学字符识别(OCR)的技术。OCR技术可以识别图像…...
Linux卸载mysql
一、查看当前安装mysql情况,查找以前是否装有mysql rpm -qa|grep -i mysql二、停止MySQL服务 三、删除mysql库和文件 查找MySQL库 # 查找命令 find / -name mysql# 显示结果 /var/lib/mysql/var/lib/mysql/mysql/usr/lib64/mysql删除对应的mysql目录 rm -rf /v…...
【大语言模型-论文精读】用于医疗领域摘要任务的大型语言模型评估综述
【大语言模型-论文精读】用于医疗领域摘要任务的大型语言模型评估综述 论文信息: 用于医疗领域摘要任务的大型语言模型评估:一篇叙述性综述, 文章是由 Emma Croxford , Yanjun Gao 博士 , Nicholas Pellegrino , Karen K. Wong 等人近期合作…...
图吧工具箱
图吧工具箱202309绿色版自动解压程序R2.exe,永久有效 链接:https://pan.baidu.com/s/1M6TI7Git8bXOzZX_qZ3LJw?pwdzked 提取码:zked...
vue2 + View design 使用inputNumber设置默认值为undefined但展示数据为1且表单校验不通过的原因
文章目录 一、背景二、操作步骤1.复现前的准备工作(1)vue版本和view design 版本(2)创建一个组件(组件中根据类型渲染不同的组件)(3)在list.vue页面中引入组件,传入配置&…...
【SpringSecurity】基本流程
【中文文档: Spring Security 中文文档 :: Spring Security Reference】 【英文文档:Spring Security】 以下内容只是记录springsecurity最简单的一种验证流程,所有配置基本都是默认的配置。 引入依赖 <dependency><groupId>org.springf…...
算法-汉诺塔问题(Hanoi tower)
介绍 汉诺塔是源于印度的一个古老传说的小游戏,简单来说就是有三根柱子,开始的时候,第一根柱子上圆盘由大到小,自下往上排列。这个小游戏要实现的目的呢,就是要把第一根柱子上的圆盘移到第三根的柱子上去;…...
HarmonyOS鸿蒙 Next 实现协调布局效果
HarmonyOS鸿蒙 Next 实现协调布局效果 假期愉快! 最近大A 的涨势实在是红的让人晕头转向,不知道各位收益如何,这会是在路上,还是已经到目的地了? 言归正传,最近有些忙,关于鸿蒙的实践系列有些脱节了,…...
【自然语言处理】(1) --语言转换方法
文章目录 语言转换方法一、统计语言模型1. 词向量转换2. 统计模型问题 二、神经语言模型1. 词向量化2. 维度灾难3. 解决维度灾难4. embedding词嵌入5. Word2Vec技术5.1 连续词袋模型(CBOW)5.2 跳字模型(Skip-gram) 总结 语言转换方…...
叉车防撞系统方案,引领安全作业新时代
在现代工业的舞台上,叉车如同忙碌的“搬运工”,在仓储和制造环境中发挥着不可或缺的作用。然而,随着叉车使用频率的不断攀升,安全事故也如影随形,给企业带来经济损失的同时,更严重威胁着操作人员的生命安全…...
Nginx的核心架构和设计原理
Nginx 是一个免费的、开源的、高性能 Http 服务器和反向代理。Nginx 的架构设计是为了提供高性能、稳定性和可扩展性。 Nginx 的主要架构组件和工作原理: 1、Master 进程:Nginx 的运行始于一个 master 进程,它负责管理所有的工作进程。mast…...
leetcode35--搜索插入位置--二分查找刷题
搜索插入位置 一共会出现下面四种情况: 目标值在数组所有元素之前 目标值等于数组中某一个元素 目标值插入数组中的位置 目标值在数组所有元素之后 首先在二分查找的代码之前处理掉目标值在数组所有元素之前和之后的情况如果目标值在数组中的某个位置,…...
Django对接支付宝沙箱环境(2024年9月新测有效)
1、申请沙箱环境 #需要填一些个人信息 https://opendocs.alipay.com/ 2、使用支付宝登入,并进入控制台,进入开发者工具推荐-->沙箱 3、获取基本信息 主要是APPID,和支付宝网关地址 4、生成应用私钥和应用公钥和支付宝公钥 上面的接口加签方式选择…...
【MySQL】-- 库的操作
文章目录 1. 查看数据库1.1 语法 2. 创建数据库2.1 语法2.2 示例2.2.1 创建一个名为java114的数据库2.2.2 创建数据库java114,如果数据库不存在则创建2.2.3 查看警告信息 3. 字符集编码和校验(排序)规则3.1 查看数据库支持的字符集编码3.2 查…...
linux桌面软件(wps)内嵌到主窗口后的关闭问题
程序测试环境是:slackware系统,属于linux系统,有桌面(Xface Session)。系统镜像是:slackware64-15.0-install-dvd.iso。qt、c代码实现。 问题描述:延续上一篇文章,将wps软件窗口内嵌…...
WindowsTerminal 美化-壁纸随机更换
目录 一. 相关网址二. 壁纸随机更换思路三. 指定 WindowsTermina 壁纸路径四. 编写脚本,随机替换壁纸4.1 powershell脚本4.2 .bat批处理脚本 四. 配置定时任务,添加触发器五. 效果 一. 相关网址 官方下载 Windows Terminal 官方Github微软商店 美化 Oh …...
iOS 多次获取图片主题色不一样
一个需求中,要求获取图片的主题色 代码如下 -(void)kk_getImage:(UIImage *)image fetchthemeColor:(void(^)(UIColor *color))callBack {dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{// 第一步 先把图片缩小 加快计算速度.…...
UE5 武器IK瞄准系统
创建空项目 创建基础蓝图类My_GameMode,My_HUD,My_PlayChar,My_PlayController 项目设置地图模式 近裁平面 0.1 My_PlayChar蓝图中添加摄像机,角色骨骼网格体,武器骨骼网格体 编辑角色骨骼,预览控制器使用特定动画,动画选择ANM_ark-47-Idle hand_r 添加插槽WeaponMes…...
①EtherCAT转ModbusTCP, EtherCAT/Ethernet/IP/Profinet/ModbusTCP协议互转工业串口网关
EtherCAT/Ethernet/IP/Profinet/ModbusTCP协议互转工业串口网关https://item.taobao.com/item.htm?ftt&id822721028899 协议转换通信网关 EtherCAT 转 ModbusTCP GW系列型号 MS-GW15 简介 MS-GW15 是 EtherCAT 和 Modbus TCP 协议转换网关,为用户提供一种 …...
终极指南:如何使用Docker Stacks与Git Hooks实现自动化代码质量检查
终极指南:如何使用Docker Stacks与Git Hooks实现自动化代码质量检查 【免费下载链接】docker-stacks Ready-to-run Docker images containing Jupyter applications 项目地址: https://gitcode.com/gh_mirrors/do/docker-stacks Docker Stacks是一个提供现成…...
UniApp项目实战:用UTS插件实现安卓后台保活(附完整Service配置与权限处理)
UniApp安卓后台保活实战:UTS插件与Service优化全解析 在移动应用开发中,后台任务保活一直是开发者面临的棘手问题。想象一下:你的UniApp应用需要持续获取用户位置、实时推送消息或播放音乐,却频繁被系统清理,用户体验直…...
互联网大厂最全 Java 面试八股文题库
纵观几年来的 Java 面试题,你会发现每家都差不多。你仔细观察就会发现,HashMap 的出现几率未免也太高了吧!连考察的知识点都一样,什么 hash 碰撞啊,并发问题啊!再比如 JVM,无外乎考内存结构&…...
STM32F103RCT6小车调试实录:搞定TCRT5000循迹与TB6612FNG调速的5个常见坑
STM32F103RCT6小车调试实战:从TCRT5000循迹到TB6612FNG调速的深度排错指南 实验室里,当你看着自己组装的STM32智能小车在黑色轨迹线上歪歪扭扭地行驶,或是电机转速时快时慢不受控制时,那种挫败感我太熟悉了。这不是一篇教你如何从…...
从‘知识冲突’到‘对齐’:图解ProGrad如何让CLIP微调既专又通
ProGrad:用向量几何重新思考多模态模型的微调艺术 想象一下,你正在训练一位精通多国语言的老教授学习一门新方言。如果完全放任他自由发挥,可能会丢失原有的语言体系;如果限制太多,又无法适应新语境。这正是CLIP等预训…...
Apollo配置中心:从基础概念到实战应用全解析
1. Apollo配置中心初探:为什么我们需要它? 想象一下你正在开发一个电商系统,数据库连接地址、支付接口密钥、商品库存阈值等配置信息散落在20个不同的properties文件里。每次修改配置都需要重新打包部署,半夜三点被叫起来改生产环…...
轻量部署开源网络性能测试工具:从环境搭建到性能调优全指南
轻量部署开源网络性能测试工具:从环境搭建到性能调优全指南 【免费下载链接】speedtest 项目地址: https://gitcode.com/gh_mirrors/spe/speedtest 在网络运维与开发过程中,准确掌握网络带宽性能是保障服务质量的关键。本文将介绍如何使用开源速…...
别再只建桶了!华为云OBS的5个高阶配置,让你的存储成本直降30%
别再只建桶了!华为云OBS的5个高阶配置,让你的存储成本直降30% 当你的业务数据量突破TB级时,存储成本就会像野马一样失控。去年我们团队就经历过这样的教训——每月OBS账单突然暴涨40%,排查后发现是数百GB的过期日志仍按标准存储计…...
Mirage Flow与Python爬虫结合:智能数据采集与分析实战
Mirage Flow与Python爬虫结合:智能数据采集与分析实战 1. 引言 你有没有遇到过这样的情况:需要从大量网站采集数据,但传统爬虫要么被封IP,要么无法处理复杂的页面结构,要么采集回来的数据杂乱无章需要大量清洗&#…...
VibeVoice与Vue3前端整合:浏览器端语音合成方案
VibeVoice与Vue3前端整合:浏览器端语音合成方案 1. 为什么要在浏览器里直接合成语音 你有没有遇到过这样的场景:在做一个在线教育应用时,想让系统自动朗读课文,但每次都要把文字发到后端服务器,等几秒钟再把音频文件…...
