当前位置: 首页 > 科技观察

刚学会深拷贝对象,学妹问我怎么深拷贝图片

时间:2023-03-19 16:39:58 科技观察

转载请联系bigsai公众号。前言里写了Java的深浅拷贝,就是基于对象的拷贝,但是看数据结构和算法,有没有考虑过怎么拷贝一个图?(无向图)在此之前,你需要明确一些概念:什么是深拷贝和浅拷贝?浅拷贝:如果拷贝是引用类型(非基本类型),只会拷贝一层(不会拷贝嵌套对象),如果原对象发生变化,那么拷贝的对象也会发生变化。深拷贝:深拷贝会拷贝多层,嵌套的对象也会拷贝出来,相当于开辟了一个新的内存地址用于存放拷贝的对象。用更通俗(可能不完全准确)的话来解释,浅拷贝就像你的孪生兄弟,你的父母和亲人一样;而深拷贝就像另一个平行时空,那里有另一个你。了解了深拷贝和浅拷贝及其区别之后,我们再来看一下图。图一般用来表示节点之间的关系,常分为有向图和无向图。这里我们使用无向图(一旦连接即双向)作为主题。我们一般用邻接矩阵和邻接表来表示图。邻接矩阵更直观的表示图的连通性,运维更简单。在Java中,一般用二维数组来表示邻接矩阵。数组中的值可以代表两个节点的权重。邻接矩阵表示一个图。使用邻接矩阵虽然简单,但是浪费了更多的内存空间。因此,在很多情况下,邻接表被用来表示一个图。邻接表一般就是这样一个数组和链表的组合。但也有一些特殊情况,每个节点都是相对独立的,不需要用数组来组合。图问题分析的邻接表表示如果此图由邻接表表示,并且给你一个无向连通图中节点的引用,请返回该图的深拷贝(克隆)。这个问题就是131克隆图的原问题。图中的每个节点都包含它的值val(int)和它的邻居列表(list[Node])。classNode{publicintval;publicListneighbors;}图像的来源是对节点的引用。如何克隆这个图?如果只有这个节点,那么克隆这个节点即可。如果该节点只有一层邻居,则只需克隆邻居列表(克隆List集合)。但事实是这个节点可能有多层邻居,邻居之间可能有复杂的联系。图有可能克隆整个图,因此必须克隆图的每个节点。我们需要利用图论的搜索算法来枚举所有的节点,在遍历过程中需要想办法找到节点之间的关系。也是克隆出来的。遍历方式可以使用dfs或者bfs,这里使用bfs。每当我们遇到困难时,我们都可以模拟克隆过程。通过下图,我们可以大致了解克隆图的过程。最大的问题是避免创建重复节点。也就是说,一旦创建了一些节点,它们的引用可能会在以后使用。模拟克隆过程,那么我们如何解决这个问题呢?怎样才能快速找到对应节点的引用呢?这里最好的方式是使用HashMap,key存放的是克隆图中的节点,value是克隆图中的节点。这样,在克隆新图的过程中,当我们遍历节点的邻居时对于克隆图,我们可以通过哈希来判断该节点对应的值是否存在(即该节点是否存在于克隆图中)。如果存在,则直接使用HashMap找到对应的节点,放入克隆图中新建的List中。但是不存在,说明第一次遇到这个节点,clone这个节点,先把它放到被克隆节点对应的hashMap中,然后再放到clonemap中新建的List中。这个过程大致是这样的:其中一个进程Map的变化和作用,经过上面的分析,想必你对解决这个问题有了思路和思路,下面给出代码实现。/*//DefinitionforaNode.classNode{publicintval;publicListneighbors;publicNode(){val=0;neighbors=newArrayList();}publicNode(int_val){val=_val;neighbors=newArrayList();}publicNode(int_val,ArrayList_neighbors){val=_val;neighbors=_neighbors;}}*/classSolution{publicNodecloneGraph(Nodenode){if(node==null)returnnull;Mapmap=newHashMap();//节点映射克隆节点Queueoldqueue=newArrayDeque();//bfs队列oldqueue.add(node);Nodevalue=newNode(node.val);//首先创建并映射返回的节点map.put(node,value);while(!oldqueue.isEmpty()){Nodeoldnode=oldqueue.poll();Nodenewnode=map.get(oldnode);//找到这个节点的映射对应clone(必须存在)Listlist=oldnode.neighbors;//NeighborsListlistnew=newArrayList();//Cloneneighborsfor(Nodeteam:list){if(map.containsKey(team)){listnew.add(map.get(team));//之前遇到过的点,直接加入邻居列表}else{//这个邻居是enc第一次失败,需要创建一个新节点并赋值Nodeno=newNode(team.val);map.put(team,no);//maplistnew.add(no);oldqueue。add(team);//这个点是第一次遇到,放入队列中供bfs搜索}}newnode.neighbors=listnew;//将节点的邻居指向列表}returnvalue;}}结论到此为止,本篇内容到此结束,后面会继续分享一些优秀而巧妙的问题和算法,对本篇进行总结。如果有帮助,请点个赞,观看分享一波!