アルゴリズム

【アルゴリズム脳トレ】leetcode medium 790 Domino and Tromino Tiling

投稿日:

こんにちは

今回の学びは

・ソートされた配列と二分木はよく似てるよ。

・できれば二分木探索を配列で実装していて 🙂

問題はdomino-and-tromino-tiling

(時間配分は5分問題理解=restate&clarify 10分検討multip-sol, analysis, reasons 10分実装  20分振り返り の一文45分構成)をできればgoogle docで笑&真剣。

終始、わからないことは声にだして、明確にしていきましょう。

1,まずは入出力をしっかりおさえましょう。(問題を自分の言葉で復唱すること、わからないことをクリアにすると、前提も声にだすこと)

 

2,いくつかのソリューションを声にだして出してみましょう。(もちろんtime complexit, space complexityの分析や理由を付け加えて)

 

3,どれでいくか、一緒に決定しましょう。(理由付きでね、よろしく)

timespace analysis (時間とスペースの分析)は 〇〇です

 

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

 

動画はこちら

 

4、実装しましょう。

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/406649/Python-DP-half-and-full
分かりやすい

https://leetcode.com/problems/domino-and-tromino-tiling/discuss/182594/Python-1-liner-O(log-n)-time-O(1)-space-with-explanation
わかりやすいけど、
すごいけど、わからない。
class Solution:
    def numTilings(self, n: int) -> int:
        if n == 0: return 0
        dp = [0] * (n+1)
        dp[0] = 0
        if n == 0: return dp[0]
        dp[1] = 1
        if n == 1: return dp[1]
        dp[2] = 2
        if n == 2: return dp[2]
        dp[3] = 5
        if n == 3: return dp[3]
        for i in range(4, n+1):
            dp[i] = dp[i-1]*2 + dp[i-2]*0  + dp[i-3]*1
            #dp[i] = dp[i-1]*0 + dp[i-2]*2  + dp[i-3]*1
            #dp[i] = dp[i-1] + dp[i-2]*2  + dp[i-3]*2
            # https://leetcode.com/problems/domino-and-tromino-tiling/discuss/407367/Python-O(0)-space
            #dp[i] = dp[i-1] + dp[i-2]*2  + dp[i-3]*5
            #dp[i] = dp[i-1] + dp[i-2]*2  + dp[i-3]*2

        return dp[n]

 




5、エッジケースとサンプルテストを忘れずに!

 

 

 

振り返り

「次のこの問題を解くばあい知っていればよい一つの事実とは?」

 

まとめ

 

以上です

-アルゴリズム

Copyright© CTOを目指す日記 , 2024 All Rights Reserved.