Medium
Related Topics: Array / Greedy
LeetCode Source

解題想法

這題是看之前解的方法

Python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        index, car = 0, 0
        total = sum(gas) - sum(cost)

        for i in range(len(gas)):
            car += gas[i] - cost[i]
            
            if car < 0:
                index = i + 1
                car = 0
        
        if total >= 0:
            return index
        else:
            return -1

C++

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        int res = 0, car = 0, total = accumulate(gas.begin(), gas.end(), 0) - accumulate(cost.begin(), cost.end(), 0);
        for (int i = 0; i < gas.size(); i++) {
            car += gas[i] - cost[i];

            if (car < 0) {
                car = 0;
                res = i + 1;
            }
        }

        if (total >= 0) return res;
        return -1;
    }
};

accumulate(gas.begin(), gas.end(), 0) 可以把 gas 的值加總，初始值是 0

這系列文被記錄在 Top Interview 150 Series