いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode easy 213 house robber ii

投稿日:

こんにちは

今回の学びは

・ある程度型、パターンを覚えて、解く・閃く速度をあげよう (これ結構大事かも)

配列がサイクリックになったら、ズラして2パターンを解く

 

問題は。。。

(時間配分は5分問題理解 10分検討 10分実装  20分振り返り の一文45分構成)

まずは入出力をしっかりおさえましょう。

 

leetcode easy 198 house robberという問題で

与えられた配列はサイクリックであるとう違いのみです。

ですが

この違いを埋めるアイデアの思いつきは結構難しかったです

例のごとくエクセルにdp表を書きながらあーだ、こーだしました。

何かしらの筆跡はわかると思いますが、(これくらいのサンプルをあーだこーだした様子がわかると思うので、後の自分の参考になる

と思ってスクショしています。)最後の方で

top includedしたバージョンと、その場合の答えはi-1

top excludedしたバージョン この場合の答えはi

というしたらいけそうだということが分かり、それがそのまま正解となった

最初の数字を使ってしまうと、それが伝搬されて最終的に最後の数字が使えなくなる。

だから

どうしたらいいんだ?的な発想が発見につながったと思います

肝は最初の数字が貢献すると最後は使えない

ということですね。

最初の25分では思いつきませんで、さらに悩むこと15分くらいしたかと思います

思いつきのスピードをあげるにはどうしたらいいのでしょうか?

=>できる人は型でと行っている記事もあるくらいなので、まぁ、パターンを自分のDBに貯めていくことをやってみましょうか。

 

ということで今日の私のパターンDBには配列がサイクリックになったら、ズラして2パターンを解く

と追加しました

 

 

 

実装前後でこれは毎回書きましょう。timespace analysis (時間とスペースの分析)は O(n)

pseudocode(擬似コード)をかいてみますか。

。。。

 

実際の実装はこちら

class Solution:
    @timeit
    def rob(self, nums: List[int]) -> int:
        length = len(nums)
        if length <= 0: return 0
        if length <= 3: return max(nums)

        # length >= 4
        dp = [0] * len(nums)
        def dp_get(i, default=0):
            if i < 0 or i >= length: return default
            else: return dp[i]

        # dp的にiまでの配列をつかった最大をほりこんでいけたと仮定(hypoth1)する
        # その上で漸化式をつくる
        # hypothXが可能か検討する yesなら実装 noならdp以外で再試行

        # Top included
        for i in range(length):
            dp[i] = max(dp_get(i-1), dp_get(i-2)+nums[i])
        maxi = dp[i-1]

        # Secound round without top
        dp[0] = 0 # bit of initializtion
        for i in range(1, length):
            dp[i] = max(dp_get(i-1), dp_get(i-2)+nums[i])
        return max(maxi, dp[i])

 

 

実装後です。timespace analysis (時間とスペースの分析)は O(n)でスペースもO(n)です

メモでコメントでかきましたが、

dpダメならと、次の手順にも目を向けているあたりは成長しているなと感じます。

速度は十分出たので満足です

メモリに関しては成績はよくないですが、他の人はdp使わずに解いたということでしょうか。

 

まとめ

・ある程度型、パターンを覚えて、解く・閃く速度をあげよう (これ結構大事かも)

配列がサイクリックになったら、ズラして2パターンを解く

 

以上です

-アルゴリズム

Copyright© CTOの日記 , 2020 All Rights Reserved.