题目描述
难度:Middle
相关话题:深度优先搜索
、广度优先搜索
、图
给定无向连通
图中一个节点的引用,返回该图的深拷贝
(克隆)。图中的每个节点都包含它的值 val
( Int
) 和其邻居的列表( list[Node]
)。
示例:
输入:{"$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 的邻居。
-
必须将给定节点的拷贝 作为对克隆图的引用返回。
思路:
这是一个带有环的图,因此hash
必须在执行遍历neighbors
之前保存当前的copy Node
,这样后面如果遇到循环引用,也能引用到hash
里的copy Node
。
遍历neighbors
并且填充copy Node.neighbors
。
/**
* @ Javascript中文网 - 前端进阶资源教程 https://www.javascriptc.com/
* // Definition for a Node.
* function Node(val,neighbors) {
* this.val = val;
* this.neighbors = neighbors;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function(node) {
let hash={}
function clone(node){
let val=node.val,adj=node.neighbors
if(hash[val])return hash[val]
let copy=new Node(val,[])
hash[val]=copy
for(let i=0;i<adj.length;i++){
copy.neighbors[i]=clone(adj[i])
}
return copy
}
return clone(node)
};
看完两件小事
如果你觉得这篇文章对你挺有启发,我想请你帮我两个小忙:
- 把这篇文章分享给你的朋友 / 交流群,让更多的人看到,一起进步,一起成长!
- 关注公众号 「画漫画的程序员」,公众号后台回复「资源」 免费领取我精心整理的前端进阶资源教程
本文著作权归作者所有,如若转载,请注明出处
转载请注明:文章转载自「 Js中文网 · 前端进阶资源教程 」https://www.javascriptc.com