Clone Graph
1/31/2018
Solution:
思路:
分三步
1. clone nodes, 把所有nodes都找出来存在collection里面,hashset 和arraylist都可以。
2. 建立旧node和新node的联系,为第三步连接做准备,用hashmap。
3. 把每一个新node的每一个neighbor都找出来。根据和它相连的旧node,找出旧node的neighbors,然后通过mapping找到neighbors对应的新node,组成新neighbors赋给当前旧node。
Solution:
/** * 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; // copy nodes Queue<UndirectedGraphNode> queue = new LinkedList<>(); Set<UndirectedGraphNode> set = new HashSet<>(); queue.offer(node); set.add(node); while (!queue.isEmpty()) { UndirectedGraphNode curNode = queue.poll(); for(UndirectedGraphNode n: curNode.neighbors) { if (set.contains(n)) continue; queue.offer(n); set.add(n); } } // map old and new nodes Map<UndirectedGraphNode, UndirectedGraphNode> map = new HashMap<>(); for (UndirectedGraphNode n: set) { map.put(n, new UndirectedGraphNode(n.label)); } // assign neighbors for (UndirectedGraphNode n: set) { UndirectedGraphNode newNode = map.get(n); for (UndirectedGraphNode neib: n.neighbors) { newNode.neighbors.add(map.get(neib)); } } return map.get(node); } }
思路:
分三步
1. clone nodes, 把所有nodes都找出来存在collection里面,hashset 和arraylist都可以。
2. 建立旧node和新node的联系,为第三步连接做准备,用hashmap。
3. 把每一个新node的每一个neighbor都找出来。根据和它相连的旧node,找出旧node的neighbors,然后通过mapping找到neighbors对应的新node,组成新neighbors赋给当前旧node。
评论
发表评论