Title: Gas Station Source: leetcode.com
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.
|
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 |
''' https://leetcode.com/problems/gas-station/ ''' class Solution(object): def canCompleteCircuit(self, gas, cost): """ :type gas: List[int] :type cost: List[int] :rtype: int """ si = 0 n = len(gas) while si < n and gas[si] < cost[si]: si += 1 if si == n: return -1 i = si + 1 g = gas[si] - cost[si] while (i%n) != si: i = i % n g += gas[i] - cost[i] if g < 0: if si < i: while i < n and gas[i] < cost[i]: i += 1 if i == n: return -1 g = gas[i] - cost[i] si = i else: break i += 1 #print g, i if (i%n) == si: return si return -1 |