ゼロから始めるLeetCode Day69 「279. Perfect Squares」
概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
どうやら多くのエンジニアはその対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイトであり、海外のテックカンパニーでのキャリアを積みたい方にとっては避けては通れない道である。
と、仰々しく書いてみましたが、私は今のところそういった面接を受ける予定はありません。
ただ、ITエンジニアとして人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
Python3で解いています。
前回
ゼロから始める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なんですよね、不思議だ。
では今回はここまで。
お疲れ様でした。
コメント
コメントを投稿