こんにちは
今回の学びは
・BSTの組み合わせはカタラン数になっている
・小さい問題の答えが大きな問題をつくれれば、dpで答えられる
マラソンのやりかた
マラソンでは一時間で難問とけるかのトライアルです。今までの練習の実践編です。
できるだけ解ければ良しなのですが、1問解く時間の目安は20分としてみます。
マラソン中は振り返らず、終了後にいつものように「次のこの問題を解くばあい知っていればよい一つの事実とは？」
とう問題の核となるものを抽出していきます。
問題の選び方は、今はleetcodeのpick nextで良さげなもを選ぶ、というほぼノールールでいきます。
それでは始めます。
8:28 start
1問目 => unique-binary-search-trees
20分かけましたが、解答浮かばず。。。反省の余地大いにあり。BFも考えれなかった。
あとで解答を見てもパッとわからなかたtので
動画をみまして、なにやらカタラン数というのを関係してくるようです。
個人的にはこちらの動画のほうがわかりやすかったです。一つ目の動画でハイレベルのコンセプトを理解できていたからかもしれませんが。
とにかく、これだけ複雑の問題を
どのように順序立ててとくことができただろうか？
再現できるか？は重要な課題であることは間違いありません。
まずは、
コンセプトと解き方がわかったので25分以内で実装を試みます
class Solution:
def numTrees(self, n: int) -> int:
if n <= 2: return n
dp = [0 for i in range(n+1)]
dp[1] = 1; dp[2] = 2;
for i in range(3, n+1):
tmp = 0
for j in range(i):
left = j
right = i - j -1
if left == 0: tmp += dp[right]
elif right == 0: tmp += dp[left]
else: tmp += dp[left] * dp[right]
dp[i] = tmp
return dp[n]
丸暗記感はいなめないが、今回の学びとしては
・BSTの組み合わせはカタラン数になっている
次！
2問目 => medium 120 triangle
この問題はtreeを構築してbfsで足し算していけばいいんじゃないでしょうか。
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
def rec(S, j, i, sofar=0): # j is previous
if i > len(S):
return sofar
# choose
ans1 = rec(S, i, i+1, sofar+S[i][j])
# choose
ans2 = rec(S, i, i+1, sofar+S[i][j+1])
return min(ans1, ans2)
return rec(triangle, 0, 0, 0)
動作せず。。しかし、これでいけるようなきがしている。
O(2^n)ですすこぶる遅いけど。。。。
はい、この時点で12:01pmになりましたので、一旦休憩します。
残り15ふんとして、午後に再開します。
こちらも解答を見たところdpで解いているのがほとんどでした。
dpで解けといわれてもパッと思い浮かばず動画を検索してコレをみました
最初のbfsでも解けると思いますがO(2^N)ですのでdpだとO(N)です。どちらの解放を御社のソフトウェアで採用したいですか？
当然、後者ですので、そちらをほりさげます。
さきほどの動画の解説では、dpは底辺のカラム数に合わせており、
ボトムからジョジョに積み上げている方法で、
うまーく、変に上書きしてしまわないように、なっています。
すごい。
これってどうやって思いつく！？
ひとまず、実装します
すごい良いパファーマンスのよい結果となりました。
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
n = len(triangle)
if n == 0: return 0
m = len(triangle[n-1])
dp = [0 for _ in range(m+1)]
print(dp)
for i in range(m-1, -1, -1):
for j, x in enumerate(triangle[i]):
dp[j] = min(x + dp[j], x + dp[j+1])
return dp[0]
なぜdpをつかったのか？
問題を抽象化表現した時に、その答えが現れるかもしれません。
まず、元の問題ですが
二次元の配列が与えられます。
ピラミッド式に一個づつ要素は増えていきます。
ルートからボトムにかけて、和が最小になるパスの和はいくつですか？
という問題です。
まず、greedyアルゴがあてはまらないことを確認していました。コレは素晴らしい点ですので、私も模倣しましょう。
これは、常に最小を選んでいっても、成り立たないというのは、実際になぞってみれば、すぐわかることでしょう。
また、
三行目までの最小の結果を持って、4行目に持ち込んでも、ダメだということに
似ています。
三行目までの結果を利用したい場合は、三行目までの全てのカラムにおいてと和が必要になってきますね。
これでDPが何かできそうです。
という解答の芽はみたきがします。
ちょっと飛びますが、この一行ごとにカラム数分、それぞれのパスの和を保存シテおくためには、底辺のカラム数がmaxなのでそれで十分だということから
dp = [0 for _ in range(m)]
にしているのですね、
さらにm+1としているのは、便宜上です。最も右のカラムの計算をするのに便利なので付け足してます。
3問目 => add-binary easy
class Solution:
def addBinary(self, a: str, b: str) -> str:
def binary_to_int(characters: str):
ans = 0
sz = len(characters)
for i in range(sz-1, -1, -1):
c = characters[i]
j = (sz-1-i)
if c == "1":
ans += 2**j
return ans
def int_to_binary(x: int):
stack = []
if x == 0: return "0"
while x:
if x & 1:
stack.append("1")
else:
stack.append("0")
x >>= 1
ans = ""
while stack:
y = stack.pop()
ans += y
return ans
a_int = binary_to_int(a)
b_int = binary_to_int(b)
y_int = a_int + b_int
return int_to_binary(y_int)
他の人の解答をみて
zipして、一気にキャリオーバーで計算する方法、すばらしい
キャリーというのがキーワードかもしれない。これもcarryしているし。昔、【アルゴリズム脳トレ】leetcode easy 371 sum of two integerという問題でadderをつくりましたが、実はこれで解けるんじゃないかとおもいます。問題はこちらもeasyの371 sum of two integerでしたね。
4問目 =>
は、いけなかったので。
この辺で終了します。だいたい一時間ちょっと取り組みまして
easyが一個解けまして、 mediumが1個解答思いつき 0.5ポイントとして、最後mediumが
一個、全く解答思いつかずの合計1.5 / 3.0と
問題は一歩やさしい問題はこちら(153)でしたねは。。。
（時間配分は5分問題理解 10分検討 10分実装の一文20分構成)
まずは入出力をしっかりおさえましょう。
「次のこの問題を解くばあい知っていればよい一つの事実とは？」
1問目 => unique-binary-search-trees => BSTの組み合わせはカタラン数になっている
2問目 => medium 120 triangle => 配列最小和問題はdpで
3問目 => add-binary => carry with adder 🙂
2問をdp問題に当たったので改めて書きます。
組み合わせは全部でいくつありますか？
最小は最大は？、小さい問題の答えが大きな問題をつくるかどうか？
それがdpで答えられるかどうかの、大きな質問です。
まとめ
・BSTの組み合わせはカタラン数になっている
・小さい問題の答えが大きな問題をつくれれば、dpで答えられる
以上です