LeetCode 133:克隆图 Clone Graph
题目:
给定无向连通图中一个节点的引用,返回该图的深拷贝(克隆)。图中的每个节点都包含它的值 val
(Int
) 和其邻居的列表(list[Node]
)。
Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int
) and a list (List[Node]
) of its neighbors.
示例:
输入: {"$id":"1","neighbors":[{"$id":"2","neighbors":[{"$ref":"1"},{"$id":"3","neighbors":[{"$ref":"2"},{"$id":"4","neighbors":[{"$ref":"3"},{"$ref":"1"}],"val":4}],"val":3}],"val":2},{"$ref":"4"}],"val":1} 解释: 节点 1 的值是 1,它有两个邻居:节点 2 和 4 。 节点 2 的值是 2,它有两个邻居:节点 1 和 3 。 节点 3 的值是 3,它有两个邻居:节点 2 和 4 。 节点 4 的值是 4,它有两个邻居:节点 1 和 3 。
提示:
- 节点数介于 1 到 100 之间。
- 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
- 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
- 必须将给定节点的拷贝作为对克隆图的引用返回。
Note:
- The number of nodes will be between 1 and 100.
- The undirected graph is a simple graph#Simple_graph), which means no repeated edges and no self-loops in the graph.
- Since the graph is undirected, if node p has node q as neighbor, then node q must have node p as neighbor too.
- You must return the copy of the given node as a reference to the cloned graph.
解题思路:
涉及到图的遍历无非就是DFS(深度优先搜索)、BFS(广度优先搜索),可以先看前几日的这篇文章:
BFS就需要借助队列实现,DFS可以借助栈也可以直接用递归实现。就这道题而言直接用递归更好一些,无需开辟额外的数据结构空间记录节点。BFS、DFS写法相对固定,建议花点时间一次性理解透,一劳永逸。
这道题思路很清晰,关键点是如何深拷贝随机节点,可以参考链表的这篇文章:LeetCode 138:复制带随机指针的链表 Copy List with Random Pointer
链表是线性的,可以 复制节点到每个节点之后,很巧妙的完成深拷贝。显然图这样的树状结构无法用这种方法,只能借助数据结构记录已拷贝过的节点。这种需要映射新旧节点关系自然就是用散列表(字典)。
Java:
class Solution { public Node cloneGraph(Node node) { if (node == null) return node; Queue<Node> queue = new LinkedList<>();//借助队列实现BFS Map<Node, Node> map = new HashMap<>();//哈希映射 Node head = new Node(node.val, new ArrayList<>());//头节点 map.put(node, head);//哈希映射原节点和新节点 queue.add(node);//原节点加入到队列 while (!queue.isEmpty()) {//队列不为空就重复循环 Node tmp = queue.poll();//弹出队列头节点 for (Node n : tmp.neighbors) {//遍历邻居节点 if (!map.containsKey(n)) {//字典的键不包含该节点时 map.put(n, new Node(n.val, new ArrayList<>()));//新建映射关系加入字典 queue.add(n);//加入队列 } map.get(tmp).neighbors.add(map.get(n));//加入邻居节点 } } return head; } }
Python3:
class Solution: def cloneGraph(self, node: 'Node') -> 'Node': if not node: return node head = Node(node.val, [])#头节点 map = {node: head}#初始化字典,并建立新旧节点的映射关系 queue = collections.deque()#队列 queue.append(node)#原节点加入队列 while queue:#队列不为空 tmp = queue.popleft()#弹出队列头节点 for n in tmp.neighbors:#遍历邻居节点 if n in map.keys():#n节点存在于字典的键里时 map[tmp].neighbors.append(map[n])#直接加入到新节点的邻居节点 else: map[n] = Node(n.val, [])#新建节点并建立映射关系 map[tmp].neighbors.append(map[n])#由新建的映射关系取出节点并加入邻居节点 queue.append(n)#该邻居节点加入队列 return head
DFS:
递归完成的深度优先搜索非常简洁,比较容易理解,唯一要注意的就是需要把字典定义在函数外。
Java:
class Solution { Map<Node, Node> map = new HashMap(); public Node cloneGraph(Node node) { if (node == null) return node; map.put(node, new Node(node.val, new ArrayList<>()));//每次都要新建节点并建立映射关系 for (Node n : node.neighbors) { if (map.containsKey(n)) map.get(node).neighbors.add(map.get(n)); else map.get(node).neighbors.add(cloneGraph(n)); } return map.get(node); } }
Python3:
class Solution: map = dict() def cloneGraph(self, node: 'Node') -> 'Node': if not node: return node self.map[node] = Node(node.val, []) for n in node.neighbors: if n in self.map.keys(): self.map[node].neighbors.append(self.map[n]) else: self.map[node].neighbors.append(self.cloneGraph(n)) return self.map[node]
注意:
python中的字典取values时可以 dict().get(key)
也可以 dict[key]
时间复杂度都为1,但是在做算法题时肯定要用 dict[key]
这种方式。因为 get() 方法虽然效果一样,但是反复调用函数造成的时间消耗非常高,python语言本来就慢,应该养成尽可能优化代码的习惯。
欢迎关注微.信公.众号:爱写Bug
低调大师中文资讯倾力打造互联网数据资讯、行业资源、电子商务、移动互联网、网络营销平台。
持续更新报道IT业界、互联网、市场资讯、驱动更新,是最及时权威的产业资讯及硬件资讯报道平台。
转载内容版权归作者及来源网站所有,本站原创内容转载请注明来源。
- 上一篇
【从入门到放弃-Java】并发编程-JUC-locks-ReentrantReadWriteLock
前言 上文【从入门到放弃-Java】并发编程-JUC-locks-ReentrantLock我们了解到,ReentrantLock是一个互斥排他的重入锁,读和读、读和写、写和写不能同时进行。但在很多场景下,读多写少,我们希望能并发读,这时候ReentrantReadWriteLock就派上用场了,是专门针对这种场景设计的。接下来我们一起来学习下ReentrantReadWriteLock。 ReentrantReadWriteLock /** * Creates a new {@code ReentrantReadWriteLock} with * default (nonfair) ordering properties. */ public ReentrantReadWriteLock() { this(fal
- 下一篇
C#总结(七)动态加载C++动态链接库
C#调用C++ 链接库的方式分为静态调用和动态调用这两种方式。静态调用之前的文章里面都有介绍,使用.net 提供的DllImport 导入相关的C++ 库即可。请看之前的文章,https://www.cnblogs.com/zhangweizhong/p/8119340.html 。 今天介绍动态调用的方法。很多时候,Dll库的目录可能是变化的,或是有些场景,需要根据具体的情况,来动态加载这些Dll库。这样使用静态调用的方式就很不方便,C#中我们经常通过配置动态的调用托管Dll,那么是不是也可以这样动态调用C++动态链接呢?只要通过LoadLibrary, GetProcess, FreeLibrary这几个函数是可以动态调用动态链接的(它们包含在kernel32.dll中)。 原理LoadLibrary ( string lpFileName):载入指定的动态链接库,并将它映射到当前进程使用的地址空间。载入成功后即可访问库内保存的资源 , 除了LoadLibrary 方法,还有一个类似的 LoadLibraryEx 方法。 GetProcAddress (int hModule, s...
相关文章
文章评论
共有0条评论来说两句吧...
文章二维码
点击排行
推荐阅读
最新文章
- CentOS8安装Docker,最新的服务器搭配容器使用
- Docker使用Oracle官方镜像安装(12C,18C,19C)
- CentOS8编译安装MySQL8.0.19
- CentOS8,CentOS7,CentOS6编译安装Redis5.0.7
- SpringBoot2整合MyBatis,连接MySql数据库做增删改查操作
- SpringBoot2整合Redis,开启缓存,提高访问速度
- SpringBoot2配置默认Tomcat设置,开启更多高级功能
- Hadoop3单机部署,实现最简伪集群
- CentOS7,CentOS8安装Elasticsearch6.8.6
- CentOS6,7,8上安装Nginx,支持https2.0的开启