leetcode gasstation_leetcode gasstation 分析

一圈加油站，每个加油站有一定量的油，从加油站i去加油站i+1会消耗一定的油。这两个数据分别存在数组gas和数组cost里，以gas[i]和cost[i]表示。

要求出从哪个加油站出发可以绕一圈。

看后面的讨论，大概问题是：绕一圈最后是回到原来的加油站吗？那是否可以倒着转呢？

绕一圈肯定是回到原来的加油站，不过倒着转还真没想到。。按照题意，从i到i+1的cost保存在数组里，那么从i+1到i的消耗是不是就是cost[i]？

而倒着转的答案就不一定和顺着的一样了。比如：gas：2,1,3,5 ； cost：4,2,2,3

思维惯性导致一直觉得需要对每个加油站遍历，但其实只用遍历一次就可以得到答案。试想：从1开到5，发现5过不去6，那么从2,3,4开到5当然也过不去，所以它们都不用试了。

我的代码的思路应该是最简单的了：

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int sumgas = 0, sumcost = 0, n = gas.size();
    	int i,j;
    	for(i = 0; i < n; i++){
    		sumgas += gas[i];
    		sumcost += cost[i];
    	}
    	if(sumcost > sumgas)return -1;
    	
    	for(i = 0;i < n;){
    		sumgas = 0; sumcost = 0;
    		for(j = i; j<n+i;j++ ){
    			int index = j%n;
    			sumgas += gas[index];
    			sumcost += cost[index];
    			if(sumcost > sumgas){
    				i = index + 1;
    				break;
    			}
    		}
    		if(j == n+i)return i;
    	}
    	return -1;//no use if guaranteed solution
    }
};

当然还有一些人写得更简洁：

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        int start(0),total(0),tank(0);
        //if car fails at 'start', record the next station
        for(int i=0;i<gas.size();i++) if((tank=tank+gas[i]-cost[i])<0) {start=i+1;total+=tank;tank=0;}
        return (total+tank<0)? -1:start;
    }
};