[leetcode]Gas Station

新博文地址：[leetcode]Gas Station

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

 一段环形公路，公路上有N个加油站，每个加油站可以加gas[i]升油，跑到下一个加油站则需要cost[i]升油，油箱容量无上限，起步时油箱是空的，问：是否可以从某一个加油站出发，从而可以环绕公路一周？

 

算法思想：

1. 先找到一个可以起步的站点，即“在该站加的油，可以使汽车足以行驶到下一站”记该站为startFrom

2. 行驶到下一个站点之后，油箱里可能还剩一部分油，再加一部分油，二者之和是油箱里的油量hasGas，这个hasGas要保证>= cost[i]，才可以继续行驶（这是一个循环过程，记作loop）

3. 当遇到某个站点退出了loop，这里有三种情况：

3.1 退出的站点，就是startFrom(后来做了改动，用标记来实现了)，则已经环绕一周，return startFrom。

3.2 退出的站点（记作i），在startFrom之后，那么（startForm ~ i）之间的站点都不需要再检查了，肯定不会超过 i ，因此只需要从i之后的检点进行检查即可。

3.3 退出的站点在startFrom之前，因为之前的站点已经检查过了，是不合法的，因此直接返回 -1。

 

代码如下：

    public int canCompleteCircuit(int[] gas, int[] cost) {
	    int leftGas = 0,startFrom = 0;
	    boolean[] visit = new boolean[gas.length]; 
	    for(int i = 0 ; i < gas.length; i++){
			if( gas[i] >= cost[i] ){//must make sure the first step can be make
				int getTo = i % gas.length;
				leftGas = gas[i];
				startFrom = i;
				while(leftGas >= cost[getTo]){
					if(visit[getTo]) return startFrom;
					visit[getTo] = true;
					leftGas -= cost[getTo];
					getTo = ( getTo + 1 ) % gas.length;
					leftGas += gas[getTo];
				}
			    if(getTo > startFrom){
						i = getTo;
				}else if(getTo < startFrom){
					return -1;
				}
			}
		}
	    return -1;
	}