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
|
近期评论