Skip to content

LeetCode: 134-Gas Station 解題紀錄

Last Updated on 2022-01-21 by Clay

題目

There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.

Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique

Example 1:

Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Constraints:

  • gas.length == n
  • cost.length == n
  • 1 <= n <= 105
  • 0 <= gas[i], cost[i] <= 104

題目給定加油站的加油量列表、以及旅途所耗費的汽油量列表，我們要計算從哪一站開始旅行可以將所有的路徑跑完一圈（當然如果油量歸零卡車就無法再跑了）。

每題最多只會有一個站點可以跑完整圈，此時返回起站的索引值；如果無法跑完整圈，則返回 -1。

解題思路

一開始我想得很複雜，各種遍歷與刪減合併列表，紀錄起始點...... 但無論如何都卡在一筆很長的零列表測試 TLE。

最後才想到，這題其實適用於 https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ 這題的解法，可以參考我當時的紀錄：LeetCode: 121-Best Time to Buy and Sell Stock 解題紀錄

簡單來說，我們從起點開始遍歷，並同時紀錄總值 sum_total 以及當前累積值 sum。

在第 i 個站點，無論 sum_total 還是 sum 都要加上 gas[i] 並減去 cost[i]；接著判斷 sum 是否小於零，如果小於的情況，則紀錄的可能起點就不可能是可以跑完整圈的起點，將可能的起點更新為 i+1 並把當前累積值 sum 歸零重新開始計算。

在遍歷完整圈後，如果總值 sum_total 大於等於零，則存在著可以跑完整圈的解答，回傳紀錄著的可能起點；如果小於零，自然就代表無論如何都跑不完，回傳 -1。


複雜度

Time ComplexityO(n)
Space ComplexityO(1)


C++ 範例程式碼

class Solution {
public:
    int canCompleteCircuit(vector<int>& gas, vector<int>& cost) {
        // Init
        int total_sum = 0;
        int sum = 0;
        int startpoint = 0;
        
        for (int i=0; i<gas.size(); ++i) {
            total_sum = total_sum + gas[i] - cost[i];
            sum = sum + gas[i] - cost[i];
            
            if (sum < 0) {
                startpoint = i+1;
                sum = 0;
            }
        }
        
        return total_sum >= 0 ? startpoint : -1;
    }
};



Python 範例程式碼

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        # Init
        sum_total = 0
        _sum = 0
        startpoint = 0
        
        for i in range(len(gas)):
            sum_total = sum_total + gas[i] - cost[i]
            _sum = _sum + gas[i] - cost[i]
            
            if (_sum < 0):
                _sum = 0
                startpoint = i + 1
            
        if sum_total >= 0: return startpoint
        else: return -1

References

Read More

Tags:

Leave a Reply