题目:

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.

思路: 最简单的思路,每个元素遍历,判断其是否可以完成绕圈任务,复杂度 ,提交之后果断TLE。。。

需要加入一个小trick,如果上一次遍历,以i为起点,到j的时候发现gas不够,则下一次不应该从i+1开始,而应该从j+1开始,原因很简单,如果gas[i]>cost[j],那么遍历i点应该是可以对i+1到j产生好处的,以此类推,i到j-1应该可以对遍历j产生好处(i到j-1之后,剩余的汽油大于0),所以若下一次仍从i+1开始,显然不可能通过。

代码如下:

class Solution:
	# @param gas, a list of integers
	# @param cost, a list of integers
	# @return an integer
	def canCompleteCircuit(self, gas, cost):
		N = len(gas)
		if N==1:
			if gas[0]>=cost[0]:
				return 0
			else:
				return -1
		if sum(gas)<sum(cost):
			return -1
		i=0
		while i<N:
			flag = True
			num = 0
			for j in xrange(N):
				num += gas[(i+j)%N]
				if num<cost[(i+j)%N]:
					flag = False
					i = (i+j)%N+1
					break
				num -= cost[(i+j)%N]
			if flag:
				return i
		return -1