1. If the total gas from station i to station j (i and j don't have to be consecutive) is less than the total cost, station i cannot be the gas station.
2. If the total gas in all stations is less than the total cost, no solution.
Update: 2015 - 01 - 03
Track a partial sum, if the sum of the gases before gas station i is less than cost. Then all gas stations before i cannot be the starting point. Reset the starting point to i and partial sum to zero.
public class GasStation { public int canCompleteCircuit(int[] gas, int[] cost) { if (gas == null || gas.length == 0 || cost == null) return -1; //return index + 1, thus need to start from -1 int index = -1; int sum = 0; int total = 0; for (int i = 0; i < gas.length; i++) { sum += gas[i] - cost[i]; total += gas[i] - cost[i]; if (sum < 0) { index = i; //need to recalculate the total sum from station i sum = 0; } } return total < 0 ? -1 : index + 1; } }
No comments:
Post a Comment