「No.64」【 每日壹题 】
冰洋 2/4/2020 编程题
当你发现自己的才华撑不起你的野心时,就请安静下来学习吧!
🌿【壹题】🌿 请分别用深度优先思想和广度优先思想实现一个拷贝函数?
鲁迅说过:
答案仅供参考...
🌿【解析】🌿
# 前置知识
- DFS (opens new window):深度优先搜索算法(Depth-First-Search)
- BFS (opens new window):广度优先算法(Breadth First Search)
# 解法
// 如果是对象/数组,返回一个空的对象/数组,
// 都不是的话直接返回原对象
// 判断返回的对象和原有对象是否相同就可以知道是否需要继续深拷贝
// 处理其他的数据类型的话就在这里加判断
function getEmpty(o){
if(Object.prototype.toString.call(o) === '[object Object]'){
return {};
}
if(Object.prototype.toString.call(o) === '[object Array]'){
return [];
}
return o;
}
function deepCopyBFS(origin){
let queue = [];
let map = new Map(); // 记录出现过的对象,用于处理环
let target = getEmpty(origin);
if(target !== origin){
queue.push([origin, target]);
map.set(origin, target);
}
while(queue.length){
let [ori, tar] = queue.shift();
for(let key in ori){
// 处理环状
if(map.get(ori[key])){
tar[key] = map.get(ori[key]);
continue;
}
tar[key] = getEmpty(ori[key]);
if(tar[key] !== ori[key]){
queue.push([ori[key], tar[key]]);
map.set(ori[key], tar[key]);
}
}
}
return target;
}
function deepCopyDFS(origin){
let stack = [];
let map = new Map(); // 记录出现过的对象,用于处理环
let target = getEmpty(origin);
if(target !== origin){
stack.push([origin, target]);
map.set(origin, target);
}
while(stack.length){
let [ori, tar] = stack.pop();
for(let key in ori){
// 处理环状
if(map.get(ori[key])){
tar[key] = map.get(ori[key]);
continue;
}
tar[key] = getEmpty(ori[key]);
if(tar[key] !== ori[key]){
stack.push([ori[key], tar[key]]);
map.set(ori[key], tar[key]);
}
}
}
return target;
}
// test
[deepCopyBFS, deepCopyDFS].forEach(deepCopy=>{
console.log(deepCopy({a:1}));
console.log(deepCopy([1,2,{a:[3,4]}]))
console.log(deepCopy(function(){return 1;}))
console.log(deepCopy({
x:function(){
return "x";
},
val:3,
arr: [
1,
{test:1}
]
}))
let circle = {};
circle.child = circle;
console.log(deepCopy(circle));
})
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
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
参考答案 (opens new window) --- 感谢【Daily-Interview-Question】 (opens new window)