134. 加油站

原题链接：134. 加油站

 

solution:

        本题先考虑暴力做法,暴力做法就是枚举每一个点为起点,判断它能否绕环形路一周,时间复杂度O(n^2)，肯定会超时,下面贴上暴力做法代码：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0, j; i < n;i++) {  // 枚举起点
            int left = 0;   //新的起点重新计算剩余油量
            for (j = 0; j < n; j ++ ) {
                int k = (i + j) % n;
                left += gas[k] - cost[k];
                if (left < 0) break;    //剩余油量小于0,则跳出本次循环
            }
            if (j == n) return i;
        }
        return -1;
    }
};

        于是得考虑一种有效的方法,对暴力做法进行优化。可以这样考虑假设起点为0，当你枚举到第4个加油站的时候,剩余油量小于0,代表以起点0的加油站不能走完整个路程。
        如果按照暴力的做法,现在肯定会去枚举第1个加油站，而我们对代码进行优化,让他直接去枚举第5个加油站就行了。
        原理:以0为起点,经过第1,2,3个加油站的时候,剩余油量肯定都是大于0的,在这种情况下都无法走到第4个加油站,如果以1,2,3为起点,剩余油量为0，那就更不可能走完了。

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0, j; i < n;) {  // 枚举起点
            int left = 0;   //新的起点重新计算剩余油量
            for (j = 0; j < n; j ++ ) {
                int k = (i + j) % n;
                left += gas[k] - cost[k];
                if (left < 0) break;    //剩余油量小于0,则跳出本次循环
            }
            if (j == n) return i;
            i = i + j + 1;
        }
        return -1;
    }
};

        双指针：将环形扩展到2n数组

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        vector<int> sum = vector<int> (n * 2, 0);
        //求解每个位置的花费
        for(int i = 0;i < 2 * n;i++) {
            sum[i] = gas[i % n] - cost[i % n];
        }
        int start = 0,end = 0,tot = 0;  //起点,终点,当前油量
        while(start < n && end < 2 * n) {
            tot += sum[end];

            while(tot < 0) {
                tot -= sum[start];
                start++;
            }

            if(end - start + 1 == n) return start;
            end++;
        }
        return -1;
    }
};