检查是否有沿圆形路线的加油站，CPP中带说明的解决方案

沿循环路线有N个加油站，其中加气站i的气体量为gas [i]。

您有一辆带无限油箱的摩托车，从第i站到下一个（i + 1）的行车成本为[i]。您可以从其中一个加油站的空罐开始旅程。

返回起始加油站’s索引，如果您可以沿顺时针方向绕过电路一次，则返回-1。

Example 1:

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

Output: 3

Explanation:
Start from station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
From then go to station 4. Current tank = 4 - 1 + 5 = 8
From then go to station 0. Current tank = 8 - 2 + 1 = 7
From then go to station 1. Current tank = 7 - 3 + 2 = 6
From then go to station 2. Current tank = 6 - 4 + 3 = 5
From then go to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

由于该解决方案是唯一的，因此我们可以得出一个结论，如果我们无法到达下一个站点，那么我们将从下一个站点开始并检查是否存在解决方案。

要到达下一个车站，我们应该加油。如果没有燃料，那么我们将从下一个站开始。

要记住的一些要点是：
1.如果煤气的总和大于成本的总和，则存在唯一的解决方案。
2.储罐不应为负，如果为负，则从储罐变为负的位置重新开始路径。

因此，这可以在O（n）时间内完成。

C ++解决方案

#include<iostream>
#include<vector>

using namespace std;
int canCompleteCircuit(vector<int>& gas, vector<int>& cost) 
{
    int tank=0;		// Current gas value
    int total=0; 	// To store the value of current_gas - cost + next_gas 
    int start=0; 	// Start station

    for(int i=0; i<gas.size(); i++) 
    {
        int current = gas[i]-cost[i];
        tank += current;
        total += current;
        if(tank < 0) 
        {
            start = i+1;
            tank = 0;
        }
    } 
    return total < 0 ? -1 : start;
}


int main()
{
	vector<int> gas;
	gas.push_back(1);
	gas.push_back(2);
	gas.push_back(3);
	gas.push_back(4);
	gas.push_back(5);

	vector<int> cost;
	cost.push_back(3);
	cost.push_back(4);
	cost.push_back(5);
	cost.push_back(1);
	cost.push_back(2);

	int result = canCompleteCircuit(gas, cost);

	if(result)
		cout<<"There is a path, the starting station is = "<< result<<endl;
	else
		cout<<"There is no path"<<endl;


	return 0;
}

输出：

There is a path, the starting station is = 3

该网站上可用的教程列表：