当前位置:网站首页>871. Minimum Number of Refueling Stops
871. Minimum Number of Refueling Stops
2022-07-05 11:23:00 【soO_007】
题目:
A car travels from a starting position to a destination which is target
miles east of the starting position.
There are gas stations along the way. The gas stations are represented as an array stations
where stations[i] = [positioni, fueli]
indicates that the ith
gas station is positioni
miles east of the starting position and has fueli
liters of gas.
The car starts with an infinite tank of gas, which initially has startFuel
liters of fuel in it. It uses one liter of gas per one mile that it drives. When the car reaches a gas station, it may stop and refuel, transferring all the gas from the station into the car.
Return the minimum number of refueling stops the car must make in order to reach its destination. If it cannot reach the destination, return -1
.
Note that if the car reaches a gas station with 0
fuel left, the car can still refuel there. If the car reaches the destination with 0
fuel left, it is still considered to have arrived.
Example 1:
Input: target = 1, startFuel = 1, stations = [] Output: 0 Explanation: We can reach the target without refueling.
Example 2:
Input: target = 100, startFuel = 1, stations = [[10,100]] Output: -1 Explanation: We can not reach the target (or even the first gas station).
Example 3:
Input: target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]] Output: 2 Explanation: We start with 10 liters of fuel. We drive to position 10, expending 10 liters of fuel. We refuel from 0 liters to 60 liters of gas. Then, we drive from position 10 to position 60 (expending 50 liters of fuel), and refuel from 10 liters to 50 liters of gas. We then drive to and reach the target. We made 2 refueling stops along the way, so we return 2.
Constraints:
1 <= target, startFuel <= 109
0 <= stations.length <= 500
0 <= positioni <= positioni+1 < target
1 <= fueli < 109
思路1:
第一反应是用递归来做,f[i][j]表示经过第 i 个加油站后,加油 j 次能够到达的最大距离,最后只需要找到最小的 j 并且f[i][j]大于等于target即可。状态转移方程中f[i][j]可以从三个地方来:1)f[i][j - 1],代表经过了当前车站,但是不在当前车站加油;2)f[i - 1][j],表示到达了第i - 1即前一个车站,并且加了j次油,即上个车站没加油;3)f[i - 1][j - 1] + stations[i - 1][1],即经过了第i - 1个车站,并且在上个车站加了油,当然这里有条件就是f[i - 1][j - 1]的最大距离必须要比stations[i - 1][0]大,不然无法到达上个车站。初始化我们用 n = stations.size() + 1,即f[i][j]当 j 等于0 时表示f[i][0]都是没加过油的,那么它们的值应该为startFuel,至于f[0][j],不需要初始化,因为j一定小于等i,即加油次数不能比路过的车站多。
代码1:
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
int n = stations.size() + 1;
vector<vector<long>> f(n, vector<long>(n));
for (int i = 0; i < n; i++) {
f[i][0] = startFuel;
}
for (int i = 1; i < n; i++) {
for (int j = 1; j <= i; j++) {
if (f[i - 1][j - 1] >= stations[i - 1][0]) {
f[i][j] = f[i - 1][j - 1] + stations[i - 1][1];
}
f[i][j] = max({f[i - 1][j], f[i][j - 1], f[i][j]});
}
}
for (int j = 0; j < n; j++) {
for (int i = 0; i < n; i++) {
if (f[i][j] >= target)
return j;
}
}
return -1;
}
};
思路2:
从本质上来看,题目要求我们需要在最少的加油次数中加最多的油,即每次加油都加能够加的最多的油。但是我们每次路过车站,其实只有当前车站可以选择,那么怎么构成选项呢?答案是每次路过车站先不加油,把能够加的油记录进一个优先队列,等到需要加油的时候我们再取出来为自己加油。这里优先队列是为了管理最大值,使我们能够随时取出来的都是最多的油。首先我们能够到达的最大距离dist就是startFuel,之后判断dist和target,一旦dist大于等于target即可结束。循环中,每次我们路过车站,如果当前dist能够到达车站,那我们就先不加油,而是把油加入优先队列;如果不能到达车站,那么就加油,如果优先队列已经无油可加,证明我们不能到达target,直接返回-1;如果优先队列有油,那么就拿出最大的油,加给dist,同时更新加油次数即可。
代码2:
class Solution {
public:
int minRefuelStops(int target, int startFuel, vector<vector<int>>& stations) {
priority_queue<int> q;
int dist = startFuel, count = 0;
int i = 0;
while (dist < target) {
if (i < stations.size() && dist >= stations[i][0]) { //能到车站说明油暂时是够的
q.push(stations[i][1]); //先不加油,存起来
i++;
} else {
if (q.size()) { //有油可加
dist += q.top(); //加油
q.pop();
count++; //更新次数
} else { //无油可加,无法到达target
return -1;
}
}
}
return count;
}
};
边栏推荐
- Bracket matching problem (STL)
- 2022 mobile crane driver examination question bank and simulation examination
- Cron表达式(七子表达式)
- Question and answer 45: application of performance probe monitoring principle node JS probe
- Detailed explanation of DDR4 hardware schematic design
- String
- FreeRTOS 中 RISC-V-Qemu-virt_GCC 的调度时机
- uniapp
- Summary of websites of app stores / APP markets
- 【广告系统】增量训练 & 特征准入/特征淘汰
猜你喜欢
go语言学习笔记-分析第一个程序
IPv6与IPv4的区别 网信办等三部推进IPv6规模部署
如何让全彩LED显示屏更加节能环保
高校毕业求职难?“百日千万”网络招聘活动解决你的难题
[JS] extract the scores in the string, calculate the average score after summarizing, compare with each score, and output
Advanced technology management - what is the physical, mental and mental strength of managers
修复动漫1K变8K
数据库三大范式
Basics - rest style development
2022 Pengcheng cup Web
随机推荐
Variables///
[Oracle] use DataGrid to connect to Oracle Database
IPv6与IPv4的区别 网信办等三部推进IPv6规模部署
购买小间距LED显示屏的三个建议
Ziguang zhanrui's first 5g R17 IOT NTN satellite in the world has been measured on the Internet of things
2022 Pengcheng cup Web
Function///
uboot的启动流程:
Golang application topic - channel
Msfconsole command encyclopedia and instructions
MySQL giant pit: update updates should be judged with caution by affecting the number of rows!!!
Intelligent metal detector based on openharmony
Technology sharing | common interface protocol analysis
R3Live系列学习(四)R2Live源码阅读(2)
居家办公那些事|社区征文
Basic testing process of CSDN Software Testing Introduction
如何让全彩LED显示屏更加节能环保
跨境电商是啥意思?主要是做什么的?业务模式有哪些?
【全网首发】(大表小技巧)有时候 2 小时的 SQL 操作,可能只要 1 分钟
Sklearn model sorting