leetcode上的“深拷贝类”题目

1 总结

1.1 图的深拷贝背后涉及到的应用场景（涉及到序列化和gc）

课本上总说deep copy和shallow copy，似懂非懂的，不觉得这东西有什么用。慢慢地，发现deep copy背后隐藏的逻辑其实是一种对象图（Object Graph）的遍历行为——这东西广泛出现在各语言的垃圾回收、序列化机制里。内存里各个对象存储空间中放置的引用域/指针就好像有向图里一条边，你沿着它去到达内存中的每个角落、去到当前对象所有的关联对象。题设里的neibours就像一道开胃菜，它可以是其他collection、甚至object，学会这个deep copy，你也就学会了GC里的可达性分析、你也就学会了如何把RAM中的数据固化到硬盘里。

1.2 解决深拷贝问题的底层逻辑是什么

2 lc138. 随机链表的复制

2.1 关键是使用哈希表定义原节点到拷贝节点的映射，方便以O(1)复杂度定位

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node>mp=new HashMap<>();

        Node node=head;
        while(node!=null){
            Node next=node.next;
            mp.put(node,new Node(node.val));
            node=next;
        }

        node=head;
        while(node!=null){
            Node next=node.next;
            mp.get(node).next=mp.get(node.next);
            mp.get(node).random=mp.get(node.random);

            node=next;
        }
        return mp.get(head);
    }
}

3 LC133. 克隆图

3.1 分析

解法和2相似，都是基于hashMap做的，这是核心技巧

3.2 代码

    public Node cloneGraph(Node node) {
        if(node==null){
            return null;
        }

        HashMap<Node,Node>vis=new HashMap<>();

        Deque<Node>q=new LinkedList<>();


        vis.put(node,new Node(node.val, new ArrayList<>()));

        q.offerLast(node);

        while(!q.isEmpty()){
            Node cur=q.pollFirst();

            for(Node n:cur.neighbors){
                if(!vis.containsKey(n)){
                    vis.put(n,new Node(n.val,new ArrayList<>()));
                    q.offerLast(n);
                }
                vis.get(cur).neighbors.add(vis.get(n));
            }
        }

        return vis.get(node);
    }