-
Notifications
You must be signed in to change notification settings - Fork 17
/
gas-station.py
31 lines (23 loc) · 903 Bytes
/
gas-station.py
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
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
left = 0
min_pos, min_val = 0, float("+inf")
for pos in range(len(gas)):
if min_val > left:
min_pos = pos
min_val = left
left += gas[pos] - cost[pos]
if left >= 0:
return min_pos
return -1
def canCompleteCircuitBruteForce(self, gas: List[int], cost: List[int]) -> int:
def dfs(pos: int, start_pos: int, gas_left: int) -> bool:
if gas_left < 0:
return False
if pos == start_pos:
return True
return dfs((pos + 1) % len(gas), start_pos, gas_left + gas[pos] - cost[pos])
for pos in range(len(gas)):
if dfs((pos + 1) % len(gas), pos, gas[pos] - cost[pos]):
return pos
return -1