Friday, July 25, 2014

[LeetCode] Gas Station

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.

解题思路:
 隐含的一个条件为: 如果 i 不能到达j, 则 i+1..j-1也不能到达j.


 public int canCompleteCircuit(int[] gas, int[] cost) {
        int gasleft = 0;
        int beginIndex = 0;
        int n = gas.length;
        
        while (beginIndex < n){
            int i = 0;
             while( i < n ){
                   int curr = (i + beginIndex)%n; 
                   gasleft +=gas[curr] -cost[curr]; 
                   
                   if(gasleft < 0){
                         beginIndex += i + 1;
                         gasleft = 0;
                         break;
                     }
                   
                   i++;
              }
             
             if(i == n) return beginIndex;
        } 
              
        return -1;
              
   }

No comments:

Post a Comment