- Total Gas you get must be more than the gas you cost
- 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; } };