【アルゴリズム脳トレ】leetcode medium 133 clone graph

こんにちは

今回の学びは

・とりえあず、自分を信じてコーディングしきってみよう

・連結グラフとは、つながっているグラフ（詳しくはwiki)で英語ではconnected graphという

問題は。。。

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

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

これまでしばらく

dp問題をやってきたので

グラフ問題は新鮮ですし、それゆえなれてないし

25分では解けませんでしたね。

むしろ、問題の構造を理解するくらいしかできず、でも最後のほうで

まぁ、単純にやればいいんじゃない。ノードの上限も小さそうでし、と

あるしゅ開き直って、これでダメなら答え見よとやってみたら、

それっぽい回答ができた。サンプル問題でdiffがすこしだけだったので、

デバッガーでバグを探して修正すると、見事、通りました。

答え見なくてよかったー

一時間以上掛けたけどまぁ、その価値は自信につながたたのであったと思います。

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

ループで回してneighborsもその都度、instanciateしていきます。

time complexityはO(n)で

space complexityは stackとclonedの辞書、更に巡回済フラッグ用の辞書でまぁ、O(n*2)といったところです。

実際の実装はこちら

class Solution:
    def cloneGraph(self, node: List[Node]) -> List[Node]:
        stack = []
        visitted = defaultdict(bool)
        cloned = {}
        if node == None: return None
        stack.append(node)
        def get_newobj(node: Node) -> Node:
            if node is None: return None
            ref = id(node)
            if ref not in cloned.keys():
                newobj = Node(node.val, [])
                cloned[ref] = newobj
            return cloned[ref]
        def add_neighbor(node:Node, neighbor:Node):
            if node is None: return
            if neighbor is None: return
            if neighbor not in node.neighbors:
                node.neighbors.append(neighbor)

        while len(stack):
            curr = stack.pop(0)
            ref = id(curr)
            newobj = get_newobj(curr)
            if not visitted[ref]:
                visitted[id(curr)] = True
                logging.debug("curr.val is %s" % curr.val)
                for nextnode in curr.neighbors:
                    stack.append(nextnode)
                    add_neighbor(newobj, get_newobj(nextnode))
                    logging.debug("cur.neighbor's node, which is nextnode val is %s" % nextnode.val)
        return cloned[id(node)]

そこそこ

ながったらしですが、

まぁ、グラフ問題重ねる過程でもうすこしキレイにかけるかなー

と楽観視しています

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

前述の通りでかわりません

まとめ

・とりえあず、自分を信じてコーディングしきってみよう

・連結グラフとは、つながっているグラフ（詳しくはwiki)で英語ではconnected graphという

以上です