概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day19 「121. Best Time to Buy and Sell Stock」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
20回続きました、飽き性の私にとっては珍しいことです。驚き。
Twitterやってます。
問題
難易度はMedium。
Top 100 Liked Questionsの一つです。
解いてて非常に面白い問題だったのでぜひ解いてみてください。
ガソリンの給油量gasとその地点に移動するまで消費するガソリンの量を示したcostの二つのリストが与えられます。
それらに加えてあなたは無限大の容量を持つガソリンタンクを備えた車を与えられました。
ステーションiから次のステーション(i+1)まで移動するにはcost[i]がかかります。スタート時点でのガソリンタンクは空であり、仮に時計回りに1週巡回で場合は開始ステーションのインデックスを返し、それ以外の場合は-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.
ステーション3から始めた場合の例です。
開始時点でのガソリンの保有量はステーション3のgasが3なので3スタートですね。その地点から仮に1終始て戻ってきてもできるのでこの場合はステーション3のインデックスである3を返します。
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.
解法
ひとまず変数候補として必要なのは、ガソリンの量を管理するtank、仮に完走できた場合に開始地点を示すstart、そして現在地点でのガソリンの保有量を示すcurの3つの変数。
tankとcurを分けたのには仮にcurの値がマイナスになってしまった場合を管理するためです。それはすなわち完走できないということであり、その場合にどういった処理をするかがこの問題を解く上で大事な部分でしょう。
なお、私は以下のように書きました。
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
tank,start,cur = 0,0,0
for i in range(len(gas)):
cur += (gas[i] - cost[i])
tank += (gas[i] - cost[i])
if cur < 0:
cur = 0
start = i + 1
if tank < 0:
return -1
else:
return start
# Runtime: 56 ms, faster than 53.48% of Python3 online submissions for Gas Station.
# Memory Usage: 14.6 MB, less than 6.25% of Python3 online submissions for Gas Station.
for文で回す中で、ifによるcurのチェックをし、仮にマイナスであればcurに0を代入し、startにi+1を代入するという処理を加えることで正しい開始位置がインデックスとして返されるようにしました。
通った後に思ったのですが、この文では最後の分岐が少し冗長ですね。
Pythonっぽく書くなら
class Solution:
def canCompleteCircuit(self, gas: List[int], cost: List[int]) -> int:
tank,start,cur = 0,0,0
for i in range(len(gas)):
cur += (gas[i] - cost[i])
tank += (gas[i] - cost[i])
if cur < 0:
cur = 0
start = i + 1
return -1 if tank < 0 else start
# Runtime: 52 ms, faster than 76.94% of Python3 online submissions for Gas Station.
# Memory Usage: 14.9 MB, less than 6.25% of Python3 online submissions for Gas Station.
Pythonでは
if tank < 0:
return -1
else:
return start
は
return -1 if tank < 0 else start
とイコールなので書き直してみました。
だいぶスッキリするので書けるならこちらの方が良いですね。
良さげな解法が他にあれば追記します。