刷

July-03-2019

这个题比较诡异。题里说的unique是指任何VAL是1的点其实都是指向1个。

做法是先走一遍，记录所有的已经存在的node： Node[100]。

复制一遍记录的所有Node，此时复制的只有里面的val，复制出的copyNode的neighbor还没做好，也就是说复制出来的copyNodes之间的指向关系还没建立好。

然后走一遍复制过的所有copyNodes,通过copyNode.val来找到对应的node，然后把node里的所有neighbor加到copyNode的neighbor里：比如neighbor-3要加在copyNode里的是copy[3]

有点绕= =

class Solution {    public Node cloneGraph(Node node) {        if (node == null) return null;        Node[] nodes = fillNodes(node);        Node[] copies = new Node[101];        for (int i = 0; i < 101; i ++) {            if (nodes[i] != null) {                copies[i] = new Node(nodes[i].val, new ArrayList<>());            }        }        Arrays.stream(copies).forEach(copy -> {            if (copy != null) {                nodes[copy.val].neighbors.stream().forEach(realNeighbor -> {                    copy.neighbors.add(copies[realNeighbor.val]);                });            }        });                return copies[node.val];            }        public Node[] fillNodes(Node node) {        Node[] nodes = new Node[101];        boolean[] visited = new boolean[101];        if (node == null) return nodes;        ArrayDeque
    
      q = new ArrayDeque<>();        q.offerLast(node);        visited[node.val] = true;                while (!q.isEmpty()) {            Node tempNode = q.pollFirst();            nodes[tempNode.val] = tempNode;            tempNode.neighbors.stream()                .filter(neighbor -> !visited[neighbor.val])                .forEach(neighbor -> {                    q.offerLast(neighbor);                    visited[neighbor.val] = true;                });        }                return nodes;    }}
    

---

四刷。。

这傻屌题都四刷了么。。

public class Solution {    Map
    
      map = new HashMap<>();    public UndirectedGraphNode cloneGraph(UndirectedGraphNode node) {        if (node == null) return null;            if (!map.containsKey(node.label)) {            map.put(node.label, new UndirectedGraphNode(node.label));        }         UndirectedGraphNode res = map.get(node.label);        res.neighbors = new ArrayList
     
      ();                for (UndirectedGraphNode n : node.neighbors) {            if (!map.containsKey(n.label)) {                res.neighbors.add(cloneGraph(n));            } else {                res.neighbors.add(map.get(n.label));            }        }                return res;    }}