LintCode Q187 Gas Station in Python

  • Jinhai ZHOU
  • 4 Minutes
  • 2017年1月10日
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
class Solution:
# @param gas, a list of integers
# @param cost, a list of integers
# @return an integer
def canCompleteCircuit(self, gas, cost):
# write your code here
# pre_check
if sum(gas) < sum(cost) or len(gas) != len(cost):
return -1
diff = gas
for i in xrange(len(gas)):
diff[i] = gas[i] - cost[i]
# find starting index of largest sub sum
# pay attention: its a cercle
max_sum, index = diff[0], 0
max_candidate, index_candiate = diff[0], 0
for i in xrange(1, len(diff)*2):
ind = i % len(diff)
if max_candidate + diff[ind] > 0:
max_candidate += diff[ind]
else:
max_candidate = 0
index_candiate = ind + 1
if max_candidate > max_sum:
max_sum = max_candidate
index = index_candiate
if index >= len(diff):
return -1
return index
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。