leetcode 134.加油站

本题运用暴力的形式确实是可以的，但是在于暴力的话会非常的麻烦，需要在循环中不断的判断特殊条件。

这里需要用到贪心的算法：

首先我们可以想，既然我们已经知道了在当前加油站的加油量和从当前加油站到下一个加油站耗费的油量，也就是说，我们从第0个站台开始，一直往后遍历一边，计算出我们在油箱为0的情况下到底能走多少路。

如果当前你走到了第i个站台，这里如果显示你当前的油量是<0的，那么证明你并不能从第0个站台到现在这个站台，所以你只能在i+1个站台开始走，然后将这前面计算的油量清零，一直这样下去。

有两个问题：

1.如果后面还会出现负数怎么办呢？这样的话我们到底选择哪个呢？我的答案是你就选刚开始的哪个位置就行，因为我们是从局部最优推算到全局最优当中，反正我们从头到尾就推算出来了你要起始的起点至少是i+1位，这个结论是固定的。

2.如果说在我们之前抛弃的那个区间里面选择了一个起始点，到了第i个站点不会出现<0的情况怎么办呢？

这里需要着重强调一点，当我们在全局的剩余油量<0时，这可以说是无论如何你跑哪个位置都不能跑完一圈。假设在这种情况下，[0,i][i+1,n]区间的剩余油量相加一定是<0，也就是说一个区间大于零，一个区间就必须小于零。这是不可避免的。

至少是i+1个位置就是这样的。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n=gas.size();
        int num1=0;
        int num2=0;
        int begins=0;
        for(int i=0;i<n;i++){
            num1+=gas[i]-cost[i];
            num2+=gas[i]-cost[i];
            if(num1<0){
                begins=i+1;
                num1=0;
            }
        }
        if(num2<0)
        return -1;
        else
        return begins;
    }
};

暴力解法需要揭示一点，就是对于环形循环的话运用while是比较好的，这样会更方便。

下面是暴力解法，虽然不能过，但是凑活着看吧：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int shengyu=0;
        int index=0;
        int n=gas.size();
        for(int i=0;i<n;i++){
            shengyu=gas[i]-cost[i];
            index=(i+1)%n;
            while(shengyu>0&&index!=i){
                shengyu+=gas[index]-cost[index];
                index=(index+1)%n;
            }
            if(index==i&&shengyu>=0)
            return index;
        }
        return -1;
    }
};