今天分享一道面试手写笔试题,主要是考察数据结构处理,以及数据引用问题
题目是下面这样的:将原数据根据pid
进行转换成一个tree
结构,也就是将pid
归类到id
相等的分组中去,当前的pid
与id
不会相等
// 原数据
var sourceData = [
{ id: 0, pid: 1, order: 1 },
{ id: 1, pid: 0, order: 1 },
{ id: 2, pid: 0, order: 1 },
{ id: 3, pid: 2, order: 1 },
{ id: 4, pid: 2, order: 1 },
{ id: 5, pid: 2, order: 1 },
{ id: 5, pid: 3, order: 1 },
{ id: 6, pid: 5, order: 1 },
{ id: 7, pid: 1, order: 2 }
];
转换成以下数据结构
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
{
"id": 2,
"pid": 0,
"order": 1,
"child": [
{
"id": 3,
"pid": 2,
"order": 1,
"child": [
{
"id": 5,
"pid": 3,
"order": 1,
"child": []
}
]
},
{
"id": 4,
"pid": 2,
"order": 1,
"child": []
},
{
"id": 5,
"pid": 2,
"order": 1,
"child": []
}
]
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
{
"id": 2,
"pid": 0,
"order": 1,
"child": [
{
"id": 3,
"pid": 2,
"order": 1,
"child": [
{
"id": 5,
"pid": 3,
"order": 1,
"child": []
}
]
},
{
"id": 4,
"pid": 2,
"order": 1,
"child": []
},
{
"id": 5,
"pid": 2,
"order": 1,
"child": []
}
]
},
{
"id": 3,
"pid": 2,
"order": 1,
"child": [
{
"id": 5,
"pid": 3,
"order": 1,
"child": []
}
]
},
{
"id": 4,
"pid": 2,
"order": 1,
"child": []
},
{
"id": 5,
"pid": 2,
"order": 1,
"child": []
},
...
]
大致思路就是双层循环,后面的pid是否等于前面的id,如果相等就添加一个child
属性,并将数据添加到 child
const transformTree = (source) => {
// 拷贝一份新的数据
let newData = JSON.parse(JSON.stringify(source));
for (let i = 0; i < newData.length; i++) {
const item = newData[i];
// 每一项添加一个child属性
item.child = [];
for (let j = i + 1; j < newData.length; j++) {
// 0-1,0-2,0-3,...,1-1,1-2...这样依次比较
if (item.id === newData[j].pid) {
item.child.push(newData[j]);
}
}
}
return newData
}
console.log(JSON.stringify(transformTree(sourceData), null, 2));
console.log(sourceData);
最后的结果就是我们前面看到的,但是我们会发现其实数据结构里面会是这样的
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
},
...
]
在id=0
的根数据上,我们看到添加进去了child
,child
里面又有与id
相同的pid
数据,所以你看到了一个树的结构。但是我们看到之前并没有用递归的方式。这就是很奇怪了?我们仔细思考下
当i=0
时,然后依次循环当前i=0
会动态新增一个child
属性, arr[0].child = []
当j=1
时,arr[1].child = [],此时arr[1].pid === arr[0].id
,所以就会把当前的arr[1]
添加到arr[0].child
中
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
}
}
...
]
当i=1
时,此时也会动态添加一个child
属性, arr[1] = []
, 此时你会发现,会变成下面这样
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": []
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": []
}
...
]
当j=6
时,arr[6].pid===arr[1].id
,然后你arr[1].child.push(arr[6])
[
{
"id": 0,
"pid": 1,
"order": 1,
"child": [
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
],
}
]
},
{
"id": 1,
"pid": 0,
"order": 1,
"child": [
{
"id": 7,
"pid": 1,
"order": 2,
"child": []
}
]
}
...
]
本质上这两个数据就是同一份引用
我们也看到我们对原数据进行一份深拷贝,这样处理就不会影响原数据,正常情况我们处理原数据,涉及到新值删除操作时,最好不要在原有数据上进行操作。
关于数据引赋值问题可以分析下面的一个问题
const obj = { c: 1 };
const obj2 = obj;
obj2.c = '22';
console.log(obj.c, obj2.c)
结果就是22,22
但是下面这样的呢
var name = 'Maic';
var cnane = name;
cname = 'Web技术学苑';
console.log(name, cname);
我们发现结果就是Maic, Web技术学苑
,与上面正好不太一样
我们继续看下下面这段代码
const obj3 = { name: 'Maic', info: { name: 'Web技术学苑' } }
const obj4 = { ...obj3 };
obj4.name = 'Tom';
obj4.info.name = 'infoQ';
console.log(obj3, obj4)
最后的结果:
obj3:{ name: 'Maic', info: { name: 'infoQ' } }
obj4:{ name: 'Tom', info: { name: 'infoQ' } }
这涉及一个问题就是基础数据类型与引用类型赋值的问题,对象与基础数据类型赋值是值拷贝,而扩展运算符是浅拷贝
,当值拷贝一个引用数据类型,新的值修改会影响原有的值,当浅拷贝一份数据时,如果对象key的值是基础数据类型,那么新值修改不会影响原值,如果是引用数据类型,那么新值会影响原有的值
最后,看下另外一种比较简单的写法,不过功能是一样的
const transformTree3 = (source) => {
const arr = JSON.parse(JSON.stringify(source));
for (let i = 0; i < arr.length; i++) {
const item = arr[i];
// 从剩下的元素中过滤获取id与pid的数据归类
item.child = arr.slice(i + 1, arr.length).filter(v => v.pid === item.id);
}
return arr;
}
console.log(JSON.stringify(transformTree3(sourceData), null, 2));
es6
扩展运算符来浅拷贝原数据时,如果原数据key对应的值时引用数据类型,那么修改新值会影响原有的值,如果是基础数据类型,那么修改新值不会影响原有的值[1]code example: https://github.com/maicFir/lessonNote/tree/master/面试题/04-数据结构转换
最后,看完觉得有收获的,点个赞,在看,转发,收藏等于学会,欢迎关注Web技术学苑,好好学习,天天向上!