134. Gas Station

1.問題

• 在這個加油站可以補充gas[i], 但到下個加油站時將會消耗cost[i], 請問從哪個點出發可以順利順時針旅行一圈回到原本的加油站?

2.想法

• 提問

• function header, parameter

• test input

• 觀察

  • 選擇出發的加油站

  • 環遊一圈

• 說明想法

• 測試計算複雜度

3.程式碼

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        if (gas.empty() || 
            cost.empty() ||
            gas.size() != cost.size()){
            return -1;
        }
        int size = gas.size();
        for (int i = 0 ; i < size; i++) {
            if (gas[i] - cost[i] >= 0) {
                int start = i;
                int val = 0, cnt = 0;
                while (val >= 0) {
                    if (cnt == size) {
                        return i;
                    }
                    val += gas[start];
                    val -= cost[start];
                    start = (start + 1) % size;
                    cnt++;
                }
            }
        }
        
        return - 1;
    }
};