刷题路程|leetcode:gas_station

题目描述

There are N gas stations along a circular route, where the amount of gas at station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station(i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

解题思路

可以先算出每一站到下一站的净获油量，就是每一站得到的油量减去到下一站会消耗的油量。既然能走完所有站，则说明油量足够，所以每一站的净获油量相加的总值为正，就表示能走完所有站。那么现在问题是从哪一站开始走呢？
可以把起点设为第一个站，如果到下一个站的油量够（目前的油量加上到下一站的净获油量为正数），那就继续判断到下一站的油量是否足够。如果到下一站的油量不够，说明刚才走过的几个点都不能作为起点，所以就要把现在这个点的下一个点设为起点重复前边的操作。

代码

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        vector<int> tmp;//保存净获油量的数组
        
        for(decltype(gas.size()) i=0;i<gas.size();++i){
            //将净获油量存入数组
            tmp.push_back(gas[i]-cost[i]);
        }
        
        int sum=0,index=-1,sum2=0;//sum用来保存当前的油量，sum2用来保存净获油量的总值
        
        for(decltype(tmp.size()) i=0;i<tmp.size();++i){
           
           sum+=tmp[i];
           sum2+=tmp[i];
           if(sum < 0){//如果当前的油量为负，也就是上一站到这一战油量不足
               index=i;//保存当前的索引
               sum=0;//把当前的油量清理，因为要重新把下一站设为起始站
           }
        }
        
        return sum2>=0 ? index+1:-1;//如果净获油量的总值为负，说明走不完所有站，如果为证，返回的起始点就是之前保存的索引对应站的下一站
    }
};