实现 LRU 淘汰算法
LRU 缓存算法是一个非常经典的算法，在很多面试中经常问道，不仅仅包括前端面试
LRU 英文全称是 Least Recently Used，英译过来就是” 最近最少使用 “的意思。LRU 是一种常用的页面置换算法，选择最近最久未使用的页面予以淘汰。该算法赋予每个页面一个访问字段，用来记录一个页面自上次被访问以来所经历的时间 t，当须淘汰一个页面时，选择现有页面中其 t 值最大的，即最近最少使用的页面予以淘汰
通俗的解释：
假如我们有一块内存，专门用来缓存我们最近发访问的网页，访问一个新网页，我们就会往内存中添加一个网页地址，随着网页的不断增加，内存存满了，这个时候我们就需要考虑删除一些网页了。这个时候我们找到内存中最早访问的那个网页地址，然后把它删掉。这一整个过程就可以称之为 LRU 算法
上图就很好的解释了 LRU 算法在干嘛了，其实非常简单，无非就是我们往内存里面添加或者删除元素的时候，遵循最近最少使用原则
使用场景
LRU 算法使用的场景非常多，这里简单举几个例子即可：
梳理实现 LRU 思路
特点分析：
我们需要一块有限的存储空间，因为无限的化就没必要使用LRU算发删除数据了。
我们这块存储空间里面存储的数据需要是有序的，因为我们必须要顺序来删除数据，所以可以考虑使用 Array、Map 数据结构来存储，不能使用 Object，因为它是无序的。
我们能够删除或者添加以及获取到这块存储空间中的指定数据。
存储空间存满之后，在添加数据时，会自动删除时间最久远的那条数据。
实现需求：
实现一个 LRUCache 类型，用来充当存储空间
采用 Map 数据结构存储数据，因为它的存取时间复杂度为 O(1)，数组为 O(n)
实现 get 和 set 方法，用来获取和添加数据
我们的存储空间有长度限制，所以无需提供删除方法，存储满之后，自动删除最久远的那条数据
当使用 get 获取数据后，该条数据需要更新到最前面
具体实现
class LRUCache { constructor(length) { this.length = length; // 存储长度 this.data = new Map(); // 存储数据 } // 存储数据，通过键值对的方式 set(key, value) { const data = this.data; if (data.has(key)) { data.delete(key) }
data.set(key, value);
// 如果超出了容量，则需要删除最久的数据 if (data.size > this.length) { const delKey = data.keys().next().value; data.delete(delKey); } } // 获取数据 get(key) { const data = this.data; // 未找到 if (!data.has(key)) { return null; } const value = data.get(key); // 获取元素 data.delete(key); // 删除元素 data.set(key, value); // 重新插入元素
return value // 返回获取的值 }}var lruCache = new LRUCache(5);
复制代码
// 测试
// 存储数据 set：
lruCache.set('name', 'test');lruCache.set('age', 10);lruCache.set('sex', '男');lruCache.set('height', 180);lruCache.set('weight', '120');console.log(lruCache);
复制代码
继续插入数据，此时会超长，代码如下：
lruCache.set('grade', '100');console.log(lruCache);
复制代码
此时我们发现存储时间最久的 name 已经被移除了，新插入的数据变为了最前面的一个。
我们使用 get 获取数据，代码如下：
我们发现此时 sex 字段已经跑到最前面去了
总结
LRU 算法其实逻辑非常的简单，明白了原理之后实现起来非常的简单。最主要的是我们需要使用什么数据结构来存储数据，因为 map 的存取非常快，所以我们采用了它，当然数组其实也可以实现的。还有一些小伙伴使用链表来实现 LRU，这当然也是可以的。
将虚拟 Dom 转化为真实 Dom
{ tag: 'DIV', attrs:{ id:'app' }, children: [ { tag: 'SPAN', children: [ { tag: 'A', children: [] } ] }, { tag: 'SPAN', children: [ { tag: 'A', children: [] }, { tag: 'A', children: [] } ] } ]}
把上面虚拟Dom转化成下方真实Dom
<div id="app"> <span> <a></a> </span> <span> <a></a> <a></a> </span></div>
复制代码
实现
// 真正的渲染函数function _render(vnode) { // 如果是数字类型转化为字符串 if (typeof vnode === "number") { vnode = String(vnode); } // 字符串类型直接就是文本节点 if (typeof vnode === "string") { return document.createTextNode(vnode); } // 普通DOM const dom = document.createElement(vnode.tag); if (vnode.attrs) { // 遍历属性 Object.keys(vnode.attrs).forEach((key) => { const value = vnode.attrs[key]; dom.setAttribute(key, value); }); } // 子数组进行递归操作 vnode.children.forEach((child) => dom.appendChild(_render(child))); return dom;}
复制代码
实现一个迭代器生成函数
ES6 对迭代器的实现
JS 原生的集合类型数据结构，只有Array（数组）和Object（对象）；而ES6中，又新增了Map和Set。四种数据结构各自有着自己特别的内部实现，但我们仍期待以同样的一套规则去遍历它们，所以ES6在推出新数据结构的同时也推出了一套 统一的接口机制 ——迭代器（Iterator）。
ES6约定，任何数据结构只要具备Symbol.iterator属性（这个属性就是Iterator的具体实现，它本质上是当前数据结构默认的迭代器生成函数），就可以被遍历——准确地说，是被for...of...循环和迭代器的 next 方法遍历。 事实上，for...of...的背后正是对next方法的反复调用。
在 ES6 中，针对Array、Map、Set、String、TypedArray、函数的 arguments 对象、NodeList 对象这些原生的数据结构都可以通过for...of...进行遍历。原理都是一样的，此处我们拿最简单的数组进行举例，当我们用for...of...遍历数组时：
const arr = [1, 2, 3]const len = arr.lengthfor(item of arr) { console.log(`当前元素是${item}`)}
复制代码
之所以能够按顺序一次一次地拿到数组里的每一个成员，是因为我们借助数组的Symbol.iterator生成了它对应的迭代器对象，通过反复调用迭代器对象的next方法访问了数组成员，像这样：
const arr = [1, 2, 3]// 通过调用iterator，拿到迭代器对象const iterator = arr[Symbol.iterator]()
// 对迭代器对象执行next，就能逐个访问集合的成员iterator.next()iterator.next()iterator.next()
复制代码
丢进控制台，我们可以看到next每次会按顺序帮我们访问一个集合成员：
而for...of...做的事情，基本等价于下面这通操作：
// 通过调用iterator，拿到迭代器对象const iterator = arr[Symbol.iterator]()
// 初始化一个迭代结果let now = { done: false }
// 循环往外迭代成员while(!now.done) { now = iterator.next() if(!now.done) { console.log(`现在遍历到了${now.value}`) }}
复制代码
可以看出，for...of...其实就是iterator循环调用换了种写法。在 ES6 中我们之所以能够开心地用for...of...遍历各种各种的集合，全靠迭代器模式在背后给力。
ps：此处推荐阅读迭代协议 (opens new window)，相信大家读过后会对迭代器在 ES6 中的实现有更深的理解。
实现深拷贝
简洁版本
简单版：
const newObj = JSON.parse(JSON.stringify(oldObj));
复制代码
局限性：
面试简版
function deepClone(obj) { // 如果是 值类型 或 null，则直接return if(typeof obj !== 'object' || obj === null) { return obj }
// 定义结果对象 let copy = {}
// 如果对象是数组，则定义结果数组 if(obj.constructor === Array) { copy = [] }
// 遍历对象的key for(let key in obj) { // 如果key是对象的自有属性 if(obj.hasOwnProperty(key)) { // 递归调用深拷贝方法 copy[key] = deepClone(obj[key]) } }
return copy}
复制代码
调用深拷贝方法，若属性为值类型，则直接返回；若属性为引用类型，则递归遍历。这就是我们在解这一类题时的核心的方法。
进阶版
// 递归拷贝 (类型判断)function deepClone(value,hash = new WeakMap){ // 弱引用，不用map，weakMap更合适一点 // null 和 undefiend 是不需要拷贝的 if(value == null){ return value;} if(value instanceof RegExp) { return new RegExp(value) } if(value instanceof Date) { return new Date(value) } // 函数是不需要拷贝 if(typeof value != 'object') return value; let obj = new value.constructor(); // [] {} // 说明是一个对象类型 if(hash.get(value)){ return hash.get(value) } hash.set(value,obj); for(let key in value){ // in 会遍历当前对象上的属性 和 __proto__指代的属性 // 补拷贝 对象的__proto__上的属性 if(value.hasOwnProperty(key)){ // 如果值还有可能是对象 就继续拷贝 obj[key] = deepClone(value[key],hash); } } return obj // 区分对象和数组 Object.prototype.toString.call}
复制代码
// test
var o = {};o.x = o;var o1 = deepClone(o); // 如果这个对象拷贝过了 就返回那个拷贝的结果就可以了console.log(o1);
复制代码
实现完整的深拷贝
1. 简易版及问题
JSON.parse(JSON.stringify());
复制代码
估计这个 api 能覆盖大多数的应用场景，没错，谈到深拷贝，我第一个想到的也是它。但是实际上，对于某些严格的场景来说，这个方法是有巨大的坑的。问题如下：
无法解决循环引用的问题。举个例子：
const a = {val:2};a.target = a;
复制代码
拷贝a会出现系统栈溢出，因为出现了无限递归的情况。
无法拷贝一些特殊的对象，诸如 RegExp, Date, Set, Map等
无法拷贝函数(划重点)。
因此这个 api 先 pass 掉，我们重新写一个深拷贝，简易版如下:
const deepClone = (target) => { if (typeof target === 'object' && target !== null) { const cloneTarget = Array.isArray(target) ? []: {}; for (let prop in target) { if (target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop]); } } return cloneTarget; } else { return target; }}
复制代码
现在，我们以刚刚发现的三个问题为导向，一步步来完善、优化我们的深拷贝代码。
2. 解决循环引用
现在问题如下:
let obj = {val : 100};obj.target = obj;
deepClone(obj);//报错: RangeError: Maximum call stack size exceeded
复制代码
这就是循环引用。我们怎么来解决这个问题呢？
创建一个 Map。记录下已经拷贝过的对象，如果说已经拷贝过，那直接返回它行了。
const isObject = (target) => (typeof target === 'object' || typeof target === 'function') && target !== null;
const deepClone = (target, map = new Map()) => { if(map.get(target)) return target;
if (isObject(target)) { map.set(target, true); const cloneTarget = Array.isArray(target) ? []: {}; for (let prop in target) { if (target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop],map); } } return cloneTarget; } else { return target; } }
复制代码
现在来试一试：
const a = {val:2};a.target = a;let newA = deepClone(a);console.log(newA)//{ val: 2, target: { val: 2, target: [Circular] } }
复制代码
好像是没有问题了, 拷贝也完成了。但还是有一个潜在的坑, 就是 map 上的 key 和 map 构成了强引用关系，这是相当危险的。我给你解释一下与之相对的弱引用的概念你就明白了
在计算机程序设计中，弱引用与强引用相对，
被弱引用的对象可以在任何时候被回收，而对于强引用来说，只要这个强引用还在，那么对象无法被回收。拿上面的例子说，map 和 a 一直是强引用的关系， 在程序结束之前，a 所占的内存空间一直不会被释放。
怎么解决这个问题？
很简单，让 map 的 key 和 map 构成弱引用即可。ES6 给我们提供了这样的数据结构，它的名字叫 WeakMap，它是一种特殊的 Map, 其中的键是弱引用的。其键必须是对象，而值可以是任意的
稍微改造一下即可:
const deepClone = (target, map = new WeakMap()) => { //...}
复制代码
3. 拷贝特殊对象
可继续遍历
对于特殊的对象，我们使用以下方式来鉴别:
Object.prototype.toString.call(obj);
复制代码
梳理一下对于可遍历对象会有什么结果：
["object Map"]["object Set"]["object Array"]["object Object"]["object Arguments"]
复制代码
以这些不同的字符串为依据，我们就可以成功地鉴别这些对象。
const getType = Object.prototype.toString.call(obj);
const canTraverse = { '[object Map]': true, '[object Set]': true, '[object Array]': true, '[object Object]': true, '[object Arguments]': true,};
const deepClone = (target, map = new Map()) => { if(!isObject(target)) return target; let type = getType(target); let cloneTarget; if(!canTraverse[type]) { // 处理不能遍历的对象 return; }else { // 这波操作相当关键，可以保证对象的原型不丢失！ let ctor = target.prototype; cloneTarget = new ctor(); }
if(map.get(target)) return target; map.put(target, true);
if(type === mapTag) { //处理Map target.forEach((item, key) => { cloneTarget.set(deepClone(key), deepClone(item)); }) }
if(type === setTag) { //处理Set target.forEach(item => { target.add(deepClone(item)); }) }
// 处理数组和对象 for (let prop in target) { if (target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop]); } } return cloneTarget;}
复制代码
不可遍历的对象
const boolTag = '[object Boolean]';const numberTag = '[object Number]';const stringTag = '[object String]';const dateTag = '[object Date]';const errorTag = '[object Error]';const regexpTag = '[object RegExp]';const funcTag = '[object Function]';
复制代码
对于不可遍历的对象，不同的对象有不同的处理。
const handleRegExp = (target) => { const { source, flags } = target; return new target.constructor(source, flags);}
const handleFunc = (target) => { // 待会的重点部分}
const handleNotTraverse = (target, tag) => { const Ctor = targe.constructor; switch(tag) { case boolTag: case numberTag: case stringTag: case errorTag: case dateTag: return new Ctor(target); case regexpTag: return handleRegExp(target); case funcTag: return handleFunc(target); default: return new Ctor(target); }}
复制代码
4. 拷贝函数
虽然函数也是对象，但是它过于特殊，我们单独把它拿出来拆解。
提到函数，在 JS 种有两种函数，一种是普通函数，另一种是箭头函数。每个普通函数都是
Function 的实例，而箭头函数不是任何类的实例，每次调用都是不一样的引用。那我们只需要
处理普通函数的情况，箭头函数直接返回它本身就好了。
那么如何来区分两者呢？
答案是: 利用原型。箭头函数是不存在原型的。
const handleFunc = (func) => { // 箭头函数直接返回自身 if(!func.prototype) return func; const bodyReg = /(?<={)(.|\n)+(?=})/m; const paramReg = /(?<=\().+(?=\)\s+{)/; const funcString = func.toString(); // 分别匹配 函数参数 和 函数体 const param = paramReg.exec(funcString); const body = bodyReg.exec(funcString); if(!body) return null; if (param) { const paramArr = param[0].split(','); return new Function(...paramArr, body[0]); } else { return new Function(body[0]); }}
复制代码
5. 完整代码展示
const getType = obj => Object.prototype.toString.call(obj);
const isObject = (target) => (typeof target === 'object' || typeof target === 'function') && target !== null;
const canTraverse = { '[object Map]': true, '[object Set]': true, '[object Array]': true, '[object Object]': true, '[object Arguments]': true,};const mapTag = '[object Map]';const setTag = '[object Set]';const boolTag = '[object Boolean]';const numberTag = '[object Number]';const stringTag = '[object String]';const symbolTag = '[object Symbol]';const dateTag = '[object Date]';const errorTag = '[object Error]';const regexpTag = '[object RegExp]';const funcTag = '[object Function]';
const handleRegExp = (target) => { const { source, flags } = target; return new target.constructor(source, flags);}
const handleFunc = (func) => { // 箭头函数直接返回自身 if(!func.prototype) return func; const bodyReg = /(?<={)(.|\n)+(?=})/m; const paramReg = /(?<=\().+(?=\)\s+{)/; const funcString = func.toString(); // 分别匹配 函数参数 和 函数体 const param = paramReg.exec(funcString); const body = bodyReg.exec(funcString); if(!body) return null; if (param) { const paramArr = param[0].split(','); return new Function(...paramArr, body[0]); } else { return new Function(body[0]); }}
const handleNotTraverse = (target, tag) => { const Ctor = target.constructor; switch(tag) { case boolTag: return new Object(Boolean.prototype.valueOf.call(target)); case numberTag: return new Object(Number.prototype.valueOf.call(target)); case stringTag: return new Object(String.prototype.valueOf.call(target)); case symbolTag: return new Object(Symbol.prototype.valueOf.call(target)); case errorTag: case dateTag: return new Ctor(target); case regexpTag: return handleRegExp(target); case funcTag: return handleFunc(target); default: return new Ctor(target); }}
const deepClone = (target, map = new WeakMap()) => { if(!isObject(target)) return target; let type = getType(target); let cloneTarget; if(!canTraverse[type]) { // 处理不能遍历的对象 return handleNotTraverse(target, type); }else { // 这波操作相当关键，可以保证对象的原型不丢失！ let ctor = target.constructor; cloneTarget = new ctor(); }
if(map.get(target)) return target; map.set(target, true);
if(type === mapTag) { //处理Map target.forEach((item, key) => { cloneTarget.set(deepClone(key, map), deepClone(item, map)); }) }
if(type === setTag) { //处理Set target.forEach(item => { cloneTarget.add(deepClone(item, map)); }) }
// 处理数组和对象 for (let prop in target) { if (target.hasOwnProperty(prop)) { cloneTarget[prop] = deepClone(target[prop], map); } } return cloneTarget;}
复制代码
实现 map 方法
回调函数的参数有哪些，返回值如何处理
不修改原来的数组
Array.prototype.myMap = function(callback, context){ // 转换类数组 var arr = Array.prototype.slice.call(this),//由于是ES5所以就不用...展开符了 mappedArr = [], i = 0;
for (; i < arr.length; i++ ){ // 把当前值、索引、当前数组返回去。调用的时候传到函数参数中 [1,2,3,4].map((curr,index,arr)) mappedArr.push(callback.call(context, arr[i], i, this)); } return mappedArr;}
复制代码
实现 Array.of 方法
Array.of()方法用于将一组值，转换为数组
Array.of(3, 11, 8) // [3,11,8]Array.of(3) // [3]Array.of(3).length // 1
复制代码
实现
function ArrayOf(){ return [].slice.call(arguments);}
复制代码
参考 前端进阶面试题详细解答
实现一下 hash 路由
基础的html代码：
<html> <style> html, body { margin: 0; height: 100%; } ul { list-style: none; margin: 0; padding: 0; display: flex; justify-content: center; } .box { width: 100%; height: 100%; background-color: red; } </style> <body> <ul> <li> <a href="#red">红色</a> </li> <li> <a href="#green">绿色</a> </li> <li> <a href="#purple">紫色</a> </li> </ul> </body></html>
复制代码
简单实现：
<script> const box = document.getElementsByClassName('box')[0]; const hash = location.hash window.onhashchange = function (e) { const color = hash.slice(1) box.style.background = color }</script>
复制代码
封装成一个 class:
<script> const box = document.getElementsByClassName('box')[0]; const hash = location.hash class HashRouter { constructor (hashStr, cb) { this.hashStr = hashStr this.cb = cb this.watchHash() this.watch = this.watchHash.bind(this) window.addEventListener('hashchange', this.watch) } watchHash () { let hash = window.location.hash.slice(1) this.hashStr = hash this.cb(hash) } } new HashRouter('red', (color) => { box.style.background = color })</script>
复制代码
实现 apply 方法
思路: 利用this的上下文特性。apply其实就是改一下参数的问题
Function.prototype.myApply = function(context = window, args) { // this-->func context--> obj args--> 传递过来的参数
// 在context上加一个唯一值不影响context上的属性 let key = Symbol('key') context[key] = this; // context为调用的上下文,this此处为函数，将这个函数作为context的方法 // let args = [...arguments].slice(1) //第一个参数为obj所以删除,伪数组转为数组
let result = context[key](...args); // 这里和call传参不一样
// 清除定义的this 不删除会导致context属性越来越多 delete context[key];
// 返回结果 return result;}
复制代码
// 使用function f(a,b){ console.log(a,b) console.log(this.name)}let obj={ name:'张三'}f.myApply(obj,[1,2]) //arguments[1]
复制代码
实现单例模式
核心要点: 用闭包和Proxy属性拦截
function proxy(func) { let instance; let handler = { constructor(target, args) { if(!instance) { instance = Reflect.constructor(fun, args); } return instance; } } return new Proxy(func, handler);}
复制代码
对象数组如何去重
根据每个对象的某一个具体属性来进行去重
const responseList = [ { id: 1, a: 1 }, { id: 2, a: 2 }, { id: 3, a: 3 }, { id: 1, a: 4 },];const result = responseList.reduce((acc, cur) => { const ids = acc.map(item => item.id); return ids.includes(cur.id) ? acc : [...acc, cur];}, []);console.log(result); // -> [ { id: 1, a: 1}, {id: 2, a: 2}, {id: 3, a: 3} ]
复制代码
数组去重方法汇总
首先:我知道多少种去重方式
1. 双层 for 循环
function distinct(arr) { for (let i=0, len=arr.length; i<len; i++) { for (let j=i+1; j<len; j++) { if (arr[i] == arr[j]) { arr.splice(j, 1); // splice 会改变数组长度，所以要将数组长度 len 和下标 j 减一 len--; j--; } } } return arr;}
复制代码
思想: 双重 for 循环是比较笨拙的方法，它实现的原理很简单：先定义一个包含原始数组第一个元素的数组，然后遍历原始数组，将原始数组中的每个元素与新数组中的每个元素进行比对，如果不重复则添加到新数组中，最后返回新数组；因为它的时间复杂度是O(n^2)，如果数组长度很大，效率会很低
2. Array.filter() 加 indexOf/includes
function distinct(a, b) { let arr = a.concat(b); return arr.filter((item, index)=> { //return arr.indexOf(item) === index return arr.includes(item) })}
复制代码
思想: 利用indexOf检测元素在数组中第一次出现的位置是否和元素现在的位置相等，如果不等则说明该元素是重复元素
3. ES6 中的 Set 去重
function distinct(array) { return Array.from(new Set(array));}
复制代码
思想: ES6 提供了新的数据结构 Set，Set 结构的一个特性就是成员值都是唯一的，没有重复的值。
4. reduce 实现对象数组去重复
var resources = [ { name: "张三", age: "18" }, { name: "张三", age: "19" }, { name: "张三", age: "20" }, { name: "李四", age: "19" }, { name: "王五", age: "20" }, { name: "赵六", age: "21" }]var temp = {};resources = resources.reduce((prev, curv) => { // 如果临时对象中有这个名字，什么都不做 if (temp[curv.name]) {
}else { // 如果临时对象没有就把这个名字加进去，同时把当前的这个对象加入到prev中 temp[curv.name] = true; prev.push(curv); } return prev}, []);console.log("结果", resources);
复制代码
这种方法是利用高阶函数 reduce 进行去重， 这里只需要注意initialValue得放一个空数组[]，不然没法push
实现 reduce 方法
初始值不传怎么处理
回调函数的参数有哪些，返回值如何处理。
Array.prototype.myReduce = function(fn, initialValue) { var arr = Array.prototype.slice.call(this); var res, startIndex;
res = initialValue ? initialValue : arr[0]; // 不传默认取数组第一项 startIndex = initialValue ? 0 : 1;
for(var i = startIndex; i < arr.length; i++) { // 把初始值、当前值、索引、当前数组返回去。调用的时候传到函数参数中 [1,2,3,4].reduce((initVal,curr,index,arr)) res = fn.call(null, res, arr[i], i, this); } return res;}
复制代码
二叉树深度遍历
// 二叉树深度遍历
class Node { constructor(element, parent) { this.parent = parent // 父节点 this.element = element // 当前存储内容 this.left = null // 左子树 this.right = null // 右子树 }}
class BST { constructor(compare) { this.root = null // 树根 this.size = 0 // 树中的节点个数
this.compare = compare || this.compare } compare(a,b) { return a - b } add(element) { if(this.root === null) { this.root = new Node(element, null) this.size++ return } // 获取根节点 用当前添加的进行判断 放左边还是放右边 let currentNode = this.root let compare let parent = null while (currentNode) { compare = this.compare(element, currentNode.element) parent = currentNode // 先将父亲保存起来 // currentNode要不停的变化 if(compare > 0) { currentNode = currentNode.right } else if(compare < 0) { currentNode = currentNode.left } else { currentNode.element = element // 相等时 先覆盖后续处理 } }
let newNode = new Node(element, parent) if(compare > 0) { parent.right = newNode } else if(compare < 0) { parent.left = newNode }
this.size++ } // 前序遍历 preorderTraversal(visitor) { const traversal = node=>{ if(node === null) return visitor.visit(node.element) traversal(node.left) traversal(node.right) } traversal(this.root) } // 中序遍历 inorderTraversal(visitor) { const traversal = node=>{ if(node === null) return traversal(node.left) visitor.visit(node.element) traversal(node.right) } traversal(this.root) } // 后序遍历 posterorderTraversal(visitor) { const traversal = node=>{ if(node === null) return traversal(node.left) traversal(node.right) visitor.visit(node.element) } traversal(this.root) } // 反转二叉树：无论先序、中序、后序、层级都可以反转 invertTree() { const traversal = node=>{ if(node === null) return let temp = node.left node.left = node.right node.right = temp traversal(node.left) traversal(node.right) } traversal(this.root) return this.root }}
复制代码
先序遍历
二叉树的遍历方式
// 测试var bst = new BST((a,b)=>a.age-b.age) // 模拟sort方法
bst.add({age: 10})bst.add({age: 8})bst.add({age:19})bst.add({age:6})bst.add({age: 15})bst.add({age: 22})bst.add({age: 20})
// 先序遍历// console.log(bst.preorderTraversal(),'先序遍历')// console.log(bst.inorderTraversal(),'中序遍历')// // console.log(bst.posterorderTraversal(),'后序遍历')
// 深度遍历：先序遍历、中序遍历、后续遍历// 广度遍历：层次遍历（同层级遍历）// 都可拿到树中的节点
// 使用访问者模式class Visitor { constructor() { this.visit = function (elem) { elem.age = elem.age*2 } }}
// bst.posterorderTraversal({// visit(elem) {// elem.age = elem.age*10// }// })
// 不能通过索引操作 拿到节点去操作// bst.posterorderTraversal(new Visitor())
console.log(bst.invertTree(),'反转二叉树')
复制代码
实现有并行限制的 Promise 调度器
题目描述:JS 实现一个带并发限制的异步调度器 Scheduler，保证同时运行的任务最多有两个
addTask(1000,"1"); addTask(500,"2"); addTask(300,"3"); addTask(400,"4"); 的输出顺序是：2 3 1 4
整个的完整执行流程：
一开始1、2两个任务开始执行500ms时，2任务执行完毕，输出2，任务3开始执行800ms时，3任务执行完毕，输出3，任务4开始执行1000ms时，1任务执行完毕，输出1，此时只剩下4任务在执行1200ms时，4任务执行完毕，输出4
复制代码
实现代码如下:
class Scheduler { constructor(limit) { this.queue = []; this.maxCount = limit; this.runCounts = 0; } add(time, order) { const promiseCreator = () => { return new Promise((resolve, reject) => { setTimeout(() => { console.log(order); resolve(); }, time); }); }; this.queue.push(promiseCreator); } taskStart() { for (let i = 0; i < this.maxCount; i++) { this.request(); } } request() { if (!this.queue || !this.queue.length || this.runCounts >= this.maxCount) { return; } this.runCounts++; this.queue .shift()() .then(() => { this.runCounts--; this.request(); }); }}const scheduler = new Scheduler(2);const addTask = (time, order) => { scheduler.add(time, order);};addTask(1000, "1");addTask(500, "2");addTask(300, "3");addTask(400, "4");scheduler.taskStart();
复制代码
树形结构转成列表（处理菜单）
[ { id: 1, text: '节点1', parentId: 0, children: [ { id:2, text: '节点1_1', parentId:1 } ] }]转成[ { id: 1, text: '节点1', parentId: 0 //这里用0表示为顶级节点 }, { id: 2, text: '节点1_1', parentId: 1 //通过这个字段来确定子父级 } ...]
复制代码
实现代码如下:
function treeToList(data) { let res = []; const dfs = (tree) => { tree.forEach((item) => { if (item.children) { dfs(item.children); delete item.children; } res.push(item); }); }; dfs(data); return res;}
复制代码
二叉树搜索
// 二叉搜索树
class Node { constructor(element, parent) { this.parent = parent // 父节点 this.element = element // 当前存储内容 this.left = null // 左子树 this.right = null // 右子树 }}
class BST { constructor(compare) { this.root = null // 树根 this.size = 0 // 树中的节点个数
this.compare = compare || this.compare } compare(a,b) { return a - b } add(element) { if(this.root === null) { this.root = new Node(element, null) this.size++ return } // 获取根节点 用当前添加的进行判断 放左边还是放右边 let currentNode = this.root let compare let parent = null while (currentNode) { compare = this.compare(element, currentNode.element) parent = currentNode // 先将父亲保存起来 // currentNode要不停的变化 if(compare > 0) { currentNode = currentNode.right } else if(compare < 0) { currentNode = currentNode.left } else { currentNode.element = element // 相等时 先覆盖后续处理 } }
let newNode = new Node(element, parent) if(compare > 0) { parent.right = newNode } else if(compare < 0) { parent.left = newNode }
this.size++ }}
复制代码
// 测试var bst = new BST((a,b)=>b.age-a.age) // 模拟sort方法
bst.add({age: 10})bst.add({age: 8})bst.add({age:19})bst.add({age:20})bst.add({age: 5})
console.log(bst)
复制代码
reduce 用法汇总
语法
array.reduce(function(total, currentValue, currentIndex, arr), initialValue);/* total: 必需。初始值, 或者计算结束后的返回值。 currentValue： 必需。当前元素。 currentIndex： 可选。当前元素的索引； arr： 可选。当前元素所属的数组对象。 initialValue: 可选。传递给函数的初始值，相当于total的初始值。*/
复制代码
reduceRight() 该方法用法与reduce()其实是相同的，只是遍历的顺序相反，它是从数组的最后一项开始，向前遍历到第一项
1. 数组求和
const arr = [12, 34, 23];const sum = arr.reduce((total, num) => total + num);
// 设定初始值求和const arr = [12, 34, 23];const sum = arr.reduce((total, num) => total + num, 10); // 以10为初始值求和
// 对象数组求和var result = [ { subject: 'math', score: 88 }, { subject: 'chinese', score: 95 }, { subject: 'english', score: 80 }];const sum = result.reduce((accumulator, cur) => accumulator + cur.score, 0); const sum = result.reduce((accumulator, cur) => accumulator + cur.score, -10); // 总分扣除10分
复制代码
2. 数组最大值
const a = [23,123,342,12];const max = a.reduce((pre,next)=>pre>cur?pre:cur,0); // 342
复制代码
3. 数组转对象
var streams = [{name: '技术', id: 1}, {name: '设计', id: 2}];var obj = streams.reduce((accumulator, cur) => {accumulator[cur.id] = cur; return accumulator;}, {});
复制代码
4. 扁平一个二维数组
var arr = [[1, 2, 8], [3, 4, 9], [5, 6, 10]];var res = arr.reduce((x, y) => x.concat(y), []);
复制代码
5. 数组去重
实现的基本原理如下：
① 初始化一个空数组② 将需要去重处理的数组中的第1项在初始化数组中查找，如果找不到（空数组中肯定找不到），就将该项添加到初始化数组中③ 将需要去重处理的数组中的第2项在初始化数组中查找，如果找不到，就将该项继续添加到初始化数组中④ ……⑤ 将需要去重处理的数组中的第n项在初始化数组中查找，如果找不到，就将该项继续添加到初始化数组中⑥ 将这个初始化数组返回
复制代码
var newArr = arr.reduce(function (prev, cur) { prev.indexOf(cur) === -1 && prev.push(cur); return prev;},[]);
复制代码
6. 对象数组去重
const dedup = (data, getKey = () => { }) => { const dateMap = data.reduce((pre, cur) => { const key = getKey(cur) if (!pre[key]) { pre[key] = cur } return pre }, {}) return Object.values(dateMap)}
复制代码
7. 求字符串中字母出现的次数
const str = 'sfhjasfjgfasjuwqrqadqeiqsajsdaiwqdaklldflas-cmxzmnha';
const res = str.split('').reduce((pre,next)=>{ pre[next] ? pre[next]++ : pre[next] = 1 return pre },{})
复制代码
// 结果-: 1a: 8c: 1d: 4e: 1f: 4g: 1h: 2i: 2j: 4k: 1l: 3m: 2n: 1q: 5r: 1s: 6u: 1w: 2x: 1z: 1
复制代码
8. compose 函数
redux compose 源码实现
function compose(...funs) { if (funs.length === 0) { return arg => arg; } if (funs.length === 1) { return funs[0]; } return funs.reduce((a, b) => (...arg) => a(b(...arg)))}
复制代码
类数组转化为数组的方法
const arrayLike=document.querySelectorAll('div')
// 1.扩展运算符[...arrayLike]// 2.Array.fromArray.from(arrayLike)// 3.Array.prototype.sliceArray.prototype.slice.call(arrayLike)// 4.Array.applyArray.apply(null, arrayLike)// 5.Array.prototype.concatArray.prototype.concat.apply([], arrayLike)
复制代码
对象数组列表转成树形结构（处理菜单）
[ { id: 1, text: '节点1', parentId: 0 //这里用0表示为顶级节点 }, { id: 2, text: '节点1_1', parentId: 1 //通过这个字段来确定子父级 } ...]
转成[ { id: 1, text: '节点1', parentId: 0, children: [ { id:2, text: '节点1_1', parentId:1 } ] }]
复制代码
实现代码如下:
function listToTree(data) { let temp = {}; let treeData = []; for (let i = 0; i < data.length; i++) { temp[data[i].id] = data[i]; } for (let i in temp) { if (+temp[i].parentId != 0) { if (!temp[temp[i].parentId].children) { temp[temp[i].parentId].children = []; } temp[temp[i].parentId].children.push(temp[i]); } else { treeData.push(temp[i]); } } return treeData;}
复制代码
实现 findIndex 方法
var users = [ {id: 1, name: '张三'}, {id: 2, name: '张三'}, {id: 3, name: '张三'}, {id: 4, name: '张三'}]
Array.prototype.myFindIndex = function (callback) { // var callback = function (item, index) { return item.id === 4 } for (var i = 0; i < this.length; i++) { if (callback(this[i], i)) { // 这里返回 return i } }}
var ret = users.myFind(function (item, index) { return item.id === 2})
console.log(ret)
复制代码
评论