题目描述

确实有N沿环形路线的加油站，在那里加油站的煤气量i是gas[i].

你有一辆有一个无限制油箱的车，而且费用很高。cost[i]从车站运来的汽油i到下一站(i+1)。你从一个加油站的空油箱开始旅程。

如果你能沿着顺时针方向绕电路一圈，返回启动加油站的指数，否则返回-1。

注：

• 如果存在解决方案，则保证该解决方案是唯一的。
• 两个输入数组都是非空的，长度相同.
• 输入数组中的每个元素都是一个非负整数.

样例

示例 1:

输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。
示例 2:

输入: 
gas  = [2,3,4]
cost = [3,4,3]

输出: -1

解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

C++ 代码1

class Solutio {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        if(gas.empty()||cost.empty())return -1;

        for(int i=0;i<gas.size();i++)
        {
            if(gas[i]>=cost[i])
                if(Dfs(gas,cost,i,gas[i]-cost[i],(i+1)%gas.size()))
                    return i;
        }

        return -1;

    }

    bool Dfs(vector<int>& gas, vector<int>& cost ,int start ,int cur ,int id)
    {
        if(id==start)return true;
        cur+=gas[id];
        if(cur>=cost[id])
            if(Dfs(gas,cost,start,cur-cost[id],(id+1)%gas.size()))
                    return true;
        return false;

    }
};

C++ 代码2

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {

        if(gas.empty()||cost.empty())return -1;
        int n=gas.size();
        for(int i=0,j;i<n;i+=j+1)
        {
            int cur=0;
            for(j=0;j<n;j++)
            {
                int k=(i+j)%n;
                cur+=gas[k]-cost[k];
                if(cur<0)
                    break; 
            }
            if(j>=n)
            {
                return i;
            }
        }
        return -1;
    }  
};