134.加油站

发表于： 分类于：
字数： 2140 阅读：≈ 5分钟

⛽134.加油站

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

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

要保证油箱中的油大于需要消耗的汽油

基本思想就是最开始要积累足够多的剩余汽油，才够后面消耗

示例

说明:

  • 如果题目有解，该答案即为唯一答案。
  • 输入数组均为非空数组，且长度相同。
  • 输入数组中的元素均为非负数。

示例 1: 输入:

  • gas = [1,2,3,4,5]
  • cost = [3,4,5,1,2]

输出: 3 解释:

  • 从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
  • 开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
  • 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
  • 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
  • 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
  • 开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
  • 因此，3 可为起始索引。

示例 2: 输入:

  • gas = [2,3,4]
  • cost = [3,4,3]
  • 输出: -1
  • 解释: 你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油。开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油。开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油。你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。因此，无论怎样，你都不可能绕环路行驶一周。

思路

基本思想

暴力解法

依次从每一个加油站开始出发，定义一个变量记录油箱中的油量，看油量是不是大于等于消耗的油量，也就是剩余油量是不是大于零，是的话就可以到达下一加油站，加油之后（油量=剩余+新的）再走，主要关注如何判断是一个环

可以判断当前是不是走到了容器的末尾，是的话让下标直接截断到0，直接使用取余就可以截断

相当于使用了暴力解法，主要要注意如何模拟环形

可能会超时

贪心算法

遍历容器，一旦出现剩余汽油为负数，那么就说明从这个起点开始无法给后面积累汽油，拖了后腿，只能从下一个起点开始

分为三种情况遍历：

  1. 遍历一遍剩余汽油为负数，问题无解

  2. 遍历一遍中间出现剩余汽油为负数的情况，说明从0开始为起点不可以

  3. 从后往前判断，到底哪个起点开始积累的汽油能够将剩余汽油为负的情况填补上

    这里从后往前是因为从前往后遇到了剩余汽油为负的情况，或者说是判断从哪个汽油站开始向后积累的汽油可以让之前某个位置不再缺油

执行流程

暴力解法

主要是模拟环形，一旦下标到了容器的末尾就需要截断到0，其余的正常递增，所以下标的变化公式为：index=(index+1)%gas.size(),到达容器的末尾，取余就是0，实现了截断为0的效果

并且需要判断油量能不能支持走到下一个加油站，所以直接看剩余油量是不是大于零，剩余油量的计算公式为：capacity=gas[i]-cost[i]

贪心算法

从0模拟一圈，记录每一步的剩余汽油量，遍历结束如果剩余汽油量大于零说明有解，如果某一步出现负数就不能从0开始，但是出现有不够之后后面又给补起来了,所以才会cursum>0

此时需要寻找一个新的起点，剩余的汽油量足够让油不够的时候进行补充

寻找新的起点需要从后往前，这样找到的起点往后积累的汽油才可以让汽油不够的路段使用

代码

暴力解法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int index=0;
        int capacity=0;
        //依次从每一个加油站出发
        for(int i=0;i<gas.size();++i){
            //从第i个加油站出发先走一步
            index= (i+1)%gas.size();//是从最后一个加油站出发的话直接截断到0
            capacity=gas[i]-cost[i];
            //先走一步判断条件更好写
            while(capacity>=0&& index!=i){
                //更新汽油剩余量和当前到达的加油站
                capacity+=gas[index]-cost[index];
                if(capacity<0)  break;
                index=(index+1)%gas.size();
            }
            if(capacity>=0&&index==i)   return i;
        }
        //每个站点都试过，都无法回到起点
        return -1;
    }
};

贪心算法 

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

class Solution {
public:
    int canCompleteCircuit(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;  // 情况1
        //剩余汽油为正，且每一步汽油都足够，以0为起点即可
        if (min >= 0) return 0;     // 情况2
                                    // 情况3
        //看从那个点出发积累的汽油可以让没油的路段变得有油
        for (int i = gas.size() - 1; i >= 0; i--) {
            int rest = gas[i] - cost[i];
            min += rest;
            if (min >= 0) {
                return i;
            }
        }
        return -1;
    }
};

总结

暴力解法主要是如何形成环形，使用while和取余操作，一旦出现某一步剩余汽油为负，这个点就不能作为起点

贪心算法主要是先尝试从0开始为起点，有两个目的，如果最后剩余汽油为负数，说明问题无解，如果剩余汽油为正数并且每一步都有足够汽油，说明以0为起点即可

如果剩余汽油为正数但是某一步出现汽油不够的情况，就需要重新找一个起点，从该七点向后积累的汽油可以供没油的路段使用

不知道为什么按照自己的思路写出来的代码不一样

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int capacity=0;
        int min=INT_MAX;
        for(int i=0;i<gas.size();++i){
            int curr=gas[i]-cost[i];
            //统计最终汽油的剩余量
            capacity+=curr;
            //判断是否有某一步汽油不够
            if(curr<min){
                min=curr;
            }
        }
        //如果剩余汽油量小于0，则无解
        if(capacity<0)  return -1;
        //如果剩余汽油量大于0并且每一步汽油都足够，则0为起点即可
        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;
    }