Gas Station

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 costscost[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.

题意

在一个圆形路径上有N个加油站，在位置 i 上的汽油的数目为gas[i]；

你有一个汽车，这个汽车的油箱是无限容量的，它从加油站 i 到加油站（i+1）需要耗费的汽油数为cost[i]，开始这段旅程的时候，

你的起始状态是在加油站中的一个，油箱为空的.

若一次性完成整个的圆形路途，返回你的其实加油站的序号，若不能完成整个路途，返回-1.

注意：

解决方案保证是唯一的.

思路

想通两点，第一，如果总存储油量大于等于总消耗油量，那么这个问题一定是有解的。第二，怎样找到这个出发点，可设变量total和变量start，当total为负时，total归零，并改变start的值。

python实现

class Solution:    def canCompleteCircuit(self, gas, cost):        if sum(gas) < sum(cost):            return -1        start = -1        total = 0        for i in range(len(gas)):            total += (gas[i] - cost[i])            if total < 0:                total = 0                start = i+1        return start

转载地址：http://lejmb.baihongyu.com/

你可能感兴趣的文章