いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 740 Delete and Earn

投稿日:

こんにちは

今回の学びは

・ソートすることで、物事を一方方向に見るだけでよくすることで、+1, -1の制約を一個外している。

 

問題はdelete-and-earn

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

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

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

 

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

 

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

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

 

# duplicated, not sorted. 1 <= x <= 10000 and N <= 20000
# constrain: remove S[i]+1, S[i]-1
# [3, 4, 2]
# {3:3 -> 9
#  4:1 -> 4
#  2:2 -> 4
# }
f(N-1) = max(points)
f(2) = f(0) + f(4) + 4 
f(i) = f(S[i]-2) + f(S[i]+2) + S[i]

 

 

4、実装しましょう。

時間オーバーなので回答をみた。その上で、もうしこしだとおもった。
もみたけど、方向はよくて、ヒントをみて自力でclearした。
特に、バグがちゃんとみつけれてよかった。この回答を眺めたのが直接のヒントとなった
バグはここにあった!dp[i-1]もわすれてはいけない!

class Solution:
    def deleteAndEarn(self, nums: List[int]) -> int:
        def f(x): # return maximum point at 1
            pass
        memo = defaultdict(int)
        for x in nums:
            memo[x] += 1
        memo = { k: k*v for k, v in memo.items() }
        print(memo)
        N = 10001
        maxi = 0
        # number of values limited to 1 to 10000
        dp = [0] * N
        for i in range(N):
            if i - 2 >= 0:
                #dp[i] = dp[i-2] + memo.get(i, 0)  # バグはここにあった!dp[i-1]もわすれてはいけない!
                dp[i] = max(dp[i-2] + memo.get(i, 0), dp[i-1])
            else:
                dp[i] = memo.get(i, 0)
            maxi = max(maxi, dp[i])
        return maxi

 

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

 

 

 

振り返り

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

ソートすることで、物事を一方方向に見るだけでよくすることで、+1, -1の制約を一個外している。

 

 

まとめ

・ソートすることで、物事を一方方向に見るだけでよくすることで、+1, -1の制約を一個外している。

 

以上です

-アルゴリズム
-

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