いいものをつくろう

CTOの日記

アルゴリズム

【アルゴリズム脳トレ】leetcode 112 Path Sum

投稿日:

こんにちは

今回の学びは

・合計の差分を持ち歩くというのと、葉の判定がポイントの問題です

 

問題はpath-sum

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

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

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

 

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

 

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

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

 

場合によっては、pseudocode(擬似コード)をかいてみてもよい。

 

4、実装しましょう。

class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None
    def __str__(self):
        return "val:%s, left:%s, right:%s" % (self.val,
                                              self.left.val if self.left else "none",
                                              self.right.val if self.right else "none",
                                              )
def bt_sum(node, k, path):
    paths = []
    if node:
        rest = k - node.val
        path_copy = path[:]
        path_copy.append(node.val)
        is_leaf = node.left is None and node.right is None
        if is_leaf:
            if rest == 0:
                return [path_copy]
            else:
                return []
        else:
            paths += bt_sum(node.left, rest, path_copy)
            paths += bt_sum(node.right, rest, path_copy)
    return paths


root = TreeNode(10)
root.left = TreeNode(16)
root.right = TreeNode(5)
root.left.right = TreeNode(-3)
root.right.left = TreeNode(6)
root.right.right = TreeNode(11)

path = []
ans = bt_sum(root, 26, path)
print(ans)

よくする間違い!

配列(path)を引数として持たす時、参照として持ち歩くので、その影響がわかっていない

赤字でコピーするのがポイント。いっつも、ハマるので注意。このために配列をコピーして走査するのでstackの積み重ねO(logN) * O(N)のspaceが必要で非常にメモリ効率はよくない

def bt_sum(node, k, path):
    paths = []
    if node:
        rest = k - node.val
        path_copy = path[:]
          path_copy.append(node.val)
        is_leaf = node.left is None and node.right is None
        if is_leaf:
            if rest == 0:
                return [path_copy]
            else:
                return []
        else:
            paths += bt_sum(node.left, rest, path_copy)
            paths += bt_sum(node.right, rest, path_copy)
    return paths

ちなみに、メモリ効率はテスト結果としては悪くないです。下の関数は返却値が{true|false}ですが、上の関数ではpathのリストを全て返すようにしています。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    """
    edge case: (initial acc is 0 , what if sum = 0 is given?!)
      root = [1], sum = 0
    edge case: ( return True only if it reaches to the end of branch)
      https://leetcode.com/submissions/detail/289318789/
      root = [1, 2], sum = 1
    """
    def hasPathSum(self, root: TreeNode, sum: int) -> bool:
        def bt_sum(node, k, path):
            paths = []
            if node:
                rest = k - node.val
                path_copy = path[:]
                path_copy.append(node.val)
                is_leaf = node.left is None and node.right is None
                if is_leaf:
                    if rest == 0:
                        return [path_copy]
                    else:
                        return []
                else:
                    paths += bt_sum(node.left, rest, path_copy)
                    paths += bt_sum(node.right, rest, path_copy)
            return paths
        return len(bt_sum(root, sum, [])) > 0
    
    def hasPathSum2(self, root: TreeNode, sum: int) -> bool:
        # dfsでaccumulative sumをcarry on すればよい
        def dfs_accumulate(node, goal: int, acc:int,) -> bool: 
            if node is None: return False
            _acc = 0 if acc == None else acc
            _acc_new = _acc + node.val
            is_leaf = (node.left == None and node.right == None)
            if _acc_new == goal and is_leaf:
                return True
            if node.left:
                if dfs_accumulate(node.left, goal, _acc_new): return True
            if node.right:
                if dfs_accumulate(node.right, goal, _acc_new): return True
            return False
        
        if root is None: return False
        
        return dfs_accumulate(root, sum, None)
        

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

 

合計の差分を持ち歩くというのと、葉の判定がポイントの問題です

 

 

振り返り

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

 

まとめ

 

以上です

-アルゴリズム

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