当前位置:网站首页>871. Minimum Number of Refueling Stops
871. Minimum Number of Refueling Stops
2022-07-05 11:27:00 【soO_ 007】
subject :
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
Ideas 1:
The first reaction is to do it with recursion ,f[i][j] It means that after the second i After a gas station , come on. j The maximum distance that can be reached , Finally, you only need to find the smallest j also f[i][j] Greater than or equal to target that will do . In the state transition equation f[i][j] You can come from three places :1)f[i][j - 1], The representative passed the current station , But don't refuel at the current station ;2)f[i - 1][j], It means reaching the i - 1 That is, the previous station , And added j Secondary oil , That is, there was no refueling at the last station ;3)f[i - 1][j - 1] + stations[i - 1][1], That is, after the i - 1 A station , And added oil at the last station , Of course, the condition here is f[i - 1][j - 1] The maximum distance of must be greater than stations[i - 1][0] Big , Otherwise, you can't get to the last station . Initialization we use n = stations.size() + 1, namely f[i][j] When j be equal to 0 It means f[i][0] All of them have not been oiled , Then their value should be startFuel, as for f[0][j], No initialization required , because j It must be less than waiting i, That is, you can't refuel more than the passing station .
Code 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;
}
};
Ideas 2:
In essence , The problem requires that we need to add the most oil in the minimum number of refueling , That is, add the most oil you can every time you refuel . But every time we pass the station , In fact, only the current station can choose , So how to form options ? The answer is not to refuel every time you pass the station , Record the fuel that can be added into a priority queue , When we need to refuel, we can take it out and refuel for ourselves . The priority queue here is to manage the maximum , What we can take out at any time is the most oil . First of all, the maximum distance we can reach dist Namely startFuel, After judgment dist and target, once dist Greater than or equal to target It's over . In circulation , Every time we pass the station , If at present dist Be able to reach the station , Then let's not refuel , Instead, add oil to the priority queue ; If you can't reach the station , Then come on , If the priority queue has run out of oil , Prove that we can't reach target, Go straight back to -1; If the priority queue has oil , Then take out the biggest oil , give dist, At the same time, update the refueling times .
Code 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]) { // Being able to get to the station means that the oil is enough for the time being
q.push(stations[i][1]); // Don't refuel first , Save up
i++;
} else {
if (q.size()) { // There is oil to add
dist += q.top(); // come on.
q.pop();
count++; // Number of updates
} else { // No oil to add , Cannot reach target
return -1;
}
}
}
return count;
}
};
边栏推荐
- CDGA|数据治理不得不坚持的六个原则
- Cron expression (seven subexpressions)
- Ddrx addressing principle
- Modulenotfounderror: no module named 'scratch' ultimate solution
- Startup process of uboot:
- 【Oracle】使用DataGrip连接Oracle数据库
- Sklearn model sorting
- 【广告系统】增量训练 & 特征准入/特征淘汰
- ZCMU--1390: 队列问题(1)
- Advanced technology management - what is the physical, mental and mental strength of managers
猜你喜欢
【Oracle】使用DataGrip连接Oracle数据库
go语言学习笔记-分析第一个程序
【广告系统】增量训练 & 特征准入/特征淘汰
In the last process before the use of the risk control model, 80% of children's shoes are trampled here
DDRx寻址原理
Characteristics and electrical parameters of DDR4
R3Live系列学习(四)R2Live源码阅读(2)
MySQL 巨坑:update 更新慎用影响行数做判断!!!
Stop saying that microservices can solve all problems!
Codeforces Round #804 (Div. 2)
随机推荐
Huawei equipment configures channel switching services without interruption
c#操作xml文件
Crawler (9) - scrape framework (1) | scrape asynchronous web crawler framework
871. Minimum Number of Refueling Stops
Basic part - basic project analysis
Codeforces Round #804 (Div. 2)
跨境电商是啥意思?主要是做什么的?业务模式有哪些?
IPv6与IPv4的区别 网信办等三部推进IPv6规模部署
AUTOCAD——遮罩命令、如何使用CAD对图纸进行局部放大
7.2每日学习4
Go language learning notes - analyze the first program
[JS] extract the scores in the string, calculate the average score after summarizing, compare with each score, and output
2022 Pengcheng cup Web
不要再说微服务可以解决一切问题了!
四部门:从即日起至10月底开展燃气安全“百日行动”
【爬虫】charles unknown错误
How to understand super browser? What scenarios can it be used in? What brands are there?
Summary of thread and thread synchronization under window
Ddrx addressing principle
TSQL – identity column, guid, sequence