leetcode------Clone Graph

5155 단어 LeetCode
제목:
Clone Graph
통과율:
23.7%
난이도:
중간
OJ's undirected graph serialization:
Nodes are labeled uniquely. We use  #  as a separator for each node, and  ,  as a separator for node label and each neighbor of the node.
 
As an example, consider the serialized graph  {0,1,2#1,2#2,2} .
The graph has a total of three nodes, and therefore contains three parts as separated by  # .
  • First node is labeled as  0 . Connect node  0  to both nodes  1  and  2 .
  • Second node is labeled as  1 . Connect node  1  to node  2 .
  • Third node is labeled as  2 . Connect node  2  to node  2  (itself), thus forming a self-cycle.

  •  
    Visually, the graph looks like the following:
           1
    
          / \
    
         /   \
    
        0 --- 2
    
             / \
    
             \_/
    
    

     
     
    이 문제는 이렇게 내는 것은 아무런 의미가 없다. 위에서 설명한 한 무더기의 재코드에는 전혀 표시되지 않고 직접 그림을 내는 반복 순서가 좀 좋아질 것이다.코드 바로 보기
     1 # Definition for a undirected graph node
    
     2 # class UndirectedGraphNode:
    
     3 #     def __init__(self, x):
    
     4 #         self.label = x
    
     5 #         self.neighbors = []
    
     6 
    
     7 class Solution:
    
     8     # @param node, a undirected graph node
    
     9     # @return a undirected graph node
    
    10     def cloneGraph(self, node):
    
    11         if node == None: return None
    
    12         nodeMap={}
    
    13         return self.cloneNode(node,nodeMap)
    
    14     
    
    15     
    
    16     def cloneNode(self,node,nodeMap):
    
    17         if node == None:return None
    
    18         if nodeMap.has_key(node):
    
    19             return nodeMap[node]
    
    20         else :
    
    21             clone =UndirectedGraphNode(node.label)
    
    22             nodeMap[node]=clone
    
    23             for nei in node.neighbors:
    
    24                 clone.neighbors.append(self.cloneNode(nei,nodeMap))
    
    25         return clone

    좋은 웹페이지 즐겨찾기