いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode hard 128 longest concecutive sequence

投稿日:

こんにちは

今回の学びは

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

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

問題は。。。

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

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

hardです。

Hardで、ちょっと身構えちゃいますが

おそれることは有りません。基礎ができているば

あとはその組み合わせ

それか、それプラス、ちょっと視点をかえて、アイデアをいれる

それでも解けない場合は、bucket sortなど、高度な術を知っている

簡単に解ける場合など様々です。

が、くりかえしになりますが、ほとんどの問題は考えれば解けます。

解けると思って、身構えず、風通にmediumの延長として取り組みましょう。

さぁ、

この問題

sortしたら簡単だけど、それをしちゃーだめで

o(n)でときなさいと

graphを利用するんだな、とほぼ確信に近いチートの上で

どのよに、それが利用できるか考える。

なんか

1-2-3のような木構造をつくってから、それこそnumber of island的に

数えられそう。

ということで

graph + dfsという術が効きそう、と思っている。

さらに

それをするためには

1の辺は0, 2で -1, +1で汎用化できる。

ここまで来たらあとは実装です。

 

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

 

graphのdfsなのでO(n)です。

何を返すかは、解いている最中は、まだ整理がついてないので

いつもまごつきます。

 

実際の実装はこちら

def longestConsecutive(self, S: List[int]) -> int:
        length = len(S)
        if length <= 0: return 0

        edges = {}
        from collections import defaultdict
        exist = defaultdict(lambda:False)
        visit = defaultdict(lambda:False)

        for i in range(length):
            value = S[i]
            edges[value] = [value-1, value+1]
            exist[value] = True

        def dfs(value, sofar=0) -> int:
            visit[value] = True
            counter = sofar
            #if value not in exist: # O(logN)
            if not exist[value]: # O(1)
                return counter

            counter += 1 # value is exist, so add one
            tmp = 1
            for neighbour in edges[value]:
                if exist[neighbour] and not visit[neighbour]:
                    # 帳尻合わせっぽい、感じになってしまったが、まぁ -1というのは neigherから帰ってくるのはvalueも含めてにことなので、その辺
                    # をうまくやるための -1。
                    tmp += dfs(neighbour, counter) - 1
            return max(tmp, counter)

        maxi = 0
        for i in range(length):
            maxi = max(dfs(S[i], 0), maxi)
        return maxi

 

後から考えれば、自分を含まない数を返してそのままtmp +=するのが

キレイかなとおもう。

 

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

o(n)問題ですからね♪

 

まとめ

・hardもやれば解ける!

 

以上です

-アルゴリズム

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