いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode medium 987 vertical order traversal of a binary tree

投稿日:

こんにちは

今回の学びは

方向性はあっているのだが、デバッグに時間がかかる見込みと見たので切り替えた。(時間勝負の時はこれ大事。)

 

問題はhttps://leetcode.com/problems/vertical-order-traversal-of-a-binary-tree

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

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

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

同じレベルの数字が2つあった時は小さい方から並べる。

深さの浅い順に並べる。というマイナールールは結構細かい。

 

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

dfsでうまいこと、x軸とy軸ごとにデータを挿入していく。

 

3,どれでいくか、一緒に決定しましょう。

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

O(N)でデータを揃えたあと

アベレージでLogN* Log(LogN) * LogN* Log(LogN) とう微妙なdefaultdictをソートしまくる

ロジックがあったがら、速さは94%と良かった。

 

4、実装しましょう。

from collections import defaultdict
class Solution:
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if root is None: return []
        res = defaultdict(lambda : defaultdict(list))

        def dfs(node: TreeNode, x: int, y: int, res):
            if node is None: return
            _y = abs(y)
            res[x][_y].append(node.val) # _y is abs y is guarateed that 1 direction
            dfs(node.left, x - 1, y - 1, res)
            dfs(node.right, x + 1, y - 1, res)

        dfs(root, 0, 0, res)
        # cost of sorted(dict.iteritems())??
        ans = []
        for x, xaxis in sorted(res.items()):
            v_res = []
            for y, vertical_ary in sorted(xaxis.items()):
                v_res += sorted(vertical_ary)
            ans.append(v_res)
        return ans

 

 

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

木がNoneとき何をかえす?前述の細かいルールに従った結果になっているか?

 

振り返り

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

defaultdict自体はdictと一緒で速いので、どんどん使えばよい。bisectも使っても良い問題だと思う。

 

 

ボツ案に対して見切りが比較的早かったので吉。ボツ案はこちら。

方向性はあっているのだが、デバッグに時間がかかる見込みと見たので切り替えた。(時間勝負の時はこれ大事。)

class Solution_botsu:
    """
    複雑過ぎて、デバッグできなかったコード。
    """
    def verticalTraversal(self, root: TreeNode) -> List[List[int]]:
        if root is None: return []
        res0, resM, resP = [], [], []

        def dfs(node: TreeNode, x: int, y: int, res0, resM, resP):
            if node is None: return
            # do something with node.val
            if x == 0: # I don't have to generate
                if len(res0) == 0:
                    res0.append([node.val])
                else:
                    res0[0].append(node.val)
            elif x < 0:
                if len(resM) < abs(x):
                    resM.append([node.val])
                else:
                    resM[abs(x)-1].append(node.val)
            else: # x > 0
                if len(resP) < abs(x):
                    resP.append([node.val])
                else:
                    resP[abs(x)-1].append(node.val)
            dfs(node.left, x - 1, y - 1, res0, resM, resP)
            dfs(node.right, x + 1, y - 1, res0, resM, resP)

        dfs(root, 0, 0, res0, resM, resP)
        res = []
        for vertical in reversed(resM):
            res.append(vertical)
        for vertical in res0:
            res.append(vertical)
        for vertical in resP:
            res.append(vertical)

        return res

まとめ

方向性はあっているのだが、デバッグに時間がかかる見込みと見たので切り替えた。(時間勝負の時はこれ大事。)

以上です

-アルゴリズム
-

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