贪心：尽量将gas[i]-cost[i]>0的放在前面，gas[i]-cost[i]<0的放在后面。（路程的前面有汽油剩下，耗汽油的放在路程的后面）。
能否全程通过的 条件 是：sum(gas[i])>=sum(cost[i])，不满足这个条件就不能全程走一遍；
起点 i 满足的 必要 条件 是：额外剩下的gas（additional_gas）要大于等于0，即 gas[i]-cost[i]>=0；
另外需满足：
找出某站点 i_save ，经过这个站点剩下的gas最多，找出某站点 i_need ，经过这个站点所欠的gas最多，
“额外需要gas最多的站点”应该放在最后，“额外剩下gas最多的站点”应该放首位，优先将“额外剩下gas最多的站点”放首位；
如果 “额外需要gas最多的i”>“额外剩下gas最多的i”（-additional_gas[need]>=additional_gas[save]），则将“额外需要gas最多的i”放在最后。
如果“额外需要gas最多的i”和“额外剩下gas最多的i”有不止一个，则“额外需要gas最多的i”取最后一个，“额外剩下gas最多的i”取最前面那个。
例如：
| i | 0 | 1 | 2 | 3 | 4 |
| gas | 1 | 2 | 3 | 4 | 5 |
| cost | 3 | 4 | 5 | 1 | 2 |
| additional_gas | -2 | -2 | -2 | 3 | 3 |
起始站点为i=3。
自认为是比较简洁的代码:
class Solution:
# @param gas, a list of integers
# @param cost, a list of integers
# @return an integer
def canCompleteCircuit(self, gas, cost):
additional_gas=[]
for i in range(len(gas)):
additional_gas.append(gas[i]-cost[i])
if sum(additional_gas)<0:
return -1
need=0
save=0
for i in range(len(gas)):
if additional_gas[i]>0 and additional_gas[i]>additional_gas[save]:
save=i
if additional_gas[i]<0 and additional_gas[i]<=additional_gas[need]:
if i<len(gas)-1 and additional_gas[i+1]>0:
need=i
if -additional_gas[need]>additional_gas[save]:
return need+1
else:
return save if __name__ == '__main__':
s=Solution()
print(s.canCompleteCircuit([6,1,2,3,2,1,8],[1,7,2,2,2,8,1]))
下面的代码也能通过。
class Solution:
# @param gas, a list of integers
# @param cost, a list of integers
# @return an integer
def canCompleteCircuit(self, gas, cost):
additional_gas=[]
for i in range(len(gas)):
additional_gas.append(gas[i]-cost[i])
if sum(additional_gas)<0:
return -1
start=0
for i in range(1,len(gas)):
if (additional_gas[i]>=0 and additional_gas[i-1]<0):
start=i
return start