ゼロから始めるLeetCode Day20 「134. Gas Station」

#概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。

その対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。

せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。

[Leetcode](https://leetcode.com/)

[ゼロから始めるLeetCode 目次](https://qiita.com/KueharX/items/6ee2502c3b620c795b70)

前回
[ゼロから始めるLeetCode Day19 「121. Best Time to Buy and Sell Stock」](https://qiita.com/KueharX/items/f89c2c1b7b15a10f86fc)

基本的にeasyのacceptanceが高い順から解いていこうかと思います。

20回続きました、飽き性の私にとっては珍しいことです。驚き。

[Twitter](https://twitter.com/kueharx)やってます。

# 問題
[134. Gas Station](https://leetcode.com/problems/gas-station/)

難易度は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`の値がマイナスになってしまった場合を管理するためです。それはすなわち完走できないということであり、その場合にどういった処理をするかがこの問題を解く上で大事な部分でしょう。

なお、私は以下のように書きました。

```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
        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っぽく書くなら

```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では

```Python
if tank < 0:
    return -1
else:
    return start
```

は

```Python
return -1 if tank < 0 else start
```

とイコールなので書き直してみました。
だいぶスッキリするので書けるならこちらの方が良いですね。

良さげな解法が他にあれば追記します。