There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.
这道题最容易想到的方法就是从一个点出发，看看能不能走回到起点，如果可以返回起点的index, 不行的话再试下一个点。但是超时。
这个超时算法中有两点值得注意。
a) L13. 对于 int a 怎么计算 a 在 循环群[0,1,2,n-1]上的index?
b) L21-L22，可以使用一个变量记录是哪一步跳出的。然后判断是不是最后一步跳出的。
1 class Solution(object): 2 def canCompleteCircuit(self, gas, cost): 3 """ 4 :type gas: List[int] 5 :type cost: List[int] 6 :rtype: int 7 """ 8 n = len(gas) 9 for i in range(n):10 fule = 011 step = 012 for j in range(n):13 index = (i+j +1)%n -114 fule += gas[index]15 step = j16 if fule < cost[index]:17 break18 else:19 fule -= cost[index]20 21 if step == n-1: 22 return i23 return -1
一下三条原则摘自： http://bangbingsyb.blogspot.com/2014/11/leetcode-gas-station.html
性质1. 对于任意一个加油站i，假如从i出发可以环绕一圈，则i一定可以到达任何一个加油站。显而易见。
性质2. 如果这样的i是唯一的，则必然不存在j!=i， 从j出发可以到达i。
反证法：如果存在这样的j，则必然存在j->i->i的路径，而这个路径会覆盖j->j一周的路径。那么j也将是一个符合条件的起点。与唯一解的限制条件矛盾。
性质3. 假如i是最后的解，则由1可知，从0 ~ i-1出发无法达到i。而从i出发可以到达i+1 ~ n-1。
1 class Solution(object): 2 def canCompleteCircuit(self, gas, cost): 3 """ 4 :type gas: List[int] 5 :type cost: List[int] 6 :rtype: int 7 """ 8 n = len(gas) 9 start = 010 netGasSum = 011 curGasSum = 012 13 for i in range(n):14 netGasSum += gas[i] - cost[i]15 curGasSum += gas[i] - cost[i]16 if curGasSum < 0:17 start = i+118 curGasSum = 0;19 20 if netGasSum < 0:21 return -122 return start