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

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 最低加油次数

重启力扣每日一题系列&#xff01; 因为过去两个月里掉粉掉的好严重&#xff0c;我想大抵是因为更新的频率不如上半年了&#xff0c;如果我重启了每日一题系列那岂不是至少是每日一更☝&#x1f913;&#xff1f; 也不是每天都更&#xff0c;我有两不更&#xff0c;特难的就不…...

OpenCV-OCR

文章目录 一、OCR技术的基本原理二、OpenCV在OCR识别中的应用1.图像预处理2.文字区域检测3.OCR识别&#xff1a;4.后处理&#xff1a; 三、OCR识别示例代码四、注意事项 OpenCV-OCR主要涉及使用OpenCV库进行光学字符识别&#xff08;OCR&#xff09;的技术。OCR技术可以识别图像…...

Linux卸载mysql

一、查看当前安装mysql情况&#xff0c;查找以前是否装有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…...

【大语言模型-论文精读】用于医疗领域摘要任务的大型语言模型评估综述

【大语言模型-论文精读】用于医疗领域摘要任务的大型语言模型评估综述 论文信息&#xff1a; 用于医疗领域摘要任务的大型语言模型评估&#xff1a;一篇叙述性综述&#xff0c; 文章是由 Emma Croxford , Yanjun Gao 博士 , Nicholas Pellegrino , Karen K. Wong 等人近期合作…...

图吧工具箱

图吧工具箱202309绿色版自动解压程序R2.exe&#xff0c;永久有效 链接&#xff1a;https://pan.baidu.com/s/1M6TI7Git8bXOzZX_qZ3LJw?pwdzked 提取码&#xff1a;zked...

vue2 + View design 使用inputNumber设置默认值为undefined但展示数据为1且表单校验不通过的原因

文章目录 一、背景二、操作步骤1.复现前的准备工作&#xff08;1&#xff09;vue版本和view design 版本&#xff08;2&#xff09;创建一个组件&#xff08;组件中根据类型渲染不同的组件&#xff09;&#xff08;3&#xff09;在list.vue页面中引入组件&#xff0c;传入配置&…...

【SpringSecurity】基本流程

【中文文档: Spring Security 中文文档 :: Spring Security Reference】 【英文文档&#xff1a;Spring Security】 以下内容只是记录springsecurity最简单的一种验证流程&#xff0c;所有配置基本都是默认的配置。 引入依赖 <dependency><groupId>org.springf…...

算法-汉诺塔问题(Hanoi tower)

介绍 汉诺塔是源于印度的一个古老传说的小游戏&#xff0c;简单来说就是有三根柱子&#xff0c;开始的时候&#xff0c;第一根柱子上圆盘由大到小&#xff0c;自下往上排列。这个小游戏要实现的目的呢&#xff0c;就是要把第一根柱子上的圆盘移到第三根的柱子上去&#xff1b;…...

HarmonyOS鸿蒙 Next 实现协调布局效果

HarmonyOS鸿蒙 Next 实现协调布局效果 ​ 假期愉快! 最近大A 的涨势实在是红的让人晕头转向&#xff0c;不知道各位收益如何&#xff0c;这会是在路上&#xff0c;还是已经到目的地了? 言归正传&#xff0c;最近有些忙&#xff0c;关于鸿蒙的实践系列有些脱节了&#xff0c;…...

【自然语言处理】(1) --语言转换方法

文章目录 语言转换方法一、统计语言模型1. 词向量转换2. 统计模型问题 二、神经语言模型1. 词向量化2. 维度灾难3. 解决维度灾难4. embedding词嵌入5. Word2Vec技术5.1 连续词袋模型&#xff08;CBOW&#xff09;5.2 跳字模型&#xff08;Skip-gram&#xff09; 总结 语言转换方…...

叉车防撞系统方案,引领安全作业新时代

在现代工业的舞台上&#xff0c;叉车如同忙碌的“搬运工”&#xff0c;在仓储和制造环境中发挥着不可或缺的作用。然而&#xff0c;随着叉车使用频率的不断攀升&#xff0c;安全事故也如影随形&#xff0c;给企业带来经济损失的同时&#xff0c;更严重威胁着操作人员的生命安全…...

Nginx的核心架构和设计原理

Nginx 是一个免费的、开源的、高性能 Http 服务器和反向代理。Nginx 的架构设计是为了提供高性能、稳定性和可扩展性。 Nginx 的主要架构组件和工作原理&#xff1a; 1、Master 进程&#xff1a;Nginx 的运行始于一个 master 进程&#xff0c;它负责管理所有的工作进程。mast…...

leetcode35--搜索插入位置--二分查找刷题

搜索插入位置 一共会出现下面四种情况&#xff1a; 目标值在数组所有元素之前 目标值等于数组中某一个元素 目标值插入数组中的位置 目标值在数组所有元素之后 首先在二分查找的代码之前处理掉目标值在数组所有元素之前和之后的情况如果目标值在数组中的某个位置&#xff0c…...

Django对接支付宝沙箱环境(2024年9月新测有效)

1、申请沙箱环境 #需要填一些个人信息 https://opendocs.alipay.com/ 2、使用支付宝登入&#xff0c;并进入控制台&#xff0c;进入开发者工具推荐-->沙箱 3、获取基本信息 主要是APPID,和支付宝网关地址 4、生成应用私钥和应用公钥和支付宝公钥 上面的接口加签方式选择…...

【MySQL】-- 库的操作

文章目录 1. 查看数据库1.1 语法 2. 创建数据库2.1 语法2.2 示例2.2.1 创建一个名为java114的数据库2.2.2 创建数据库java114&#xff0c;如果数据库不存在则创建2.2.3 查看警告信息 3. 字符集编码和校验&#xff08;排序&#xff09;规则3.1 查看数据库支持的字符集编码3.2 查…...

linux桌面软件(wps)内嵌到主窗口后的关闭问题

程序测试环境是&#xff1a;slackware系统&#xff0c;属于linux系统&#xff0c;有桌面&#xff08;Xface Session&#xff09;。系统镜像是&#xff1a;slackware64-15.0-install-dvd.iso。qt、c代码实现。 问题描述&#xff1a;延续上一篇文章&#xff0c;将wps软件窗口内嵌…...

WindowsTerminal 美化-壁纸随机更换

目录 一. 相关网址二. 壁纸随机更换思路三. 指定 WindowsTermina 壁纸路径四. 编写脚本&#xff0c;随机替换壁纸4.1 powershell脚本4.2 .bat批处理脚本 四. 配置定时任务&#xff0c;添加触发器五. 效果 一. 相关网址 官方下载 Windows Terminal 官方Github微软商店 美化 Oh …...

iOS 多次获取图片主题色不一样

一个需求中&#xff0c;要求获取图片的主题色 代码如下 -(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 协议转换网关&#xff0c;为用户提供一种 …...

AIGC内容创作流水线:Qwen3-ASR-0.6B赋能语音素材自动化文本化

AIGC内容创作流水线&#xff1a;Qwen3-ASR-0.6B赋能语音素材自动化文本化 你有没有过这样的经历&#xff1f;录完一段精彩的课程讲解、一次深度的访谈对话&#xff0c;或者一段灵光乍现的语音随笔&#xff0c;看着长达几十分钟的音频文件&#xff0c;一想到要把它整理成文字稿…...

P1061 Jam 的计数法【洛谷算法习题】

P1061 Jam 的计数法 网页链接 P1061 Jam 的计数法 题目描述 Jam 是个喜欢标新立异的科学怪人。他不使用阿拉伯数字计数&#xff0c;而是使用小写英文字母计数&#xff0c;他觉得这样做&#xff0c;会使世界更加丰富多彩。 在他的计数法中&#xff0c;每个数字的位数都是相…...

cat-catch:构建智能化媒体资源捕获的浏览器扩展解决方案

cat-catch&#xff1a;构建智能化媒体资源捕获的浏览器扩展解决方案 【免费下载链接】cat-catch 猫抓 chrome资源嗅探扩展 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch cat-catch是一款专注于网页媒体资源智能捕获的浏览器扩展工具&#xff0c;通过深度…...

Carla仿真实战:3种高效定位车辆生成点的方法(附代码示例)

Carla仿真实战&#xff1a;3种高效定位车辆生成点的方法&#xff08;附代码示例&#xff09; 在自动驾驶仿真开发中&#xff0c;精确控制车辆生成位置是构建测试场景的基础需求。许多开发者在使用Carla时都遇到过车辆"乱跑"的问题——明明指定了坐标&#xff0c;生成…...

别再当黑匣子用了!手把手教你用FastMCP的tool()、resource()和prompt()装饰器,从源码理解到实战避坑

FastMCP装饰器深度解析&#xff1a;从tool()到prompt()的实战进阶指南 1. 为什么需要理解装饰器内部机制&#xff1f; 在Python开发领域&#xff0c;装饰器(Decorator)是一种强大的元编程工具&#xff0c;而FastMCP框架中的tool()、resource()和prompt()装饰器更是将这一理念发…...

实测MinerU 2.5-1.2B:复杂排版PDF提取效果惊艳,小白也能上手

实测MinerU 2.5-1.2B&#xff1a;复杂排版PDF提取效果惊艳&#xff0c;小白也能上手 1. 引言&#xff1a;为什么需要专业的PDF提取工具 1.1 日常工作中的PDF处理痛点 作为一名经常需要处理学术文献的研究员&#xff0c;我深知PDF文档带来的困扰。上周我尝试用常规工具提取一…...

FastAPI分块上传存储:对象存储集成完整指南

FastAPI分块上传存储&#xff1a;对象存储集成完整指南 【免费下载链接】fastapi FastAPI framework, high performance, easy to learn, fast to code, ready for production 项目地址: https://gitcode.com/GitHub_Trending/fa/fastapi 想要在FastAPI应用中实现大文件…...

libusb+zadig实战:Windows USB设备驱动快速配置指南

1. 为什么需要libusb和zadig组合&#xff1f; 如果你在Windows系统上开发过USB设备应用&#xff0c;大概率遇到过这样的场景&#xff1a;明明代码逻辑没问题&#xff0c;设备也连接正常&#xff0c;但程序就是无法正常访问USB设备。这种情况往往是因为Windows系统的安全机制在…...

构建学术文献自由:caj2pdf开源转换工具深度解析

构建学术文献自由&#xff1a;caj2pdf开源转换工具深度解析 【免费下载链接】caj2pdf Convert CAJ (China Academic Journals) files to PDF. 转换中国知网 CAJ 格式文献为 PDF。佛系转换&#xff0c;成功与否&#xff0c;皆是玄学。 项目地址: https://gitcode.com/gh_mirro…...

Qwen3-ASR-1.7B与Python爬虫结合实战:音频数据采集与智能分析流水线

Qwen3-ASR-1.7B与Python爬虫结合实战&#xff1a;音频数据采集与智能分析流水线 1. 为什么需要这套音频分析流水线 最近在帮一家做社交媒体舆情监控的团队搭建分析系统时&#xff0c;他们提出了一个很实际的问题&#xff1a;视频平台里大量用户评论是以语音形式存在的&#x…...