Question: https://oj.leetcode.com/problems/gas-station/

Question Name: Gas Station

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 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 | class Solution: # @param gas, a list of integers # @param cost, a list of integers # @return an integer def canCompleteCircuit(self, gas, cost): # The change of gas, if we move from one station to the next. gasChange = [gas[index]-cost[index] for index in xrange(len(gas))] # Double the array to avoid the mod operation for circular route. gasChange = gasChange + gasChange # Try to start our trip at each statioin. start = 0 while start < len(gas): left = 0 # Remaining gas in current trip. station = 0 # The current station during this trip. while station < len(gas): left += gasChange[start + station] if left < 0: # No enough gas to continue our trip. break station += 1 else: # Finished the trip successfully. return start # Let start be i, start + station be j. We know that sum of # gasChange[i : j+1] is negative. And for ANY m and n, if the # sum of gasChange[m : n+1] is nagative, we will break the while # loop. So as long as we COULD travel from i to j station, for # ALL k in range [i+1, j), we know that the remaining gas, or # say the sum of gasChange[i, k+1], is zero or positive. # # sum(gasChange[i, k+1]) + sum(gasChange[k+1, j+1]) # = sum(gasChange[i, j+1]) < 0 # AND # sum(gasChange[i, k+1]) >= 0 # Thus # sum(gasChange[k+1, j+1]) < 0 ( For ALL k in [i+1,j) ) # Considering the i(th) and j(th) item, we can easily get that: # sum(gasChange[k+1, j+1]) < 0 ( For ALL k in [i,j] ) # # So no station in the range [i, j+1) could be the start position. start += station + 1 return -1 |