当前位置:网站首页>[daily training] 871 Minimum refueling times
[daily training] 871 Minimum refueling times
2022-07-03 00:42:00 【Puppet__】
subject
The car set off from the starting point to the destination , The purpose is to the east of the starting position target Miles away .
There are gas stations along the way , Every station[i] For a gas station , It's east of the starting point station[i][0] Miles away , And there are station[i][1] A litre of petrol .
Suppose the capacity of the car's fuel tank is infinite , At first there was startFuel Liter fuel . Every time it drives 1 Miles will be used 1 A litre of petrol .
When the car arrives at the gas station , It may stop to refuel , Transfer all gasoline from the gas station to the car .
In order to reach the destination , What's the minimum number of refuels necessary for a car ? If you can't get to your destination , Then return to -1 .
Be careful : If the remaining fuel when the car arrives at the gas station is 0, It can still refuel there . If the remaining fuel is 0, Still think it has reached its destination .
Example 1:
Input :target = 1, startFuel = 1, stations = []
Output :0
explain : We can get to our destination without refueling .
Example 2:
Input :target = 100, startFuel = 1, stations = [[10,100]]
Output :-1
explain : We can't get to our destination , Not even getting to the first gas station .
Example 3:
Input :target = 100, startFuel = 10, stations = [[10,60],[20,30],[30,30],[60,40]]
Output :2
explain :
We set out with 10 Liter fuel .
We drove to the starting point 10 The gas station at mile , Consume 10 Liter fuel . Take the gas from 0 To add to 60 l .
then , We from 10 The gas station is miles away 60 The gas station at mile ( Consume 50 Liter fuel ),
And take the gas from 10 To add to 50 l . Then we drove to our destination .
We are on the way 1 Two gas stations stop , So back 2 .
Tips :
1 <= target, startFuel, stations[i][1] <= 109
0 <= stations.length <= 500
0 < stations[0][0] < stations[1][0] < … < stations[stations.length-1][0] < target
Code
package dayLeetCode;
public class dayleetcoe871 {
// dp dp[i] It means refueling i The maximum number of miles traveled
// Take the oil away , Whether you use it or not depends on the specific situation , Always get the biggest oil
public int minRefuelStops(int target, int startFuel, int[][] stations) {
long[] dp = new long[stations.length + 1];
dp[0] = startFuel;
for (int i = 0; i < stations.length; i++){
// Before judgment j Can I get there with this refueling i, If it can be reached, it will be judged whether it will be i Fill the car with gas from a gas station
for (int j = i; j >= 0; j--){
if (dp[j] >= stations[i][0]){
dp[j + 1] = Math.max(dp[j + 1], dp[j] + stations[i][1]);
}
}
}
// Find the least number of refuelling
for (int i = 0; i <= stations.length; i++){
if (dp[i] >= target){
return i;
}
}
return -1;
}
public static void main(String[] args) {
dayleetcoe871 obj = new dayleetcoe871();
System.out.println(obj.minRefuelStops(1, 1, new int[][]{
}));
}
}
边栏推荐
- [jetcache] jetcache configuration description and annotation attribute description
- Wechat applet obtains the information of an element (height, width, etc.) and converts PX to rpx.
- Shell脚本基本使用
- Form form instantiation
- 详解用OpenCV的轮廓检测函数findContours()得到的轮廓拓扑结构(hiararchy)矩阵的意义、以及怎样用轮廓拓扑结构矩阵绘制轮廓拓扑结构图
- AttributeError: ‘tuple‘ object has no attribute ‘layer‘问题解决
- Nc20806 District interval
- NC50965 Largest Rectangle in a Histogram
- Vulkan-性能及精细化
- cordova-plugin-device获取设备信息插件导致华为审核不通过
猜你喜欢
[shutter] Introduction to the official example of shutter Gallery (learning example | email application | retail application | wealth management application | travel application | news application | a
【AutoSAR 十 IO架构】
可下载《2022年中国数字化办公市场研究报告》详解1768亿元市场
redis21道经典面试题,极限拉扯面试官
Pageoffice - bug modification journey
kubernetes资源对象介绍及常用命令(五)-(NFS&PV&PVC)
【AutoSAR 十一 通信相关机制】
详解用OpenCV的轮廓检测函数findContours()得到的轮廓拓扑结构(hiararchy)矩阵的意义、以及怎样用轮廓拓扑结构矩阵绘制轮廓拓扑结构图
ftrace工具的介绍及使用
Shell 实现文件基本操作(sed-编辑、awk-匹配)
随机推荐
机器学习:numpy版本线性回归预测波士顿房价
【AutoSAR 十 IO架构】
AEM: Nanlin fan Ben et al. - plant rhizosphere growth promoting bacteria control soybean blight
NC20806 区区区间间间
[shutter] image component (the placeholder | transparent_image transparent image plug-in is loaded into the memory)
腾讯云免费SSL证书扩展文件含义
【Pulsar文档】概念和架构/Concepts and Architecture
Is there a free text to speech tool to help recommend?
helm 基础学习
使用jenkins之二Job
Automated defect analysis in electron microscopic images-论文阅读笔记
lex && yacc && bison && flex 配置的問題
1.12 - 指令
[shutter] image component (load network pictures | load static pictures | load local pictures | path | provider plug-in)
Briefly talk about other uses of operation and maintenance monitoring
多进程编程(五):信号量
kubernetes资源对象介绍及常用命令(五)-(NFS&PV&PVC)
kubernetes编写yml简单入门
免费自媒体必备工具分享
node_ Modules cannot be deleted