LeetCode-Python-133. クローン図
連通図のノードへの参照がない場合は、図の深いコピー(クローン)を返します.図中の各ノードには、その値val(Int)とその隣のリスト(list[Node])が含まれています.
例:
入力:{「$id」:「$id」:「"1」、「neighbors」:[{「$id」:「$id」:「{2」、「neighbors」:[{「$ref」:[{「$ ref」:「$ id」:「"3」、「neighbors」:[{「$ref」:「「$ ref」:「「$ 2」},{「$id」:「「$id」:「「{4」、「neighbors」:[{「$ref」:「「$ 3」},{「$ref」:「「$ref」:「}」,「$ref」」:「「}」」:「}」,「val」:4}],「val」:3}],「val」:「「}val":2},{"$ref":"4"},"val":1}
説明:ノード1の値は1で、ノード2と4の2つの隣接があります.ノード2の値は2で、ノード1と3の2つの隣接があります.ノード3の値は3で、ノード2と4の2つの隣接があります.ノード4の値は4で、ノード1と3の2つの隣接があります.
ヒント:
ノード数は1~100です.無方向図は単純な図であり、これは図中に重複するエッジも自己ループもないことを意味する.図は無方向であるため、ノードpがノードqの隣接である場合、ノードqもノードpの隣接である必要がある.指定したノードのコピーをクローンマップの参照として返す必要があります.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/clone-graph著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
図の遍歴BFS+ハッシュ表解題.
ハッシュテーブルmappingを使用して、すべてのノードとそのcopyの関係を記録します.
時間複雑度:O(N)
空間複雑度:O(N)
例:
入力:{「$id」:「$id」:「"1」、「neighbors」:[{「$id」:「$id」:「{2」、「neighbors」:[{「$ref」:[{「$ ref」:「$ id」:「"3」、「neighbors」:[{「$ref」:「「$ ref」:「「$ 2」},{「$id」:「「$id」:「「{4」、「neighbors」:[{「$ref」:「「$ 3」},{「$ref」:「「$ref」:「}」,「$ref」」:「「}」」:「}」,「val」:4}],「val」:3}],「val」:「「}val":2},{"$ref":"4"},"val":1}
説明:ノード1の値は1で、ノード2と4の2つの隣接があります.ノード2の値は2で、ノード1と3の2つの隣接があります.ノード3の値は3で、ノード2と4の2つの隣接があります.ノード4の値は4で、ノード1と3の2つの隣接があります.
ヒント:
ノード数は1~100です.無方向図は単純な図であり、これは図中に重複するエッジも自己ループもないことを意味する.図は無方向であるため、ノードpがノードqの隣接である場合、ノードqもノードpの隣接である必要がある.指定したノードのコピーをクローンマップの参照として返す必要があります.
ソース:力ボタン(LeetCode)リンク:https://leetcode-cn.com/problems/clone-graph著作権はインターネットの所有に帰属する.商業転載は公式の授権に連絡してください.非商業転載は出典を明記してください.
考え方:
図の遍歴BFS+ハッシュ表解題.
ハッシュテーブルmappingを使用して、すべてのノードとそのcopyの関係を記録します.
時間複雑度:O(N)
空間複雑度:O(N)
"""
# Definition for a Node.
class Node(object):
def __init__(self, val, neighbors):
self.val = val
self.neighbors = neighbors
"""
class Solution(object):
def cloneGraph(self, node):
"""
:type node: Node
:rtype: Node
"""
from collections import defaultdict, deque
mapping = dict() # key is the original node, value is its copy
queue = deque([node])
visited = set()
visited.add(node)
while queue:
cur = queue.popleft()
visited.add(cur)
copy = Node(cur.val, [])
mapping[cur] = copy
for neigh in cur.neighbors:
if neigh not in visited:
queue.append(neigh)
for cur, copy in mapping.items():
for each in cur.neighbors:
copy.neighbors.append(mapping[each])
return mapping[node]