leetcode上的“深拷贝类”题目

发布时间:2024-01-03 12:53:46

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);
    }
文章来源:https://blog.csdn.net/yxg520s/article/details/135360190
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。