-
Notifications
You must be signed in to change notification settings - Fork 2
/
133.克隆图.html
111 lines (91 loc) · 3.52 KB
/
133.克隆图.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta http-equiv="X-UA-Compatible" content="IE=edge" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>133. 克隆图</title>
</head>
<body>
<script src="../helper/graph.js"></script>
<script>
// https://leetcode-cn.com/problems/clone-graph/
// 给你无向 连通 图中一个节点的引用,请你返回该图的 深拷贝(克隆)。
// 图中的每个节点都包含它的值 val(int) 和其邻居的列表(list[Node])。
// class Node {
// public int val;
// public List<Node> neighbors;
// }
// 测试用例格式:
// 简单起见,每个节点的值都和它的索引相同。例如,第一个节点值为 1(val = 1),第二个节点值为 2(val = 2),以此类推。该图在测试用例中使用邻接列表表示。
// 邻接列表 是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。
// 给定节点将始终是图中的第一个节点(值为 1)。你必须将 给定节点的拷贝 作为对克隆图的引用返回。
// 提示:
// 节点数不超过 100 。
// 每个节点值 Node.val 都是唯一的,1 <= Node.val <= 100。
// 无向图是一个简单图,这意味着图中没有重复的边,也没有自环。
// 由于图是无向的,如果节点 p 是节点 q 的邻居,那么节点 q 也必须是节点 p 的邻居。
// 图是连通图,你可以从给定节点访问到所有节点。
/**
* // Definition for a Node.
* function Node(val, neighbors) {
* this.val = val === undefined ? 0 : val;
* this.neighbors = neighbors === undefined ? [] :
neighbors;
* };
*/
/**
* @param {Node} node
* @return {Node}
*/
var cloneGraph = function (node) {};
// --- answer-1 ---
// 需要考虑循环引用的问题
var cloneGraph = function (node) {
const map = new WeakMap();
function clone(node) {
if (!node) return null;
if (map.has(node)) return map.get(node);
let nd = new Node(node.val, []);
map.set(node, nd); // 存储对象 可以避免节点的val一样的情况
for (let neighbor of node.neighbors) {
nd.neighbors.push(clone(neighbor));
}
return nd;
}
return clone(node);
};
// --- answer-1 ---
// --- answer-2 ---
// --- answer-2 ---
var adjList = [
[2, 4],
[1, 3],
[2, 4],
[1, 3]
];
var result = [
[2, 4],
[1, 3],
[2, 4],
[1, 3]
];
// 解释:
// var adjList = [[]];
// var result = [[]];
// 解释:输入包含一个空列表。该图仅仅只有一个值为 1 的节点,它没有任何邻居。
// var adjList = [];
// var result = [];
// 解释:这个图是空的,它不含任何节点。
// var adjList = [[2],[1]];
// var result = [[2],[1]];
var { graph: node } = buildUndirectedGraphByArray(adjList);
var cloneGraph = cloneGraph(node);
var cloneNode = buildArrayByUndirectedGraph(cloneGraph);
console.log('result = ', result);
console.log('cloneNode = ', cloneNode);
console.log('node = ', node);
console.log('cloneGraph = ', cloneGraph);
</script>
</body>
</html>