題目

  • 題目連結
  • 目標函式 : cloneGraph(node)
    • Input : node: Node
    • Output : Node

解題概念

  • 題意 : 給定一 Connected Undirected Graph 中一節點的 Reference，需要回傳該 Graph 的 Deep Copy 版本
    • 在 Graph 中，每個節點都包含 :
      • val : 一個 value (int)
      • neighbors : 其 neighbors 陣列 (List[Node])

我的寫法

  • 想法 : 想使用 DFS 或 BFS 去處理
  • 面臨問題 : 發現不知道要怎麼去處理新複製的 Node…

解答 or 其他優秀寫法 - BFS

  • 想法 : 其實就是差在需要使用 Hashmap 去儲存新複製的 Node，詳細變數如下 :
    • Hashmap hashmap 之儲存結構 :
      • Key : 舊有的 Node
      • Value : 複製新的對應的 Node
    • clone : root 的複製對應 Node，也是回傳之變數
    • queue : BFS 所需的 Queue
    • 詳細流程請見程式碼
  • 程式碼 : 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    def cloneGraph(self, node):     

        if not node: return None

        # 建立變數
        hashmap = {}
        clone = Node(node.val, [])
        queue = []

        # 先將 root 的舊版 & 新版丟入 Hashmap 中
        hashmap[node] = clone
        # 再將 root 丟到 Queue 中
        queue.append(node)

        while len(queue) != 0:

            # 取出當前要處理的節點
            current = queue.pop(0)

            # 針對該節點的每個 neighbor node
            for neighbor in current.neighbors:

                # 如果 neighbor 未出現在 Hashmap 的 Key 中 (代表 neighbor 尚未被檢視過)
                if neighbor not in hashmap:

                    # 複製一個新節點，並當作 neighbor 在 Hashmap 的對應 Value
                    hashmap[neighbor] = Node(neighbor.val, [])

                    # 再將該節點丟入 Queue
                    queue.append(neighbor)

                # 不管 neighbor 有沒有被檢視過
                # 仍要將該對應的新節點 (hashmap[neighbor])
                # 加入到 current 對應新節點的 neighbors 中
                hashmap[current].neighbors.append(hashmap[neighbor])

        return clone
  • 成效 :
    • Time Complexity : $O(V + E)$
    • Runtime: 34 ms (faster than 62.9%)
    • Memory Usage: 13.6 MB (more than 37.91%)