leetcode 133. Clone Graph

    xiaoxiao2021-03-25  38

    今天换换口味,来一题数据结构题

    对于一个图,如何clone它呢

    Clone an undirected graph. Each node in the graph contains a label and a list of its neighbors.

    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 / \ \_/

    Subscribe to see which companies asked this question.

    题目如上,可以建一个哈希表,将新老节点一一对应,然后再复制其邻居节点链表即可

    /** * Definition for undirected graph. * class UndirectedGraphNode { * int label; * List<UndirectedGraphNode> neighbors; * UndirectedGraphNode(int x) { label = x; neighbors = new ArrayList<UndirectedGraphNode>(); } * }; */ public class Solution { public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) { if(node==null)return null; help(node); for(Map.Entry<UndirectedGraphNode,UndirectedGraphNode>entry:map.entrySet()){ List<UndirectedGraphNode> list=entry.getKey().neighbors; List<UndirectedGraphNode> newlist=new ArrayList<UndirectedGraphNode>(); for(int i=0;i<list.size();i++){ newlist.add(map.get(list.get(i))); } entry.getValue().neighbors=newlist; } return newheadall; } UndirectedGraphNode newheadall; HashMap<UndirectedGraphNode,UndirectedGraphNode> map=new HashMap<>(); boolean mark=true; public void help(UndirectedGraphNode node){ UndirectedGraphNode newnode=new UndirectedGraphNode(node.label); map.put(node,newnode); if(mark){ mark=false; newheadall=newnode; } List<UndirectedGraphNode> list=node.neighbors; for(int i=0;i<list.size();i++){ if(!map.containsKey(list.get(i))){ help(list.get(i)); } } } }

    转载请注明原文地址: https://ju.6miu.com/read-50392.html

    最新回复(0)