面试题是这样描述的,一个人从北京出发,坐火车去旅行,途经N个城市,目的地是上海,拿到这些火车票如何对其进行排序。
记得当时的面试官给了我一根马克笔让我用代码将其写出来,好像是写在会议室的玻璃墙上,幸好笔者机智作答拿到offer,今天就跟大家分享一下这道题的思路。
我刚接到这个题目的时候是有点懵逼的,只有上面面试官给的一句话,写什么代码呢?
冷静下来再仔细分析一下这个题目的描述,本质就是数组排序啊,只不过这个数组比较特殊,数组的每一项应该是一个对象,对象有两个属性,即每张票的起始站和终点站。
所以第一步应该是构建这个数据结构,如下:
var arr =[
{ start: '肃宁', end: '长沙' },
{ start: '沧州', end: '任丘' },
{ start: '任丘', end: '肃宁' },
{ start: '长沙', end: '武汉' },
{ start: '武汉', end: '上海' },
{ start: '北京', end: '沧州' }
]
模拟出数据结构了,下一步就是将其按照顺序排列出来。解题思路大致是先找出旅行的起始站那张票,然后循环遍历这个数组,根据当前项的终点站和下一张票的起始站相同,查找出下一张火车票,从而将顺序排列出来。
如何用代码将第一张票找出来呢?可以仔细观察一下这个数据,发现如下特点:第一张车票的起始站绝对不会出现在终点站里面出现,利用这个特点将起始站的车票查找出来,代码如下(详解见注释):
// 计算出每趟车的起始站
var startarr= arr.map((e,l)=>{
return e.start;
});
// 计算出每趟车的终点站
var endarr =arr.map((e,l)=>{
return e.end
});
// 定义一个新数组
var arr2 = [];
// 利用旅行目的的起始站绝对不会出现在终点站里面,将其筛选出来,填充进数组;
for(var i=0;i<startarr.length;i++){
if(endarr.indexOf(startarr[i])==-1){
let a= arr.filter((e,t)=>{
return e.start == startarr[i]
})
arr2.push(a[0])
}
}
之后循环遍历乱序的车票数组,每次循环取出arr2数组的最后一项,根据这一项的end属相,到乱序数组中查询start属性与其相同的车票,查找到之后将其推进arr2数组,循环遍历完,得到排序完成的数组,代码如下:
for(var i=0;i<arr.length;i++){
let ticket = arr2[arr2.length-1];
var tt = arr.filter((e)=>{
return e.start ==ticket.end
});
if(tt.length==1){
arr2.push(tt[0])
}
}
今天回过头来看这些代码,当然是略显稚嫩了,所以用se6的一些特性对上面代码做了一次优化,代码如下:
var arr =[
{ start: '肃宁', end: '长沙' },
{ start: '沧州', end: '任丘' },
{ start: '任丘', end: '肃宁' },
{ start: '长沙', end: '武汉' },
{ start: '武汉', end: '上海' },
{ start: '北京', end: '沧州' }
]
let a = arr.filter((e,i,arr)=>arr.map(v=>v.end).indexOf(e.start) == -1);
let b = arr.reduce((pre,cur,index,arr)=>{
return pre.concat(arr.filter((e,i)=>{
return e.start == pre[pre.length-1].end;
}));
},a)
console.log(b);
思路是一样的但是却使用了es6的一些语法,当然大家有其他方法可以留言。
记得以前一位年长的程序员对我说过,程序员提高自己的方法有很多种,其中一种方法就是读一下自己以前写的代码,看看能否将其优化重构。在这个过程中,现在的你和原先的你通过代码做了一次沟通,能清楚的检验自己的成长,从而达到温故而知新。
程序员这个职业是需要不断去学习的,但是学习不只是无止境的学习新的知识,还包括温故知新。希望对大家有帮助。
上一篇文章介绍了数组去重的几种方法,后来有朋友留言或者给我发消息分享了一些其他的方法,原理就不一一介绍了,代码如下供大家参考:
function unique(arr){
return Array.from(new Set(arr));
}
function unique(arr){
return [...new Set(arr)];
}
function unique(arr){
var obj = {};
return arr.filter(e=>{return !obj[e]&&(obj[e]=1)})
}
主要是使用了一些es6的特性,有兴趣的朋友可以打开编辑器测试一下。欢迎大家转发或者留言。