DFS Solution ( Time Limit Exceeded )
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
def dfs(start, current, remain):
if remain < 0:
return False
if start == current:
return True
return dfs(start, (current + 1) % len(gas), remain + gas[current] - cost[current])
for i in range(len(gas)):
if dfs(i, (i + 1) % len(gas), gas[i] - cost[i]):
return i
return -1
The DFS based solution will time out. However it reveals :
1. To finish a circle, the total gained gas must larger than total used gas
2. At each position, remained gas = last remained gas + gained gas - used gas.
To reach to the next position, remained gas must larger than 0
If remained gas < 0, it means from the start position to current position, none of them can be used as start point. Because the initial remained gas of start position = 0
Greedy Solution
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
# to finish a circle, gained gas must larger or equal to used gas
total = 0
# at each pos, remained gas = last remained gas + gained gas - used gas
# if remained gas < 0, it means from start pos to current pos,
# none of them can be used as start point.
# because the initial remained gas of the start position = 0
remain = 0
start = 0
for i in range(len(gas)):
total += gas[i] - cost[i]
remain += gas[i] - cost[i]
if remain < 0:
start = i + 1
remain = 0
return start if total >= 0 else -1
No comments:
Post a Comment