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 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64
|
""" https://leetcode.com/problems/gas-station/
Input: gas = [1,2,3,4,5] cost = [3,4,5,1,2]
Output: 3
Explanation: Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4 Travel to station 4. Your tank = 4 - 1 + 5 = 8 Travel to station 0. Your tank = 8 - 2 + 1 = 7 Travel to station 1. Your tank = 7 - 3 + 2 = 6 Travel to station 2. Your tank = 6 - 4 + 3 = 5 Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3. Therefore, return 3 as the starting index. """
class : def canCompleteCircuit(self, gas, cost): N = len(gas)
def delta(gas, cost): for i in range(2): for i, j in zip(gas, cost): yield i - j s = 0 start = 0 idx = 0 for d in delta(gas, cost): s += d if s < 0: s = 0 start = idx + 1 else: if idx - start == N: return start idx += 1 return -1
class Solution2: def canCompleteCircuit(self, gas, cost):
delta = [i-j for i, j in zip(gas, cost)] * 2 s = 0 start = 0 for i in range(len(delta)): s += delta[i] if s < 0: s = 0 start = i + 1 else: if i - start == len(gas): return start return -1
if __name__ == '__main__': s = Solution() gas = [1, 2, 3, 4, 5] cost = [3, 4, 5, 1, 2] assert s.canCompleteCircuit(gas, cost) == 3
|
近期评论