首页 > 试题广场 >

加油站

[编程题]加油站

热度指数：2291 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

在一条环路上有 n 个加油站，其中第 i 个加油站有 gas[i] 升油，假设汽车油箱容量无限，从第 i 个加油站驶往第 (i+1)%n 个加油站需要花费 cost[i] 升油。

请问能否绕环路行驶一周，如果可以则返回出发的加油站编号，如果不能，则返回 -1。

题目数据可以保证最多有一个答案。

数据范围： $1 \leq n \leq 10^4 \$ ， gas 和 cost 数组中的值满足 $1 \leq val \leq 10^5 \$

示例1

输入

[1,2,3,4,5],[3,4,5,1,2]

输出

说明

只能从下标为 3 的加油站开始完成 （即第四个加油站）

示例2

输入

[0,10],[9,1]

输出

示例3

输入

[2,3,4],[3,4,5]

输出

-1

说明

无论从哪个加油站出发都无法环绕环道一圈

算法知识视频讲解

Java

pein531

时间复杂度O(n²)的解法还是比较好想的，首先构建一个“纯能值”数组energy（用gas减去cost）。其中的元素energy[i]表示如果从i加油站开车去往下一个加油站i+1，可以给下一个加油站带去多少油。如此一来，只有在energy[i]非负的情况下，i才有可能是符合题意的出发点，这样可以过滤掉一些明显不合题意的加油站。

而根据energy数组的含义我们就能明白，其中的元素表示在车行驶到某个加油站时的剩余油量。因此随便选择一个加油站出发，如果累加一圈的过程中出现了负数，那肯定就无法从这个加油站出发环绕一周。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        // write code here
        LinkedList<Integer> candicates = new LinkedList<>();
        int n = gas.length;
        for(int i = 0; i < n; i++){
            gas[i] -= cost[i];
            if(gas[i] >= 0){
                candicates.add(i);
            }
        }
        while(!candicates.isEmpty()){
            int startPoint = gameStarted(gas, candicates.removeFirst());
            if(startPoint != -1){
                return startPoint;
            }
        }
        return -1;
    }
    
    private int gameStarted(int[] energy, int start) {
        int cur = start;
        int cumsum = energy[cur];
        cur++;
        if(cur == energy.length) cur = 0;
        while(cur != start){
            if(cumsum >= 0){
                cumsum += energy[cur];
                cur++;
                if(cur == energy.length) cur = 0;
            }else{
                return -1;     // 累加一圈出现了负数
            }
        }
        return start;
    }
}

编辑于 2021-12-22 15:28:33 回复(0)

空中转体一周半

解题思路：挨个检查是否满足gas[i] - cost[i] >= 0 如果满足，则说明该加油站有充足的油驶往下一个加油站，则开始模拟加油过程。时间复杂度o(n^2).

import java.util.*;
public class Solution {
    public int gasStation (int[] gas, int[] cost) {
        int res = 0;
        for(int i = 0; i < gas.length; ++i) {
            if(gas[i] < cost[i]) continue;
            res = gas[i];
            for(int j = 0; j < gas.length; ++j) {
                res -= cost[(j + i) % gas.length];
                if(res < 0) break;
                res += gas[(j + i + 1) % gas.length];
            }
            if(res >= 0) return i;
        }
        return -1;
    }
}

发表于 2023-04-19 17:15:09 回复(0)

在重庆的9527想飞翔

import java.util.*;

public class Solution {

/**

* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可

* @param gas int整型一维数组

* @param cost int整型一维数组

* @return int整型

public int gasStation (int[] gas, int[] cost) {

// write code here

int ans = 0;

int left = 0;

int total = 0;

for(int i = 0; i<gas.length; i++){

total += gas[i] - cost[i];

if(left+gas[i]-cost[i]>=0){

left += gas[i]-cost[i];

}

else{

ans = i + 1;

left = 0;

}

System.out.println(total);

return total>=0 ? ans:-1;

}

发表于 2023-08-11 14:03:30 回复(0)

布加迪.威龙

static const auto io_sync_off = [](){
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);
    return nullptr;
}();
class Solution {
public:
    int gasStation(vector<int>& gas, vector<int>& cost) {
        int curSum=0;
        int min=INT_MAX;
        for(int i=0;i<gas.size();i++)
        {
            int rest=gas[i]-cost[i];
            curSum+=rest;
            if(curSum<min)
                min=curSum;
        }
        if(curSum<0)
            return -1;
        if(min>=0)
            return 0;
        for(int i=gas.size()-1;i>=0;i--)
        {
            int rest=gas[i]-cost[i];
            min+=rest;
            if(min>=0)
                return i;
        }
        return -1;
    }
};

发表于 2022-07-19 09:09:59 回复(0)

Java

keduoli

思路还是贪心，时间复杂度为O（n）。

import java.util.*;


// 这个题， 和简单题，求子序列的最大和，有点像
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        // write code here
        
        // *)
        int s = 0;
        int sum = 0;
        
        int n = gas.length;
        for (int i = 0; i < n; i++) {
            
            int delta = gas[i] - cost[i];
            sum += delta;
              
            // 维护子序列的和 >= 0, 移动子序列的头指针
            while (sum < 0 && s <= i) {
                sum -= (gas[s] - cost[s]);
                s++;    
            }
           
        }
        
        // 补剩下的环
        for (int i = 0; i < s; i++) {
            sum += (gas[i] - cost[i]);
        }
        
        if (sum >= 0) {
            return s;
        }
        return -1;
        
    }
    
}

发表于 2022-03-11 20:08:26 回复(0)

Java

牛客774131035号

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param gas int整型一维数组 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int gasStation (int[] gas, int[] cost) {
        int spare=0;
        int minspare=Integer.MAX_VALUE;
        int index=0;
        for(int i=0;i<gas.length;i++){
            spare+=gas[i]-cost[i];
            if(spare<minspare){
                minspare=spare;
                index=i;
            }
        }
        return spare>=0?index+1:-1;
        // write code here
    }
}

}
}

发表于 2022-02-25 14:13:38 回复(0)

Java

牛客564911714号

直接暴力，用2个forloop和%膜判断能不能绕一圈，当出现一个站点的gasCapacity < 0 就说明当前不可行，跳到下一个站点。

import java.util.*;

public class Solution {
   
    public int gasStation (int[] gas, int[] cost) {
        // write code here
        int gasCapacity = 0;
        int begin = -1;
        
        for (;;) {
            begin++;
            if (begin == gas.length) return -1; //走完一圈没有发现有站点满足需求 返回-1
            for (int i = begin; i < begin + gas.length; i++) {
                gasCapacity += gas[i % gas.length]; //膜一下，当超出范围会回到起点
                gasCapacity -= cost[i % gas.length];
                if (gasCapacity < 0) { //当前站点累计的汽油不足以到下一个站点
                    gasCapacity = 0;
                    break;
                }
                if (i == begin + gas.length - 1) { //判断是否已经走了一圈，返回这个初始站点的位置
                    return begin;
                }
            }
        }
    }
}

发表于 2022-01-05 12:55:34 回复(0)

C++

QNBZ

class Solution {
public:
int startGame(vector<int>energy,int start)
{
int power=energy[start];
int cur=start+1;
if(cur==energy.size())cur=0;
while(cur!=start)
{
power+=energy[cur];cur++;
if(cur==energy.size())cur=0;
if(power<0)return -1;
}
return start;
}
int gasStation(vector<int>& gas, vector<int>& cost) {
// write code here
queue<int>tmp;int n=gas.size();
for(int i=0;i<n;i++)
{
gas[i]-=cost[i];
if(gas[i]>=0)tmp.push(i);
}
while(!tmp.empty())
{
int pos=startGame(gas,tmp.front());tmp.pop();
if(pos!=-1) return pos;
}
return -1;

}
};

发表于 2022-01-01 18:12:04 回复(0)

提交观点

问题信息

贪心数组

难度：

8条回答 42收藏 1663浏览

通过挑战的用户

查看代码

bierxiensi

2022-09-17 10:07:35
牛客80519...

2022-09-15 17:18:59
蒋燊

2022-09-15 08:14:59
牛客89818...

2022-09-14 13:39:35
Asphyxiay

2022-09-14 01:34:36

加油站

输入

输出

说明

输入

输出

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题