ゼロから始めるLeetCode Day5 「1266. Minimum Time Visiting All Points」

概要

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

どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。

早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。

と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。

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

Leetcode

Python3で解いています。
Twitterやってます。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day4 「938. Range Sum of BST」
次回
ゼロから始めるLeetCode Day6 「1342. Number of Steps to Reduce a Number to Zero」

問題

1266. Minimum Time Visiting All Points

リストでx軸とy軸の座標が複数与えられるのでその全ての座標へ訪れるための最短時間を求めよ、という問題ですね。

なお、ルールとして、
1秒間に、垂直方向、水平方向に、または斜めに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.

ただ、こちらは少し遅いですね。

スタックの勉強も兼ねて前者のような実装をした方が勉強になって良さげですね。

コメント

このブログの人気の投稿

Braveブラウザの同期機能をiPhoneで設定した話。

failed: unable to get local issuer certificate (_ssl.c:1123)と出たので解決した話

自作のChrome Extensionをインポートした時に "Invalid value for 'content_scripts[0].matches[0]': Empty path."というエラーが出たので解決した