let arr = [ [ ['1-7', '2-6'], '4-6', [ ['2-0', '1-4'], ['3-9'], '4-5', ], ] ]
// Q1: 完成数组 flat 函数 function flat(arr) { // code return arr }
arr = flat(arr); console.log(arr);
// Q2: 计算 arr 中所有的值：'1-7' => 1 * 7 = 7， 返回一个数字组成的数组 function calc(arr) { // code return arr; }
arr = calc(arr); console.log(arr);
// Q3: 对这个数组排序和去重 function sortAndReduce(arr) { // code return arr; }
arr = sortAndReduce(arr); console.log(arr);
数组 Flat 时间回溯 这个数组结构比较深，这应该是整个题目的考点所在。看这个样子应该是需要用递归，不！应该还有更好的方法，那就使用ES 2019 的 Array.prototype.flat 函数吧！然后被面试官一票否决。在涂涂改改和思考的时间中，面试官问了我的思路结束了这个问题。 方案1： 递归 如果有对递归不太熟悉的同学，可以看看我的读书笔记【算法图解】读书笔记：第3章 递归。 递归的核心就在于两步：找到基线条件和递归条件。 function flat(arr) { const result = []; // 利用闭包缓存我们的结果 function _flat(arr) { arr.forEach(element => { if(Array.isArray(element)) { // 递归条件 _flat(element); } else { // 基准条件 result.push(element); // 将符合结果的值推入我们的结果数组中 } }) } _flat(arr); arr = result; return arr; }
// 更加简练的版本
const flat = arr => [].concat(...arr.map(v => Array.isArray(v) ? flat(v) : v)); 复制代码方案2： 迭代 - 广度优先搜索 这个思路是我借鉴《图解算法》中广度优先搜索算法章节写的。
创建一个数组，保存结果 创建一个队列 初始化 使用 while 循环去遍历 list 里面的每一项 将第一项推出队列
如果是数组，将子项依次推入队列 如果是字符串，将子项推入结果
当 list 长度为0时候，遍历完成
但是广度优先搜索的结果是不保证顺序的。
参考书籍：《图解算法》 不推荐的笔记，没书可以看看【算法图解】读书笔记：第6章 广度优先搜索
function flat(arr) { const result = []; // 储存结果 const list = []; // 队列 function _forEach(arr) { arr.forEach(el => { if(Array.isArray(el)) list.push(el); // item 如果是数组，将子项依次推入队列 else result.push(el); // item 如果是字符串，将子项推入结果 }); } _forEach(arr); // 初始化 while(list.length > 0) { // 当 list 长度为0时候，遍历完成 const item = list.shift(); _forEach(item); }
上面两个方法只是我的拙见，希望可以在评论区看见更好更优秀的算法
方案3: 投机取巧的 toString 们
// 首页你得确定你的数据里面没有字符串 ',' 哦 function flat(arr) { arr = arr.toString().split(',') return arr; }
// or // 异曲同工 function flat(arr) { arr = arr.join(',').split(',') return arr; } 迭代 - 深度优先搜索 感谢 @IWANABETHATGUY 同学的赐教。 原理与广度优先搜索类似，通过模拟栈的行为去遍历数组。好处是能够保证有序输出。 function flat(arr) { let result = []; let stack = []; // 模拟栈的行为
function forEachRight(arr) { for (let i = arr.length - 1; i >= 0; i--) { // 先进后出 const item = arr[i]; if(Array.isArray(item)) stack.push(item); else result.push(item); } } if (arr.length > 0) forEachRight(arr); while (stack.length > 0) { // 当栈空了，遍历完成 let current = s.pop(); if(current.length > 0) { forEachRight(current); // 感谢 @Drowned-fish 朋友的建议 } } return ret; } 数组计算 '1-7' => 1 * 7 = 7 这个问题难度不大，就是考察一些常用方法的使用，直接上代码。 function calc(arr) { // 随手骚一下，不建议 eval arr = arr.map(el => eval(el.replace('-', '*'))); return arr; }
// or
function calc(arr) { arr = arr.map(el => { const [n1, n2] = el.split('-'); return +n1 * +n2; }); return arr; }
Q3: 数组排序和去重 数组去重可以通过 ES6 的 Set 完成。传送门：ES6 Set 数据结构，不作赘述。数组排序可以使用 Array.prototype.sort 函数实现。但是显然考察算法内容，不能直接使用原生方法，而且排序和去重同时完成，性能肯定更好。 我之前写过一篇常规的几种排序方法的对比和实现，【JS面试向】选择排序、桶排序、冒泡排序和快速排序简介，这里我直接使用快速排序完成排序和去重工作。 function sortAndReduce(arr) { if(arr.length < 2) { return arr; } else { const pivot = arr[0]; // 基准值 const lowArr= []; // 小的放左边 const hightArr = []; // 大的放右边 arr.forEach(current => { if(current > pivot) hightArr.push(current); else if(current < pivot) lowArr.push(current); }) return sortAndReduce(lowArr).concat(pivot, sortAndReduce(hightArr)); } }
