If car starts at A and can not reach B. Any station between A and B can not reach B.(B is the first station that A can not reach.) If the total number of gas is bigger than the total number of cost. There must be a solution.
| 21 | //If car starts at A and can not reach B. Any station between A and B can not reach B.(B is the first station that A can not reach.) |
| 22 | //If the total number of gas is bigger than the total number of cost. There must be a solution. |
| 23 | int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { |
| 24 | n = gas.size(); |
| 25 | for (int i = 0; i < n; ) { |
| 26 | if (gas[i] < cost[i]) { i ++ ; continue; } |
| 27 | int dst = i, j = next(i), rg = gas[i] - cost[i]; |
| 28 | while (j != dst) { |
| 29 | rg += gas[j] - cost[j]; |
| 30 | if (rg < 0) break; |
| 31 | j = next(j); |
| 32 | } |
| 33 | if (j != dst) { |
| 34 | if (j < i) break; |
| 35 | else { |
| 36 | i = j; |
| 37 | continue; |
| 38 | } |
| 39 | } |
| 40 | else return i; |
| 41 | } |
| 42 | return -1; |
| 43 | } |
| 44 | }; |
| 45 | |
| 46 | int main() { |
nothing calls this directly
no outgoing calls
no test coverage detected