137. Clone Graph

  1. 不知道为什么我的记忆里这道题要遍历两遍。NONONONO!只需要一次Queue的BFS遍历。利用hashmap保存原件和复印件。
  2. BFS的过程中,出队列的node的每一个neighbors创建其复印件,然后如果map里没有neighbor,添加neighbor-copy进map,然后neighbor入队,然后从map里找到node的复印件(注意是node也就是爸爸的)把所有新的复印件加到它的neighbor list里。 如果map里已有neighbor,说明不是第一次见了,也就是map里已有这个nei的复印件,找到map里nei的这个复印件,把它加进node的复印件(注意是node也就是爸爸的)加到它的neighbor list里。

while(!q.isEmpty()){
 UndirectedGraphNode n = q.poll();
 if(n.neighbors.size()!=0){ //noted could be a lone node
 for(UndirectedGraphNode nei : n.neighbors){
 UndirectedGraphNode copy = new UndirectedGraphNode(nei.label);
 
 if(!map.containsKey(nei)){
 map.put(nei, copy);
 q.offer(nei);
 map.get(n).neighbors.add(copy);
 }
 else{
 map.get(n).neighbors.add(map.get(nei)); 
 }}}}

One clap, two clap, three clap, forty?

By clapping more or less, you can signal to us which stories really stand out.