Shulou(Shulou.com)06/02 Report--

This article introduces the relevant knowledge of "how to clone a map by Python". In the operation of actual cases, many people will encounter such a dilemma, so let the editor lead you to learn how to deal with these situations. I hope you can read it carefully and be able to achieve something!

Title:

Given a reference to a node in an undirected connected graph, a deep copy (clone) of the graph is returned. Each node in the figure contains its value val (Int) and a list of its neighbors (list [Node]).

Example:

Enter: {"$id": "1", "neighbors": [{"$id": "2", "neighbors": [{"$ref": "1"}, {"$id": "3", "neighbors": [{"$ref": "2"}, {"$id": "4", "neighbors": [{"$ref": "3"}, {"$ref": "1"}], "val": 4}], "val": 3}], "val": 2}] {"$ref": "4"}], "val": 1} explain: the value of node 1 is 1 It has two neighbors: nodes 2 and 4. Node 2 has a value of 2 and has two neighbors: node 1 and node 3. Node 3 has a value of 3, and it has two neighbors: nodes 2 and 4. Node 4 has a value of 4, and it has two neighbors: nodes 1 and 3.

Tip:

The number of nodes is between 1 and 100.

An undirected graph is a simple graph, which means that there are no duplicate edges or self-loops in the graph.

Because the graph is undirected, if node p is a neighbor of node Q, then node Q must also be a neighbor of node p.

A copy of a given node must be returned as a reference to the clone graph.

Ideas for solving the problem:

The traversal of graphs is nothing more than DFS (depth-first search) and BFS (breadth-first search). You can take a look at this article a few days ago:

BFS needs to be implemented with queues, and DFS can be implemented either by stack or directly by recursion. For this problem, it is better to use recursion directly, and there is no need to open up additional data structure space recording nodes. The writing methods of BFS and DFS are relatively fixed, so it is recommended to take some time to understand them once and for all.

The idea of this question is very clear. the key point is how to copy random nodes deeply. You can refer to this article in the linked list: LeetCode 138: copying a linked list Copy List with Random Pointer with random pointers.

The linked list is linear and can copy nodes to each node and make a deep copy cleverly. Obviously, the tree structure like the figure cannot be used in this way, and the copied nodes can only be recorded with the help of the data structure. This need to map the relationship between new and old nodes is naturally a hash table (dictionary).

Java:

Class Solution {public Node cloneGraph (Node node) {if (node = = null) return node; Queue queue = new LinkedList (); / / implement BFS Map map = new HashMap () with queue; / / Hash mapping Node head = new Node (node.val, new ArrayList ()); / / header node map.put (node, head); / / Hash map original node and new node queue.add (node) / / the original node joins the queue while (! queue.isEmpty ()) {/ / repeat cycle Node tmp = queue.poll () if the queue is not empty; / / the queue header node for (Node n: tmp.neighbors) {/ / traverses the neighbor node if (! map.containsKey (n)) {/ / when the key of the dictionary does not contain the node map.put (n, new Node (n.val, new ArrayList () / / add a new mapping relationship to the dictionary queue.add (n); / / join the queue} map.get (tmp) .neighbors.add (map.get (n)); / / join a neighbor node}} return head;}}

Python3:

Class Solution: def cloneGraph (self, node: 'Node')->' Node': if not node: return node head = Node (node.val, []) # header node map = {node: head} # initialization dictionary And establish a mapping relationship between new and old nodes queue = collections.deque () # queue queue.append (node) # the original node joins the queue while queue:# queue is not empty tmp = queue.popleft () # pop-up queue header node for n in tmp.neighbors:# traverses neighbor node if n in map.keys (): # n node exists in the dictionary key mapping [tmp] .neighbo rs.append (map [n]) # directly added to the new node Neighbor node else: map [n] = Node (n.val []) # create a new node and establish a mapping relationship map[ tmp] .neighbors.append (map [n]) # take out the node from the new mapping relationship and join the neighbor node queue.append (n) # the neighbor node joins the queue return head

DFS:

The recursive depth-first search is very concise and easy to understand, and the only thing to note is that the dictionary needs to be defined outside the function.

Java:

Class Solution {Map map = new HashMap (); public Node cloneGraph (Node node) {if (node = = null) return node; map.put (node, new Node (node.val, new ArrayList ()); / / create a new node and establish a mapping relationship for (Node n: node.neighbors) {if (map.containsKey (n)) map.get (node) .neighbors.add (map.get (n)); else map.get (node) .neighbors.add (cloneGraph (n)) } return map.get (node);}}

Python3:

Class Solution: map = dict () def cloneGraph (self, node: 'Node')->' Node': if not node: return node self.map [node] = Node (node.val, []) for n in node.neighbors: if n in self.map.keys (): self.map [node] .neighbors.append (self.map.append) else: self.map.neighbors.append (self.cloneGraph (n)) return self.map [node]

Note:

The dictionary in python can be dict (). Get (key) or dict [key] when taking values, but the time complexity of dict [key] is 1, but it is necessary to use this method when doing algorithm problems. Because although the effect of the get () method is the same, the time consumption caused by repeatedly calling the function is very high, and the python language is slow, so we should get into the habit of optimizing the code as much as possible.

This is the end of the content of "how to achieve cloning of Python". Thank you for your reading. If you want to know more about the industry, you can follow the website, the editor will output more high-quality practical articles for you!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.