阅读 11

关于去重等等一系列

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)); } }

关注下面的标签,发现更多相似文章
评论