我要招人

去企业版

首页 > 试题广场 >

加油站

[编程题]加油站

热度指数：2417 时间限制：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

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)

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)

提交观点

问题信息

贪心数组

难度：

9条回答 46收藏 1721浏览

通过挑战的用户

查看代码

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

加油站

输入

输出

说明

输入

输出

输入

输出

说明

问题信息

热门推荐

通过挑战的用户

相关试题