【LeetCode】134. Gas Station 解答・解説【Python】

はじめに
詳細
終わりに
1. 補足・参考・感想
2. 他の問題もどうぞ

はじめに

LeetCodeの問題を解答します。

なるべく、問題の和訳と詳細なコメントを書いています。

余裕があれば、複数のアプローチの解答と、実際の面接を想定して英語での解法やコメントを書いています。

これまでこのサイトでメモしてきた問題はこのページに全て載せています。

LeetCode 解答・解説記事一覧

二分探索、連結リストなど、テーマを絞って集中的に解きたい方は以下の記事が有用です。

LeeetCodeの問題をアルゴリズムとデータ構造による分類しました。

また、LeetCodeではAtcoderと違ってクラスと関数を定義して解答します。

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめています。

はじめてLeetCodeに触れる方はこちらの記事も役に立つと思います。

解答前に知っておくと役に立つかもしれない情報

詳細

問題

原文

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

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the i^th 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.

1
2
3
4
5
6
7
8
9
10

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.

1
2
3
4
5
6
7
8
9

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:

n == gas.length == cost.length

1 <= n <= 10⁵

0 <= gas[i], cost[i] <= 10⁴

内容(和訳)

n個のガスステーションが円状に並んでいます。i番目のガスステーションはgas[i]の値の燃料があります。

容量が無限の車を持っており、配列costのi番目の要素から次の要素へ行くには、cost[i]の値の燃料が必要です。あなたは燃料が空の状態でどれかのガスステーションから旅を始めます。

2つの配列gas,costが与えられます。もし、燃料切れを起こさずに一周できた場合は、スタート地点のインデックスを返してください。できない場合は-1を返してください。一周できる場合は解がただ一つであることが保証されます。

※正しくない可能性があります。

考察

・ガスステーションの数はn個なので、O(n^2)の時間計算量を要する方法では時間切れとなります。

・gasの合計がcostの合計より大きい場合は、必ず一周できるものとしてスタート地点を決める方法が思いつきます。

解答

解答1：Python

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #Check sum of gas is greater than sum of cost.
        if sum(gas) < sum(cost):
            #If the condition is true, return -1
            return -1
        #Is there a case where we cant circulate stations when sum of gas is greate than sum of cost?
        
        #Initilize the variables as values of zero.
        start, fuel = 0, 0
        #Start a for loop iterate over the range from 0 to length of gas.
        for i in range(len(gas)):
            #Add the result of subtranct between i-th element of gas and i-th element of cost to fuel.
            fuel += gas[i] - cost[i]
            #Check if fuel is less than zero.
            if fuel < 0:
                #If the condition is true, update start as next index of element and fuel as zero.
                start = i + 1
                fuel = 0
        #Return start
        return start

class Solution:

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:

#Check sum of gas is greater than sum of cost.

if sum(gas) < sum(cost):

#If the condition is true, return -1

return -1

#Is there a case where we cant circulate stations when sum of gas is greate than sum of cost?

#Initilize the variables as values of zero.

start, fuel = 0, 0

#Start a for loop iterate over the range from 0 to length of gas.

for i in range(len(gas)):

#Add the result of subtranct between i-th element of gas and i-th element of cost to fuel.

fuel += gas[i] - cost[i]

#Check if fuel is less than zero.

if fuel < 0:

#If the condition is true, update start as next index of element and fuel as zero.

start = i + 1

fuel = 0

#Return start

return start

初めに、gasの合計とcostの合計を比較しています。

costの合計の方がgasの合計よりも大きい場合、-1を返します。

※合計を比較するのは思いついたものの、costの合計の方が大きい場合に常に1周できないことを証明する方法があるのかが気になる。

下段のfor文ではスタート地点を決めます。

startはスタート地点を示すインデックス、fuelは残りの燃料。

現在の燃料に、i番目の給油量とi番目からi+1番目へ行くための消費量の差を加えます。

もし、燃料が0を下回ったらスタート地点をi+1番目に進め、残燃料を0にリセットします。

燃料が尽きない限りstart(スタート地点)は変わらないので、for文が終わればstartを返します。

解答2：Python, brute force, time limit exceeded

class Solution:
    def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
        #Initilize the variable candidates as list
        candidates = []
        #Collect elements that fulfill bellow condition.
        for i in range(len(gas)):
            #If the result of subtract between i-th element of gas and i-th element of cost 
            #is equal or greater than zero, the index is appended to candidates.
            if gas[i] - cost[i] >= 0:
                candidates.append(i)
        #Sort candidates as decreasing order.
        candidates.sort(reverse=True)
        
        #Check if each element can circulate gas station
        for i in range(len(candidates)):
            #Assign value 0 to the variable fuel
            fuel = 0
            #Assign i-th element of candidates to the varible "index".
            index = candidates[i]
            #Start a for loop iterate over the range from 0 to length of gas.
            for j in range(len(gas)):
                #Add the result of subtranct between gas[index] and cost[index].
                fuel += gas[index] - cost[index]
                #If amount of fuel is smaller than zero, break this itaration.
                if fuel < 0:
                    break
                #If amount of fuel is equal or greate than 0 and if index reach to the last elemenet,
                #Assing 0 to the variable index. This mean car moves to first element of "gas".
                elif index == len(gas)-1:
                    index = 0
                #If amount of fuel is equal or greate than 0
                #and if index dose not reach to the last elemenet,
                #increment index by one.     
                elif index != len(gas)-1:
                    index+=1
                #If the variable j reaches the last element of gas,
                #which indicates that the car has completed the circuit,
                #return the i-th element."                
                if j == len(gas)-1:
                    return candidates[i]
        #If None element couldn't complete the circuit, return -1
        return -1

class Solution:

def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:

#Initilize the variable candidates as list

candidates = []

#Collect elements that fulfill bellow condition.

for i in range(len(gas)):

#If the result of subtract between i-th element of gas and i-th element of cost

#is equal or greater than zero, the index is appended to candidates.

if gas[i] - cost[i] >= 0:

candidates.append(i)

#Sort candidates as decreasing order.

candidates.sort(reverse=True)

#Check if each element can circulate gas station

for i in range(len(candidates)):

#Assign value 0 to the variable fuel

fuel = 0

#Assign i-th element of candidates to the varible "index".

index = candidates[i]

#Start a for loop iterate over the range from 0 to length of gas.

for j in range(len(gas)):

#Add the result of subtranct between gas[index] and cost[index].

fuel += gas[index] - cost[index]

#If amount of fuel is smaller than zero, break this itaration.

if fuel < 0:

break

#If amount of fuel is equal or greate than 0 and if index reach to the last elemenet,

#Assing 0 to the variable index. This mean car moves to first element of "gas".

elif index == len(gas)-1:

index = 0

#If amount of fuel is equal or greate than 0

#and if index dose not reach to the last elemenet,

#increment index by one.

elif index != len(gas)-1:

index+=1

#If the variable j reaches the last element of gas,

#which indicates that the car has completed the circuit,

#return the i-th element."

if j == len(gas)-1:

return candidates[i]

#If None element couldn't complete the circuit, return -1

return -1

こちらは、時間切れになった解答です。

時間計算量：O(n^2)、空間計算量：O(n)になります。

i番目の給油量と消費量が0よりも大きい場合のガスステーションを集め、1つずつ一周できるかを確認する方法です。

brute forceで考えてみたかったので、一応メモとして書き残しておきます。

終わりに

補足・参考・感想

問題を分類しました。テーマごとに集中して問題を解くことができます。

LeeetCodeの問題をアルゴリズムとデータ構造による分類

LeetCodeに特有の内容など、知っておくと役に立つかもしれないことをまとめました。

解答前に知っておくと役に立つかもしれない情報

他の問題もどうぞ

前：45. Jump Game II

次：

LeetCode 解答・解説記事一覧