Gas Stations

数组越界

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        //依次从每一个加油站出发
        for (int i = 0; i < gas.size(); i++) {
            int j = i;
            int curgas = gas[j];

            while (curgas >= cost[j]) { //如果当前的汽油量能够到达下一站
                curgas -= cost[j];      //减去本次的消耗

                // 这一行是重点， 我自己的是 j=(i+1)%gas.size(), 混了i，j造成了逻辑混乱
                j = (j + 1) % gas.size(); //到达下一站
                if (j == i) return i;   //如果回到了起始站，那么旅行成功

                curgas += gas[j];       //到下一站后重新加油，继续前进
            }
        }
        return -1;
    }
};

First Try

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        bool goal = false;
        for (int i = 0; i < gas.size(); i++) {
            tank = gas[i];

            //这种逻辑混乱了，j和i混在一起，有两个问题
            //1, cost[(j-1)%n] 当j=0时为-1，错
            //2, 如何跳出错误循环，逻辑设计太复杂
            // 这两个问题被上面的解法用j=i，模拟从i出发，完美解决，在实验第i个的时候应该用一个单独的变量独立测试
            bool run = false;
            if (tank > cost[i]) {
                for (j = (i+1)%gas.size(); j++) {
                    tank = tank - cost[(j-1)%gas.size(); + gas[j];
                    if ( tank < cost[j] ) {
                        run = false;
                        break;
                    }
                }
            }
        }
};

Second Solution

Need Prove

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int sum = 0;
        int total = 0;
        int j = -1;
        for (int i = 0; i < gas.size(); i++) {
            sum += gas[i] - cost[i];
            total += gas[i] - cost[i];
            if(sum < 0) {   //之前的油量不够到达当前加油站
                j = i;
                sum = 0;
            }
        }
        if (total < 0) return -1;    //所有加油站的油量都不够整个路程的消耗
        else return j + 1;
    }
};