いいものをつくろう

CTOの日記

アルゴリズム

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

投稿日:

こんにちは

今回の学びは

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

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

問題はmeduim 133 clone-graph

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

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

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

配列でわたされるの?ノードで?valはユニーク?

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

 

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

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

 

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

 

4、実装しましょう。

自分の実装はO(3N)で、悪くわないと思いますが、冗長です

class Solution:
    def rec(self, node: Node, cloned):
        if node is None: return None
        if node.val not in cloned:
            new_node = Node(node.val) # let's clone
            cloned[node.val] = new_node
            for next_node in node.neighbors:
                self.rec(next_node, cloned)

    def rec2(self, node: Node, cloned, visited):
        if node is None: return None
        if node.val not in visited or visited[node.val] == 0:
            new_node = cloned[node.val]
            # neighbors creation
            for next_node in node.neighbors:
                new_node.neighbors.append(cloned[next_node.val])
            visited[node.val] = 1
            for next_node in node.neighbors:
                self.rec2(next_node, cloned, visited)


    def cloneGraph(self, node: Node) -> Node:
        if node is None: return None
        cloned = {}
        self.rec(node, cloned)
        visited = {}
        self.rec2(node, cloned, visited)
        return cloned[node.val]

いいやつはO(1N)です

https://leetcode.com/problems/clone-graph/discuss/478738/Intuitive-Python-BFS

class Node:
    def __init__(self, val):
        self.val = val
        self.neighbors = []
class Solution:
    def cloneGraph(self, node: Node) -> Node:
        from collections import deque
        if node is None: return None
        q = deque()
        visited = {}
        visited[node] = Node(node.val) # 最初に作っておく
        q.append(node)
        """
        queueに入れる前に具現がされていること!
        """
        while len(q) > 0:
            curr: Node = q.popleft()  # q = [4], cloned = {1: 1', 2: 2', 4: 4'}
            for neighbor in curr.neighbors: # q = [4], curr = 2
                if neighbor not in visited: # neighbors = [1, 3]
                    visited[neighbor] = Node(neighbor.val) # cloned = {1: 1', 2: 2', 4: 4', 3:3'}
                    q.append(neighbor) # q = [2, 4]
                # visited[1] = 1' -> neighors(2', 4')
                # visited[2] = 2' -> neighors(1')
                visited[curr].neighbors.append(visited[neighbor]) # すでに具現化されているので。

        return visited[node]

最初の実装は40ms, 36%で、

あとのdequeは36ms, 72%の速さでした。

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

 

 

 

振り返り

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

この問題はdequeを使うとと楽

 

類似問題はcopy-list-with-random-pointer

まとめ

 

以上です

-アルゴリズム
-

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