[LeetCode] 134. Gas Station

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