概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
前回
ゼロから始めるLeetCode Day4 「938. Range Sum of BST」
問題
1266. Minimum Time Visiting All Points
リストでx軸とy軸の座標が複数与えられるのでその全ての座標へ訪れるための最短時間を求めよ、という問題ですね。
なお、ルールとして、
1秒間に、垂直方向、水平方向に、または斜めに1単位移動できる。
与えられた順番と同様の順番に座標に到達する必要がある
という制約があります。
例１をみると、グラフの最短経路の出し方なんて知らんし・・・となってしまうかもしれませんが、この問題でとりあえず解けるようにするための重要な考え方としては、最短経路を求めるには単純にそれぞれの与えられた座標からより差が大きい方の数値から引けば良いという点です。
ここで大事なのは差をそのまま取得するのではなく、絶対値を取得するということです。
Pythonには組み込み関数でabs()があるのでそれを使うだけで大丈夫です。
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
sec = 0
x1,y1 = points.pop()
while points:
x2,y2 = points.pop()
sec += max(abs(x2-x1),abs(y2-y1))
x1,y1 = x2,y2
return sec
# Runtime: 56 ms, faster than 84.71% of Python3 online submissions for Minimum Time Visiting All Points.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Minimum Time Visiting All Points.
まずsecですが、secondの略で、移動時間の加算のための変数を用意します。
そして今回はスタックのpopを使いました。
Pythonのpopは引数を指定しない場合、末尾（最後）の要素を削除します。
解答のテストケースでは[[1,1],[3,4],[-1,0]]が使われているので、この場合はx1,y1には-1,0が代入され、x2,y2には3,4がそれぞれ代入されます。
そしてそれぞれx2からx1を、y2からy1を引いた後、大きい方の数値を抽出するためにmax関数を使い、secに代入します。
その後にx1,y1にx2,y2を代入し、それをpointsの要素数がなくなるまでループさせ、最後に差の最大値の総和であるsecを返す、という関数です。
以上のようにシンプルな答えにまとまったと思います。
また、for文での回答も作れます。
class Solution:
def minTimeToVisitAllPoints(self, points: List[List[int]]) -> int:
sec = 0
current = points[0]
for point in points[1:]:
sec += max(abs(current[0] - point[0]), abs(current[1] - point[1]))
current = point
return sec
# Runtime: 64 ms, faster than 32.15% of Python3 online submissions for Minimum Time Visiting All Points.
# Memory Usage: 13.9 MB, less than 100.00% of Python3 online submissions for Minimum Time Visiting All Points.
ただ、こちらは少し遅いですね。
スタックの勉強も兼ねて前者のような実装をした方が勉強になって良さげですね。