ゼロから始めるLeetCode Day69 「279. Perfect Squares」

-

概要

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

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

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

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

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

Leetcode

Python3で解いています。

ゼロから始めるLeetCode 目次

前回
ゼロから始めるLeetCode Day68 「709. To Lower Case」

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

Twitterやってます。

問題

279. Perfect Squares
難易度はMedium。
Top 100 Liked Questionsからの抜粋です。

正の整数nが与えられたとき、足してnになる完全な平方数の最小数（例えば、1, 4, 9, 16, …）を求めよ、という問題です。

Example 1:

Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.

Example 2:

Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.

#解法

class Solution:
    def numSquares(self, n: int) -> int:
        dp = [i for i in range(n+1)]
        for i in range(2,n+1):
            for j in range(1,int(i ** 0.5)+1):
                dp[i] = min(dp[i],dp[i-j*j]+1)
        return dp[n]
# Runtime: 4608 ms, faster than 39.65% of Python3 online submissions for Perfect Squares.
# Memory Usage: 14 MB, less than 60.54% of Python3 online submissions for Perfect Squares.

動的計画法を使って実装しました。
問題をみた時にあー・・・これDPや・・・ってなりました。
値が小さければ全探索でもいけますが、どう考えても効率が悪いので以上のように書いています。

なお、個人的なQiitaの記事の動的計画法のおすすめとして
動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集
とPythonでの実装において
動的計画法 (Dynamic Programming：DP) 学習メモ　～by Python～　Part 1

が良い例じゃないでしょうか。
前者で概念を掴んで、後者でPythonでの実装について学ぶ、という方式が良いと思います。

そういえば日本語では動的計画法なのに英語ではDynamic Programmingなんですよね、不思議だ。

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

コメント

コメントを投稿

このブログの人気の投稿

Braveブラウザ(iPhone,iPad)にオフラインでもYouTubeの動画が視聴可能なPlaylist機能が追加されていたので使い方をまとめてみた。

-
イメージ
アップデートしたら使えるようになっていた 公式 からリリースされている通り、 BraveのiPhoneとiPadアプリのユーザーは、 新機能「Playlist」 を、 v1.25版 から利用可能になりました。これはユーザーが動画・音声コンテンツを好きなプラットフォームから保存し、楽しめるようにする機能です。Brave Playlistを使うと、ユーザーは複数のプラットフォームから選んだコンテンツを1つのプレイリストに保存して、いつでも、どこでもアクセスできます。音楽、動画、ポッドキャストなどを、通勤や旅行、日常生活で楽しむのに最適な機能です。 オフライン でYouTubeの動画を手元にダウンロードし、どこでも視聴可能になる機能が今回のアップデートで追加されました。 いやいや、これ相当便利ですね。 Braveを使っている方なら、Braveを通してYouTubeを視聴すれば広告を見なくて済むということを知ってらっしゃるとは思うのですが、まさかオフラインでも視聴可能になるとは・・・ AdBlockなどを活用すれば他のブラウザでも広告をブロックすること自体はできたのですが、まさか無償でブラウザ側が実装してくれるとは！ ただ、広告収入をメインにしているYouTube側から規制されそうな気もしますが・・・ どうなんでしょうか？ ちなみにこの機能、よくみたら5日前の段階でリリースされていたようなのですが、チェックできていなかったので先ほどアップデートをしたときに驚きました。 使い方 直感的に使えるので、すぐに使い方は分かるようになるかと思います。 1. YouTubeを開く 2.保存したい動画を開く。この時、画面下部に「Brave Playlistに追加する」と表示されるのでタップ。 3.画面右下の「・・・」をタップし、表示されたPlaylistをタップ 4.ダウンロードが始まっているので、完了するまで待つ。 5.ダウンロードが完了次第いつでもどこでも楽しめるように！ これで完了です。 例えば機内モード(左上の飛行機マークに注目してください)にしたとしても問題なく動画は再生されます。 これで広告無し、しかもオフラインでもYouTubeを楽しめるようになりました！
続きを読む

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

-
イメージ
タイトル通りのエラーが出た。 Chromeの拡張機能を作っていたところ試しに作った拡張機能をインポートした時にエラーが出た。 調べてみるとmanifest.jsonでエラーが起こっているようで、タイトルのように、"Invalid value for 'content_scripts[0].matches[0]': Empty path."と表示されている。 manifest.jsonの中に書いたmatchesのインデックスの0番目がどうやら空のパスになっているらしい。 ちなみにmanifest.jsonは設定ファイルのようなもので、ここで定義している 'content_scripts[0].matches[0]'はGoogleのURI。 { "name" : "Example Extension" , "version" : "1.0.0" , "manifest_version" : 2 , "description" : "Sample Extension" , "content_scripts" : [ { "matches" : [ "https://www.google.com" ] , "js" : [ "content.js" ] } ] } という内容で、このディレクトリには他に content.js のみ。 なんぞやということで色々調べてみると単純に末尾にスラッシュが足りなかっただけのよう。 { "name" : "Example Extension" , "version" : "1.0.0" , "manifest_version" : 2 , "description" : "Sample Extension" , "content_scrip...
続きを読む

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ブラウザを開き、画面右下の**•••**という所をタップしてください。 すると上から二番目に歯車アイコンの設定が表示されますのでそちらをタップします。 初期表示で画面中部に表示さ...
続きを読む