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
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 Solution:
    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