134. gas station

Original link ：134. Gas station

 

solution:

        This topic first considers violent practices , Violence is to enumerate every point as a starting point , Judge whether it can go round the ring road , Time complexity O(n^2), It's bound to time out , The code of violent practices is posted below ：

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0, j; i < n;i++) {  //  Enumeration starting point 
            int left = 0;   // Recalculate the remaining oil volume from a new starting point 
            for (j = 0; j < n; j ++ ) {
                int k = (i + j) % n;
                left += gas[k] - cost[k];
                if (left < 0) break;    // Remaining oil is less than 0, Then jump out of this cycle 
            }
            if (j == n) return i;
        }
        return -1;
    }
};

        So we have to consider an effective method , Optimize violent practices . Consider this by assuming that the starting point is 0, When you enumerate to 4 At a gas station , Remaining oil is less than 0, Represents the starting point 0 You can't walk all the way to the gas station .
        If the practice of violence , Now I will definitely enumerate the 1 A gas station , And we optimize the code , Ask him to enumerate the number 5 Just a gas station .
        principle : With 0 As a starting point , After the first 1,2,3 At a gas station , The remaining oil volume must be greater than 0 Of , In this case, you can't go to the 4 A gas station , If the 1,2,3 As a starting point , The remaining oil volume is 0, Then it is even more impossible to finish .

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        for (int i = 0, j; i < n;) {  //  Enumeration starting point 
            int left = 0;   // Recalculate the remaining oil volume from a new starting point 
            for (j = 0; j < n; j ++ ) {
                int k = (i + j) % n;
                left += gas[k] - cost[k];
                if (left < 0) break;    // Remaining oil is less than 0, Then jump out of this cycle 
            }
            if (j == n) return i;
            i = i + j + 1;
        }
        return -1;
    }
};

        Double pointer ： Extend the ring to 2n Array

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int n = gas.size();
        vector<int> sum = vector<int> (n * 2, 0);
        // Solve the cost of each location 
        for(int i = 0;i < 2 * n;i++) {
            sum[i] = gas[i % n] - cost[i % n];
        }
        int start = 0,end = 0,tot = 0;  // The starting point , End , Current oil volume 
        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;
    }
};