いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 300 Longest Increasing Subsequence

投稿日:

こんにちは

今回の学びは

・最初に、全ての一個目をrec(i) for i in range(N)で訪れているのは、何も選んでいない-1のインデックスから再帰をはじめるより

分かりやすいから、と理解した。

 

問題はlongest-increasing-subsequence

(時間配分は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/longest-increasing-subsequence/discuss/138240/Python-dp-recursive-and-nlogn-binary-search-solutions

#https://leetcode.com/problems/longest-increasing-subsequence/discuss/138240/Python-dp-recursive-and-nlogn-binary-search-solutions
class Solution:
    def lengthOfLIS(self, nums: List[int]) -> int:
        # https://leetcode.com/problems/longest-increasing-subsequence/discuss/138240/Python-dp-recursive-and-nlogn-binary-search-solutions
        cache = {}
        
        def rec(i):
            if i == N-1: return 1
            if i in cache: return cache[i]
            ans = 1
            for j in range(i+1, N):
                if nums[i] < nums[j]:
                    ans = max(ans, 1 + rec(j))
            cache[i] = ans
            return ans
        if nums is None or len(nums) == 0: return 0
        N = len(nums)
        return max( [rec(i) for i in range(N)] )

 

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

 

 

 

振り返り

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

二重での配列でかんあげるのではなく、i, jポインターで、maxを探す旅O(N)にでる

 

 

参考動画

再帰とrecursiveの解き方は一通り触れた

最後にO(NlogN)の解法は

 

まとめ

 

以上です

-アルゴリズム

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