Question Name: Gas Station
Solution to Gas Station by LeetCode
# @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.
station += 1
# Finished the trip successfully.
# 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
# sum(gasChange[i, k+1]) >= 0
# 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