スキップしてメイン コンテンツに移動

ゼロから始めるLeetCode Day71 「1496. Path Crossing」

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day70 「295. Find Median from Data Stream」

次回
ゼロから始めるLeetCode Day72 「1498. Number of Subsequences That Satisfy the Given Sum Condition」

Twitterやってます。

問題

1496. Path Crossing

難易度はEasy。
一番新しく追加されたEasyの問題です。

問題としては、path[i] = ‘N’, ‘S’, ‘E’, ‘W’ のような文字列のパスが与えられたとき,それぞれ1単位の移動を表す.2 次元平面上の原点 (0, 0) を起点とし、path で指定されたパス上を歩きます。
パスが任意の点で交差している場合、つまり以前に訪れたことのある場所にいる場合はTrueを返します。それ以外の場合は False を返します。

画像の関係で例を貼れないので各自確認をよろしくお願いいたします。

解法

x,yで座標を管理して最初の座標をdictで管理する、という方法を取りました。
うーん。
あまりスマートではないと思うのですが、pathをfor文で回して各文字列と一致するならば座標を変更するというものです。
しかしこれでも回答数が少ないせいかスピード自体は上位なんですよね・・・
何とも言えませんがとりあえず今回はこれで。

class Solution:
    def isPathCrossing(self, path: str) -> bool:
        x = y = 0
        isVisited = {(0,0):True}
        for i in path:
            if i == 'N':
                y += 1
            elif i == 'E':
                x += 1
            elif i == 'S':
                y -= 1
            else:
                x -= 1
            if isVisited.get((x,y)):
                return True
            isVisited[(x,y)] = True
        return False
# Runtime: 24 ms, faster than 96.92% of Python3 online submissions for Path Crossing.
# Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Path Crossing.

Javaとかだとswitch文とかで書くのがいいのでしょうか・・・?
今回は新しい問題という事でdiscussにも投稿してみました。
Simple Python Solution

緊張しますがこういうのやるともっと頭の良い人からアドバイスがもらえたりしていいですよね!

では今回はここまで。お疲れ様でした。

コメント

このブログの人気の投稿

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

Braveブラウザを使い始めて結構経った 設定 1 .同期ページを開く 2.QRコードの表示 3.iPhoneで読み取る Braveブラウザを使い始めて結構経った Google Domainsで独自ドメインを持っているBloggerをBrave Creatorsに登録した話。 この記事を書いた頃から僕はBraveしか使わなくなっちゃいましたね〜。 広告がないとネットサーフィンが捗りますし、Braveの直接クリエイターに貢献できるような仕組みが特に気に入っています。Blogger,ひいてはGoogle的にどうなんだって話もありそうですけど、ただのユーザなのでそんなのは気にせず便利なものは使います。 それで本題です。 タイトルのように今回同期機能を設定しました。 余計なことをしていたせいで少しハマったので設定ついでに誰かが困ったときに役に立つように設定方法を残しておこうかと思います。 ちなみにこちらの記事はPCの同期にiPhoneを追加するという設定方法についての解説です。iPhone→PCの同期方法などはまた別の話のようです。 設定 1 .同期ページを開く ブラウザのタブの右上にある上矢印のマークをクリックすると以下のような項目が表示されます。 こちらの同期という欄をクリックします。 すると以下のページが表示されます。 自動的に設定ページの中の同期欄が表示されるわけですね。 2.QRコードの表示 同期欄に同期済みのデバイスを管理という欄があるのでそちらをクリックします。 すると以下のようなページが表示されるのでそちらの中の新たなデバイスを追加、スマホ/タブレットという順にクリックしていくとQRコードが表示されます。 これでこのステップは完了です。 3.iPhoneで読み取る このQRコードをiPhoneで読み取っていく訳ですが、このQRコードはプリインストールされているQRコードで読み取っても正しく処理してくれません。 書いてある通り、iPhoneのBraveブラウザで読み取って上げる必要があります。 なのでひとまずiPhoneでBraveブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ

JavaのindexOf関数はナイーブ法で実装されているらしい

indexOf関数とは 実際のソースを見よう ナイーブ法ってなんぞや indexOf関数とは ドキュメント はここ。 indexOf の細かい使い方は説明はしないが、簡単にいうと二つの文字列を比較して重複する箇所がある場合にその開始部分のインデックスを返すというもの。 実際のソースを見よう どのように実装されているのかが気になったので jdkの中に存在するsrc.zipを解凍して確認してみることに。 public int indexOf ( String str ) { return indexOf ( str , 0 ) ; } public int indexOf ( String str , int fromIndex ) { return indexOf ( value , 0 , value . length , str . value , 0 , str . value . length , fromIndex ) ; } static int indexOf ( char [ ] source , int sourceOffset , int sourceCount , char [ ] target , int targetOffset , int targetCount , int fromIndex ) { if ( fromIndex >= sourceCount ) { return ( targetCount == 0 ? sourceCount : - 1 ) ; } if ( fromIndex < 0 ) { fromIndex = 0 ; } if ( targetCount == 0 ) { return fromIndex ; } char

djoserを使ったDjango REST Frameworkでのカスタムユーザーモデル認証機能の実装

djoserとは 使い方 djoserとは djoser とはDjango REST Framework上での基本的なユーザー認証や登録などの認証周りをサポートしてくれるライブラリです。 カスタムモデルに対しても使え、Djangoのコードを再利用するような形をとるのではなく、Single Page Application(以下SPA)によりフィットするようなアーキテクチャを目指して作られています。 今回はdjoserの最もシンプルな認証機能の実装について書きます。 なお、この認証はセキュリティの面などから実際に使用するべきではなく、以下のJWT認証のようなより強固なセキュリティの設定があります。 あくまでお手軽な認証として紹介します。 ソースコードは こちら なお、以下の全てが導入後にエンドポイントとして使えます。 /users/ /users/me/ /users/confirm/ /users/resend_activation/ /users/set_password/ /users/reset_password/ /users/reset_password_confirm/ /users/set_username/ /users/reset_username/ /users/reset_username_confirm/ /token/login/ (Token Based Authentication) /token/logout/ (Token Based Authentication) /jwt/create/ (JSON Web Token Authentication) /jwt/refresh/ (JSON Web Token Authentication) /jwt/verify/ (JSON Web Token Authentication) Getting started djoser関連の記事を他にも書いています。 djoserを使ったDjango REST Frameworkでの認証機能の実装 djoserを使ったDjango REST FrameworkでのJWT認証機能の実装 なお、今回はJWT認証を用いたユーザー認証を実装することとします。 使い方 途中