Gas Station (Medium)

Description

There are N gas stations along a circular route, where the amount of gas at station i 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.

Note:
The solution is guaranteed to be unique.

Analysis

简单的贪心。有点像求连续区间最大和的感觉。。

My Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
//C++
class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
     
        int len = gas.size();
        int sum = 0,i,j;
        for(i = 0;i<len;i+=(j+1)){
            
            for(j = 0 ; j< len ;j++){
                
                int k = (i+j)%len;
                sum+=gas[k]-cost[k];
                if(sum<0){
                    break;
                }
            }
            if(j>=len)
                return i;
            sum = 0;
        }
        return -1;
    }
};