[LeetCode] Gas Station

1. Total Gas you get must be more than the gas you cost
2. If the first rule is satisfied, there must be a point can be start point

gas  = [ 1,  2,  3,  4,  5,  1,  4,  2,  6,  2]
cost = [ 3,  4,  5,  1,  2,  8,  1,  0,  3,  1]
diff = [-2, -2, -2,  3,  2, -7,  3,  2,  3,  1]

for the example, there must be a legal point since total Gas you get must be more than the gas you cost

If we choose point where cost gas is bigger than gas we get ,we can’t move to next step

So we choose such as point 3, we can move to next step and still have remain gas.

However when we arrive at point 5, we’ll fail the this problem again.

so we need to look for a positive sequence which can afford next negative sequence after that. and then we can get complement in next positive sequence

in this case the start point should 6.

第一次嘗試用英文描述解題過程

看Code可能比較好懂我在講啥XD

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int tmp = 0;
        int sum = 0;
        int ss = -1;
        int len = gas.size();
        
        for (int i = 0; i < len; i++)
            sum += (gas[i]-cost[i]);
        
        if (sum < 0)
            return -1;
        else if(len == 1)
            return 0;
        
        for (int i = 0; i < len; i++) {
            int diff = gas[i] - cost[i];
            if (diff && tmp <= 0)
                ss = i;
            if (tmp >= -diff)
                tmp += diff;
            else 
                tmp = 0;
        }
        
        return ss;
    }
};