概要
海外ではエンジニアの面接においてコーディングテストというものが行われるらしく、多くの場合、特定の関数やクラスをお題に沿って実装するという物がメインである。
その対策としてLeetCodeなるサイトで対策を行うようだ。
早い話が本場でも行われているようなコーディングテストに耐えうるようなアルゴリズム力を鍛えるサイト。
せっかくだし人並みのアルゴリズム力くらいは持っておいた方がいいだろうということで不定期に問題を解いてその時に考えたやり方をメモ的に書いていこうかと思います。
前回
ゼロから始めるLeetCode Day24 「21. Merge Two Sorted Lists」
基本的にeasyのacceptanceが高い順から解いていこうかと思います。
Twitterやってます。
問題
70. Climbing Stairs
難易度はeasy。
Top 100 Liked Questionsからの抜粋です。
中学受験をしたことある人には見覚えがある問題だと思います。
実はすごく簡単な解き方があるのですが、それは解法で説明します。
階段を登る時、1段か2段登れます。
自然数nが与えられるので頂上に辿り着くまでの方法が何通りあるかを答えなさい。
Example 1:
Input: 2
output: 2
2の場合、一気に2段あがる方法と1段を2回登る方法があるので2を返します。
Example 2:
Input: 3
Output: 3
3の場合は1段づつ上がるのを3回繰り返す、1段上がって2段あがる方法、2段上がって1段あがる方法の3通りあるため3を返します。
解法
実はこれフィボナッチ数列の問題なんですよね。
場合の数の勉強をしていた時に見たことがある人もいるかもしれません。
ちなみにフィボナッチ数列というのは、
１,１,２,３,５,８,１３,２１,３４,５５,
といったように、前の２つの数の和が次の数になる数列です。
例のように3段だった場合を考えてみましょう。
この場合、最初の段階での場合分けによって大きく変わります。
1段登るか2段登るかパターンがありますよね。
仮に2段登った場合、その後の選択肢は残りの階段数が1のため、必然的に1通りとなります。
対して1を選んだ場合は残りが2段、つまり例にあるように2通りです。
これらを足し算したときの和が場合分けの答えとなり、これこそが上記のようなフィボナッチ数列の典型的な例なのです。
他の数字でも試してみましょう。
仮に4段だとしましょう。
すると最初に1段と最初に2段選びます。
最初に1段の場合ですが、残りは3段です。つまり先ほどの3段の時の3通りをそのまま使えます。
そして2段の場合だと残りは2段です。つまりは2通りです。
3通り+2通りなので5通りです。
また一つ階段が増えると8,そしてもう一段増えると13...といったように増えていきます。
この足し算の構造が理解できれば後はその法則をコードにするだけです。
簡単な例としては、
class Solution:
def climbStairs(self, n: int) -> int:
if n <= 1:
return n
num1, num2 = 0, 1
for i in range(n):
num1, num2 = num2, num1+num2
return num2
# Runtime: 32 ms, faster than 39.40% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.7 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
これが一般的な解き方でしょう。
しかしdiscussを見ているとこれよりも高速な書き方がありました。
from functools import lru_cache
class Solution:
@lru_cache(None)
def climbStairs(self, n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return self.climbStairs(n-1) + self.climbStairs(n-2)
# Runtime: 24 ms, faster than 91.08% of Python3 online submissions for Climbing Stairs.
# Memory Usage: 13.9 MB, less than 5.97% of Python3 online submissions for Climbing Stairs.
めちゃ速ですね・・・
ところでlru_cacheってなんやねん。
となったので大人しく公式ドキュメントで調べました。
@functools.lru_cache(user_function)
@functools.lru_cache(maxsize=128, typed=False)
関数をメモ化用の呼び出し可能オブジェクトでラップし、最近の呼び出し最大 maxsize 回まで保存するするデコレータです。高価な関数や I/O に束縛されている関数を定期的に同じ引数で呼び出すときに、時間を節約できます。結果のキャッシュには辞書が使われるので、関数の位置引数およびキーワード引数はハッシュ可能でなくてはなりません。
引数のパターンが異なる場合は、異なる呼び出しと見なされ別々のキャッシュエントリーとなります。 例えば、 f(a=1, b=2) と f(b=2, a=1) はキーワード引数の順序が異なっているので、2つの別個のキャッシュエントリーになります。
.....LRU (least recently used) キャッシュ は、最新の呼び出しが次も呼び出される可能性が最も高い場合 (例えば、ニュースサーバーの最も人気のある記事は、毎日変わる傾向にあります) に最も効率が良くなります。キャッシュのサイズ制限は、キャッシュがウェブサーバーなどの長期間に渡るプロセスにおける限界を超えては大きくならないことを保証します。
一般的には、 LRU キャッシュは前回計算した値を再利用したいときにのみ使うべきです。 そのため、副作用のある関数、呼び出すごとに個別の可変なオブジェクトを作成する必要がある関数、 time() や random() のような純粋でない関数をキャッシュする意味はありません。
つまり呼び出した関数の結果を辞書を使ってキャッシュするからそのキャッシュされた結果が最新の呼び出しでも呼び出される場合は実行するときの効率があがる、ということっぽいです。
知らなかったのでとても勉強になりました、やはりdiscussを見るのは大事。