学步园

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.

题目解析：

方案一：

两个数组之间的值是对应的，那么就将gas[i]-cost[i]经过i结点增加或消耗的油量。这样就直接考虑结点的值，而不用考虑路程中的值，进一步转化成一个一维数组，求从哪一点开始求和，能无负数出现。

常规思维是，让任一点为起始点，开始计算，这样时间复杂度为O(N^2)。但是负数的起始点是不可能的，因此跳过负数为起始的。更进一步，我们选那些s[i-1]为负数，s[i]为大于等于0时，i为起始点，即使i后有连续几个为正数，由于题目中结果唯一，则必须i开始为起始点。这样就更进一步简化。不过实现的时候，有点复杂，我只是选择非负数为起始点，进行递归求解。

如果Judge为false时，才判断深层次的递归返回值。

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        if(gas.size() != cost.size())
            return -1;
        res = -1;
        vector<int> remainder;
        for(int i = 0;i < gas.size();i++)
            remainder.push_back(gas[i]-cost[i]);
        FindIndex(remainder,0);
        return res;
    }
    bool FindIndex(vector<int> &remainder,int index){
        if(index >= remainder.size()){
            return false;
        }
        int i;//写在外面
        for(i = index;i < remainder.size();i++){
            if(remainder[i] >= 0)   //要加等号[2] [2]
                break;
        }
        if(i == remainder.size()){
            int res = -1;
            return false;
        }

        return Judge(remainder,i) || FindIndex(remainder,i+1);
    }
    bool Judge(vector<int> &remainder,int index){
        int sum = 0;
        for(int i = 0;i < remainder.size();i++){
            sum += remainder[(index+i)%remainder.size()];
            if(sum < 0)
                return false;
        }
        res = index;
        return true;
    }
private:
    int res;
};

方案二：

线性时间复杂度O(n)

我们让i=0...n-1开始遍历，期间统计求和sum，如果sum为负数，则肯定从i+1之后开始！所以当j从i+1...n-1后sum始终保持非负数， 就无序验证n个数的和是否一定为正数。这也跟题目有关，保证了有唯一解。

class Solution {
public:
    int canCompleteCircuit(vector<int> &gas, vector<int> &cost) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int sum=0;
        int total=0;
        int start=0;
        for(int i=0;i<gas.size();i++)
        {
            sum+=gas[i]-cost[i];
            total+=gas[i]-cost[i];
            if(sum < 0)
            {
                start=(i+1)%gas.size(); sum=0;
            }
        }
        
        if(total <0)
            return -1;
        else
            return start;
    }
};

方案三：

以某一结点为起始点i=begin，然后i++，如果sum为负数了，就begin--，并sum+s[begin]；当sum再为负数了，就begin--.....这样求解的话，也为线性时间复杂度。

解题思路：
1：假设出发车站为0，初始化车内油量0
2：车内油量＝车站油量－消耗
3：如果车内油量大于0，车开到下一车站，否则出发车站前移一个车站
重复2，3步，直到所有车站遍历完。如果车内油量剩余大于等于0，返回出发车站，否则返回－1.

public int canCompleteCircuit(int[] gas, int[] cost) {
		if (gas == null) {
			return -1;
		}
        // Note: The Solution object is instantiated only once and is reused by each test case.
		int count = gas.length;
		
		int n = 0;
		int gasInCar = 0;
		int begin = 0;
		int end = 0;
		int i = 0;
		while (n < count - 1) {
			gasInCar += gas[i] - cost[i];
			if (gasInCar >=0) {//forward
				end++;
				i=end;
			} else {
				begin--;
				if (begin < 0) {
					begin = count - 1;
				}
				i = begin;
			}
			
			n++;
		}
		
		gasInCar += gas[i] - cost[i];
		
		if (gasInCar >= 0) {
			return begin;
		} else {
			return -1;
		}
		
    }