高频

一、手写LRU缓存

leetcode 446

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入
[“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

a. LRU 缓存策略举例：
i. 假设缓存大小为 4，依次打开了 gitlab、力扣、微信、QQ，缓存链表为 QQ -> 微信 -> 力扣 -> gitlab；
ii. 若此时切换到了「微信」，则缓存链表更新为 微信 -> QQ -> 力扣 -> gitlab；
iii. 若此时打开了腾讯会议，因为缓存已经满 4 个 ，所以要进行缓存淘汰机制，删除链表的最后一位 「gitlab」，则缓存链表更新为 腾讯会议 -> 微信 -> QQ -> 力扣；
b. 本题用的是 map 迭代器，map 实现了 iterator，next 模拟链表的下一个指针，为了方便操作，这里将 map 第一个元素作为链表的最后一个元素；

let cache = new Map();
cache.set('a', 1);
cache.set('b', 2);
cache.set('c', 3);
cache.keys(); // MapIterator {'a', 'b', 'c'}
cache.keys().next().value; // a

a. 时间复杂度：对于 put 和 get 都是 O(1);

b. 空间复杂度：O(capacity);

class LRUCache {

    capacity:number;
    cache:Map<number,number> = new Map();
    //缓存的容量
    constructor(capacity: number) {
        this.capacity = capacity
    }

    get(key: number): number {
        if(this.cache.has(key)){

            let value = this.cache.get(key);
            //重新set，相当于更新到cache最后----可以保证删除时，最久未使用的在第一位
            //先删除
            this.cache.delete(key);
            this.cache.set(key,value);
            return value;
        }
        return -1;
    }

    put(key: number, value: number): void {

        if(this.cache.has(key)){
            this.cache.delete(key);
        }

        this.cache.set(key,value);

        if(this.cache.size>this.capacity){
            //利用next指针，反复进行put时，可以删除正确的缓存
            this.cache.delete(this.cache.keys().next().value);
        }

    }
}

二、手写深拷贝

前置知识

前面文章我们讲到，JavaScript中存在两大数据类型：

• 基本类型
• 引用类型

基本类型数据保存在在栈内存中

引用类型数据保存在堆内存中，引用数据类型的变量是一个指向堆内存中实际对象的引用，存在栈中

深拷贝

深拷贝开辟一个新的栈，两个对象属完成相同，但是对应两个不同的地址，修改一个对象的属性，不会改变另一个对象的属性

常见的深拷贝方式有：

• _.cloneDeep()
• jQuery.extend()
• JSON.stringify()
• 手写循环递归

console.log(obj1.b.f === obj2.b.f); // false

JSON.stringify()

const obj2=JSON.parse(JSON.stringify(obj1));

但是这种方式存在弊端，会忽略undefined、symbol和函数

const obj = {
    name: 'A',
    name1: undefined,
    name3: function() {},
    name4:  Symbol('A')
}
const obj2 = JSON.parse(JSON.stringify(obj));
console.log(obj2); // {name: "A"}

function deepCopy(object) {
  if (!object || typeof object !== "object") return object;

  let newObject = Array.isArray(object) ? [] : {};

  for (let key in object) {
    if (object.hasOwnProperty(key)) {
      newObject[key] = deepCopy(object[key]);
    }
  }

  return newObject;
}

循环递归——考点

function deepClone(obj, hash = new WeakMap()) {
  if (!object || typeof object !== "object") return object;

  // 是对象的话就要进行深拷贝,遇到循环引用，将引用存储起来，如果存在就不再拷贝
  if (hash.get(obj)) return hash.get(obj);
  let cloneObj = Array.isArray(object) ? [] : {};
  hash.set(obj, cloneObj);

  for (let key in obj) {
    if (obj.hasOwnProperty(key)) {
      // 实现一个递归拷贝
      cloneObj[key] = deepClone(obj[key], hash);
    }
  }
  return cloneObj;
}

下面首先借助两张图，可以更加清晰看到浅拷贝与深拷贝的区别

从上图发现，浅拷贝和深拷贝都创建出一个新的对象，但在复制对象属性的时候，行为就不一样

浅拷贝只复制属性指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存，修改对象属性会影响原对象

// 浅拷贝
const obj1 = {
    name : 'init',
    arr : [1,[2,3],4],
};
const obj3=shallowClone(obj1) // 一个浅拷贝方法
obj3.name = "update";
obj3.arr[1] = [5,6,7] ; // 新旧对象还是共享同一块内存

console.log('obj1',obj1) // obj1 { name: 'init',  arr: [ 1, [ 5, 6, 7 ], 4 ] }
console.log('obj3',obj3) // obj3 { name: 'update', arr: [ 1, [ 5, 6, 7 ], 4 ] }

但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象

// 深拷贝
const obj1 = {
    name : 'init',
    arr : [1,[2,3],4],
};
const obj4=deepClone(obj1) // 一个深拷贝方法
obj4.name = "update";
obj4.arr[1] = [5,6,7] ; // 新对象跟原对象不共享内存

console.log('obj1',obj1) // obj1 { name: 'init', arr: [ 1, [ 2, 3 ], 4 ] }
console.log('obj4',obj4) // obj4 { name: 'update', arr: [ 1, [ 5, 6, 7 ], 4 ] }

三、手写Array.filter/map/fill/reduce/forEach

/*
纯函数API : 
concat
filter
map
reduce
slice
非纯函数API
splice
shift(unshift同理)
reverse
*/

forEach返回undefined不属于纯函数，同样的由every、some

Array.prototype._forEach = function(fn,_this){
    if(typeof fn!='function') throw '需要传入一个函数';
    if(!this instanceof Array) throw '需要传入一个数组';
    let length = this.length;
    for(let i=0;i<length;i++)
    {
        fn.call(_this,this[i],i,this)
    }
}

纯函数API

concat() 方法用于合并两个或多个数组。此方法不会更改现有数组，而是返回一个新数组。

concat方法不会改变this或任何作为参数提供的数组，而是返回一个浅拷贝.也就是说,如果数组里有引用对象的话,拷贝过来的是引用地址

//实现一个简易concat
Array.prototype._concat = function(...args){
    let context = this , result = [];
    //如果数组为空，直接返回当前数组对象
    if(!args.length){
      return context
    }
    //如果没有参数,直接返回this
    args.forEach( item => {
      if(Object.prototype.toString.call(item) !== '[object Array]'){
        result.push(item)
        //判断参数里面有没有数组
      }else{
        item.forEach( it => result.push(it))
      }
    })
    return result
}
console.log( []._concat(1,2,3,3,45))
console.log( []._concat(1,2,3,{name:'dd'},45))
console.log( []._concat([1,[2]],3,3,45))
console.log( []._concat() )
// [ 1, 2, 3, 3, 45 ]
// [ 1, 2, 3, { name: 'dd' }, 45 ]
// [ 1, [ 2 ], 3, 3, 45 ]
// []

filter() 方法创建一个新数组, 其包含通过所提供函数实现的测试的所有元素。

需要注意的点

• filter方法不会改变原数组，它返回过滤后的新数组。
• 这个过程是一次性的,后面数组改变不会影响filter的值

//实现一个简易filter
Array.prototype._filter = function(cb,thisArg){
    let context = this
    let cbThis = thisArg ? thisArg : null
    let result = []
    //this默认指向this,提供了thisArg的情况下指向thisArgs
    context.forEach( (item,index,arr) => {
      if(cb.call(cbThis,item,index,arr)){
        result.push(item)
      }
    })
    return result
}
console.log( [1,2,3,43]._filter( item => item&1 == 1 ) )
console.log( []._filter(item => item&1 == 1 , [1,2,3,43]) )
//[ 1, 3, 43 ]
//[]

map() 方法创建一个新数组，其结果是该数组中的每个元素是调用一次提供的函数后的返回值。

需要注意的点

• map方法不会改变原数组，它返回新数组。
• callback 函数会被自动传入三个参数：数组元素，元素索引，原数组本身。
• map函数的第二个参数是可选项,作为callback的this指向

//实现一个简易map
Array.prototype._map = function(cb,thisArg){
    let context = this
    let cbThis = thisArg ? thisArg : null
    let result = []
    //this默认指向this,提供了thisArg的情况下指向thisArgs
    context.forEach( (item,index,arr) => {
       result.push( cb.call(cbThis,item,index,arr) )
      }) 
      return result
    }
console.log( [1,2,3]._map(Math.sqrt) )
console.log( [1,2,3]._map((index,item)=>{ return index * 2 + item}) )
// [ 1, 1.4142135623730951, 1.7320508075688772 ]
// [ 2, 5, 8 ]

reduce() 方法对数组中的每个元素执行一个由您提供的reducer函数(升序执行)，将其结果汇总为单个返回值。

需要注意的点

• reduce方法不会改变原数组，它返回一个值。
• 提供初始值initialValue会更加安全(建议)

//实现一个简易reduce
Array.prototype._reduce = function(reducer,initialValue){
    let context = this , startIndex = 1
    debugger
    //this默认指向this,提供了thisArg的情况下指向thisArgs
    if(initialValue !== undefined){
        startIndex = 0
    }else{
        initialValue = context[0]
    }
    for(let i = startIndex ; i < context.length ; i ++){
        initialValue = reducer(initialValue,context[i],i,context)
    }
      return initialValue
    }
console.log([1,2,3,34]._reduce((a,b) => a+b , 12))
console.log([1,2,3,34]._reduce((a,b) => a.concat(b) , []))
// 52
// [ 1, 2, 3, 34 ]

slice() 方法返回一个新的数组对象，这一对象是一个由 begin 和 end 决定的原数组的浅拷贝（包括 begin，不包括end）。原始数组不会被改变。

需要注意的点

• slice方法是对数组项的浅拷贝
• slice方法不会对原始数组进行修改

//实现一个简易slice
Array.prototype._slice = function(...args){
    let len = this.length , result = []
    let startIndex = args[0] === undefined ? 0 : args[0]
    let endIndex = args[1] === undefined ? len : args[1] >= len?len:args[1]
    for(let i = startIndex ; i < endIndex ; i ++ ){
        result.push(this[i])
    }
    return result
}
console.log( [1,2,3,34,3,3,3,33,3]._slice() )
//[1, 2,  3, 34, 3,3, 3, 33,  3]

非纯函数API

splice()方法通过删除或替换现有元素或者原地添加新的元素来修改数组,并以数组形式返回被修改的内容。此方法会改变原数组。

需要注意的点

• 指定修改的开始位置（从0计数）。如果超出了数组的长度，则从数组末尾开始添加内容；如果是负值，则表示从数组末位开始的第几位（从-1计数，这意味着-n是倒数第n个元素并且等价于array.length-n）；如果负数的绝对值大于数组的长度，则表示开始位置为第0位。
• 如果 deleteCount 大于 start 之后的元素的总数，则从 start 后面的元素都将被删除（含第 start 位）。 如果 deleteCount 被省略了，或者它的值大于等于array.length – start(也就是说，如果它大于或者等于start之后的所有元素的数量)，那么start之后数组的所有元素都会被删除。 如果 deleteCount 是 0 或者负数，则不移除元素。这种情况下，至少应添加一个新元素

//实现一个简易splice
Array.prototype._splice = function(startIndex,count,...items){
    debugger
    let context = this , len = context.length;
    let temp = this.slice()
    startIndex = startIndex < 0 ? Math.abs(startIndex>=len)?0:len + startIndex : startIndex
    //这里是判断startIndex负值相关情况
    //这里是判断count值得情况
    count = count <=0 ? 0 : count//count可以是负值
    if( count >= len - startIndex ){
        for(let i = 0 ; i < len - startIndex ; i ++){
            context.pop()
        }
        items.forEach( item => {
            context.push(item)
        })
    }else{//正常情况下得
        context.length = len - count + items.length//数组原地操作
        for(let j = context.length - 1 ; j >= startIndex + count ; j--){
            context[j] = context[ j + count - items.length ]
        }
        for(let i = 0 ; i < items.length ; i ++){
            context[startIndex + i] = items[i]
        }
    }
    console.log(this)
    return count === undefined ? temp.slice(startIndex) : temp.slice(startIndex,startIndex + count)
}
console.log( [1,2,3,34]._splice(1,2,3,4,45) )
// [ 1, 3, 4, 45, 34 ]
// [ 2, 3 ]

拓展:手写push、pop、shift、unshift——均为非纯函数

push

向数组末尾添加一个或多个元素，并返回数组新的长度

//通过数组的arguments属性

function push(){
    for(let i=0;i<arguments.length;i++){
        this[this.length] = arguments[i];
    }
    return this.length
}
Array.prototype.push = push;

unshift

向数组开头添加一个或多个元素，并且返回数组新的长度

function unshift(){
    //创建一个新数组接收添加的元素
    let newAry = [];
    for(let i=0;i<arguments.length;i++){
        newAry[i] = arguments[i];
    }
    let len = newAry.length;
    for(let i=0;i<this.length;i++){
        newAry[i+len] = this[i];
    }
    for(let i=0;i<newAry.length;i++){
        this[i] = newAry[i];
    }
    return this.length;
}
Array.prototype.unshift = unshift;

pop

删除数组最后一项，并返回该删除项目

function pop(){
    let returnVal = this[this.length-1];
    this.length--;
    return returnVal
}
Array.prototype.pop = pop;

shift

删除数组第一项，并且返回该删除项目

function shift(){
    let newAry = [];
    let reVal = this[0];
    for(let i=0;i<this.length-1;i++){
        newAry[i] = this[i+1];
    }
    for(let i=0;i<newAry.length;i++){
        this[i] = newAry[i]
    }
    this.length--;
    return reVal;
}
Array.prototype.shift = shift;

四、手写new操作符

前置知识

从上面介绍中，我们可以看到new关键字主要做了以下的工作：

• 创建一个新的对象obj
• 将对象与构建函数通过原型链连接起来
• 将构建函数中的this绑定到新建的对象obj上
• 根据构建函数返回类型作判断，如果是原始值则被忽略，如果是返回对象，需要正常处理

举个例子：

function Person(name, age){
    this.name = name;
    this.age = age;
}
const person1 = new Person('Tom', 20)
console.log(person1)  // Person {name: "Tom", age: 20}
t.sayName() // 'Tom'

流程图如下：

手写

现在我们已经清楚地掌握了new的执行过程

那么我们就动手来实现一下new

function mynew(Func, ...args) {
    // 1.创建一个新对象
    const obj = {}
    // 2.新对象原型指向构造函数原型对象
    obj.__proto__ = Func.prototype
    // 3.将构建函数的this指向新对象
    let result = Func.apply(obj, args)
    // 4.根据返回值判断
    return result instanceof Object ? result : obj
}

测试一下

function mynew(func, ...args) {
    const obj = {}
    obj.__proto__ = func.prototype
    let result = func.apply(obj, args)
    return result instanceof Object ? result : obj
}
function Person(name, age) {
    this.name = name;
    this.age = age;
}
Person.prototype.say = function () {
    console.log(this.name)
}

let p = mynew(Person, "huihui", 123)
console.log(p) // Person {name: "huihui", age: 123}
p.say() // huihui

五、手写bind

从上面可以看到，apply、call、bind三者的区别在于：

• 三者都可以改变函数的this对象指向
• 三者第一个参数都是this要指向的对象，如果如果没有这个参数或参数为undefined或null，则默认指向全局window
• 三者都可以传参，但是apply是数组，而call是参数列表，且apply和call是一次性传入参数，而bind可以分为多次传入
• bind是返回绑定this之后的函数，apply、call 则是立即执行

实现bind的步骤，我们可以分解成为三部分：

• 修改this指向
• 动态传递参数

// 方式一：只在bind中传递函数参数
fn.bind(obj,1,2)()

// 方式二：在bind中传递函数参数，也在返回函数中传递参数
fn.bind(obj,1)(2)

• 兼容new关键字

整体实现代码如下：

Function.prototype.myBind = function (context) {
    // 判断调用对象是否为函数
    if (typeof this !== "function") {
        throw new TypeError("Error");
    }

    // 获取参数
    const args = [...arguments].slice(1),
          fn = this;

    return function Fn() {

        // 根据调用方式，传入不同绑定值
        return fn.apply(this instanceof Fn ? new fn(...arguments) : context, args.concat(...arguments)); 
    }
}

六、手写vue v-if/v-show

v-show原理

不管初始条件是什么，元素总是会被渲染

我们看一下在vue中是如何实现的

代码很好理解，有transition就执行transition，没有就直接设置display属性

// https://github.com/vuejs/vue-next/blob/3cd30c5245da0733f9eb6f29d220f39c46518162/packages/runtime-dom/src/directives/vShow.ts
export const vShow: ObjectDirective<VShowElement> = {
  beforeMount(el, { value }, { transition }) {
    el._vod = el.style.display === 'none' ? '' : el.style.display
    if (transition && value) {
      transition.beforeEnter(el)
    } else {
      setDisplay(el, value)
    }
  },
  mounted(el, { value }, { transition }) {
    if (transition && value) {
      transition.enter(el)
    }
  },
  updated(el, { value, oldValue }, { transition }) {
    // ...
  },
  beforeUnmount(el, { value }) {
    setDisplay(el, value)
  }
}

v-if原理

v-if在实现上比v-show要复杂的多，因为还有else else-if 等条件需要处理，这里我们也只摘抄源码中处理 v-if 的一小部分

返回一个node节点，render函数通过表达式的值来决定是否生成DOM

// https://github.com/vuejs/vue-next/blob/cdc9f336fd/packages/compiler-core/src/transforms/vIf.ts
export const transformIf = createStructuralDirectiveTransform(
  /^(if|else|else-if)$/,
  (node, dir, context) => {
    return processIf(node, dir, context, (ifNode, branch, isRoot) => {
      // ...
      return () => {
        if (isRoot) {
          ifNode.codegenNode = createCodegenNodeForBranch(
            branch,
            key,
            context
          ) as IfConditionalExpression
        } else {
          // attach this branch's codegen node to the v-if root.
          const parentCondition = getParentCondition(ifNode.codegenNode!)
          parentCondition.alternate = createCodegenNodeForBranch(
            branch,
            key + ifNode.branches.length - 1,
            context
          )
        }
      }
    })
  }
)

七、防抖与节流

//防抖函数
function debounce(func, delay) {

  // 这里使用了闭包，所以 timer 不会轻易被销毁
  let timer = null

  // 生成一个新的函数并返回
  return function (...args) {
    // 清空定时器
    if (timer) {
      clearTimeout(timer)
    }
    // 重新启动定时器
    timer = setTimeout(() => {
      func.call(this, ...args)
    }, delay)
  }
    
}


//节流函数
function throttle(func, delay) {
    
  let timer = null
  // 在 delay 时间内，最多执行一次 func
  return function (...args) {
    if (!timer) {
      timer = setTimeout(() => {
        func.call(this, ...args)
        // 完成一次计时，清空，待下一次触发
        timer = null
      }, delay)
    }
  }
    
}

八、手写 instanceof

// 原理：验证当前类的原型prototype是否会出现在实例的原型链proto上，只要在它的原型链上，则结果都为true
function myinstanceOf_(obj, class_name) {
      // let proto = obj.__proto__;
    let proto = Object.getPrototypeOf(obj)
    let prototype = class_name.prototype
    while (true) {
        if (proto == null) return false
        if (proto == prototype) return true
          // proto = proto.__proto__;
        proto = Object.getPrototypeOf(proto)
    }
}

九、手写 call、apply、bind 函数

// 给函数的原型添加 _call 方法，使得所有函数都能调用 _call
// thisArg 就是要绑定的那个this；...args 扩展操作符传参，适合不定长参数，args是一个数组
Function.prototype._call = function(thisArg,...args){
    // 1.获取需要执行的函数
    let func = this

    // 2.将 thisArg 转成对象类型（防止它传入的是非对象类型，例如123数字）
    thisArg = (thisArg !== null && thisArg !== undefined) ? Object(thisArg) : window

    // 3.使用 thisArg 调用函数，绑定 this
    // 评论区大佬提出的改进方法，用 Symbol 创建一个独一无二的属性，避免属性覆盖或冲突的情况
    let fn = Symbol()
    thisArg[fn] = this
    // thisArg.fn = fn
    let result = thisArg[fn](...args)
    delete thisArg[fn]

    // 4.返回结果
    return result
}


Function.prototype._apply = function(thisArg,argArray){
    // 1.获取需要执行的函数
    let fn = this

    // 2.将 thisArg 转成对象类型（防止它传入的是非对象类型，例如123数字）
    thisArg = (thisArg !== null && thisArg !== undefined) ? Object(thisArg) : window
    // 判断一些边界情况
    argArray = argArray || []

    // 3.使用 thisArg 调用函数，绑定 this
    thisArg.fn = fn
    // 将传递过来的数组（可迭代对象）拆分，传给函数
    let result = thisArg.fn(...argArray)
    delete thisArg.fn

    // 4.返回结果
    return result
}


Function.prototype._call = function(thisArg,...args){
    let fn = this
    thisArg = (thisArg !== null && thisArg !== undefined) ? Object(thisArg) : window

    thisArg.fn = fn
    let result = thisArg.fn(...args)
    delete thisArg.fn

    return result
}

// 利用 call 模拟 bind
Function.prototype._bind = function(thisArg,...args){
    let fn = this // 需要调用的那个函数的引用
    // bind 需要返回一个函数
    return function(){
        return fn._call(thisArg, ...args)
    }
}

十、手写AJAX请求

function ajax(url) {
    // 创建一个 XHR 对象
    return new Promise((resolve,reject) => {
        const xhr = new XMLHttpRequest()
        // 指定请求类型，请求URL，和是否异步
        xhr.open('GET', url, true)
        xhr.onreadystatechange = funtion() {
          // 表明数据已就绪
            if(xhr.readyState === 4) {
                if(xhr.status === 200){
                    // 回调
                    resolve(JSON.stringify(xhr.responseText))
                }
                else{
                    reject('error')
                }
            }
        }
        // 发送定义好的请求
        xhr.send(null)
    })
}

十一、手写数组去重

// 1.Set + 数组复制
fuction unique1(array){
    // Array.from()，对一个可迭代对象进行浅拷贝
    return Array.from(new Set(array))
}

// 2.Set + 扩展运算符浅拷贝
function unique2(array){
    // ... 扩展运算符
    return [...new Set(array)]
}



// 3.filter，判断是不是首次出现，如果不是就过滤掉
function unique3(array){
    return array.filter((item,index) => {
        return array.indexOf(item) === index
    })
}

// 4.创建一个新数组，如果之前没加入就加入
function unique4(array){
    let res = []
    array.forEach(item => {
        if(res.indexOf(item) === -1){
            res.push(item)
        }
    })
    return res
}


进阶：如果数组内有数组和对象，应该怎么去重（此时对象的地址不同，用Set去不了重）

方法：

十二、手写数组扁平

// 方法1-3：递归
function flat1(array){
    // reduce(): 对数组的每一项执行归并函数，这个归并函数的返回值会作为下一次调用时的参数，即 preValue
    // concat(): 合并两个数组，并返回一个新数组
    return array.reduce((preValue,curItem) => {
        return preValue.concat(Array.isArray(curItem) ? flat1(curItem) : curItem)
    },[])
}

function flat2(array){
    let res = []
    array.forEach(item => {
        if(Array.isArray(item)){
            // res.push(...flat2(item))
        // 如果遇到一个数组，递归
            res = res.concat(flat2(item))
        }
        else{
            res.push(item)
        }
    })
    return res
}

function flat3(array){
    // some(): 对数组的每一项都运行传入的函数，如果有一项返回 TRUE，则这个方法返回 TRUE
    while(array.some(item => Array.isArray(item))){
    // ES6 增加了扩展运算符，用于取出参数对象的所有可遍历属性，拷贝到当前对象之中：
        array = [].concat(...array)
        console.log(...array)
    }
    return array
}

// 方法4、5：先转成字符串，再变回数组
function flat4(array){
    //[1,[2,3]].toString()  =>  1,2,3
    return array.toString().split(',').map(item => parseInt(item))
}

function flat5(array){
    return array.join(',').split(',').map(item => Number(item))
}

另附：手写对象扁平化

十三、手写数组乱序

// 方法1： sort + Math.random()
function shuffle1(arr){
    return arr.sort(() => Math.random() - 0.5);// 
}

// 方法2：时间复杂度 O(n^2)
// 随机拿出一个数（并在原数组中删除），放到新数组中
function randomSortArray(arr) {
    let backArr = [];
    while (arr.length) {
        let index = parseInt(Math.random() * arr.length);
        backArr.push(arr[index]);
        arr.splice(index, 1);
    }
    return backArr;
}

// 方法3：时间复杂度 O(n)
// 随机选一个放在最后，交换
function randomSortArray2(arr) {
    let lenNum = arr.length - 1;
    for (let i = 0; i < lenNum; i++) {
        let index = parseInt(Math.random() * (lenNum + 1 - i));
        [a[index],a[lenNum - i]] = [a[lenNum - i],a[index]]
    }
    return arr;
}

十四、手写 Promise.all()、Promise.race()、Promise.on() 等其他promise方法

function myAll(promises){
    // 问题关键：什么时候要执行resolve，什么时候要执行 reject
    return new Promise((resolve,reject) => {
        results = []
        // 迭代数组中的 Promise，将每个 promise 的结果保存到一个数组里
        let counter = 0
        for (let i = 0; i < promises.length; i++) {
            // 如果不是 Promise 类型要先包装一下
            // 调用 then 得到结果
            Promise.resolve(promises[i]).then(res => {
                // 这里不能用 push()，因为需要保证结果的顺序。感谢评论区大佬的批评指正
                results[i] = res
                counter++
                // 如果全部成功，状态变为 fulfilled
                if(counter === promises.length){
                    resolve(results)
                }
                },err => { // 如果出现了 rejected 状态，则调用 reject() 返回结果
                reject(err)
            })
        }
    }
)
}

// test
let p1 = new Promise(function (resolve, reject) {
    setTimeout(function () {
        resolve(1)
    }, 1000)
})
let p2 = new Promise(function (resolve, reject) {
    setTimeout(function () {
        resolve(2)
    }, 2000)
})
let p3 = new Promise(function (resolve, reject) {
    setTimeout(function () {
        resolve(3)
    }, 3000)
})
myAll([p3, p1, p2]).then(res => {
    console.log(res) // [3, 1, 2]
})

// 哪个 promise 状态先确定，就返回它的结果
function myRace(promises) {
    return new Promise((resolve, reject) => {
        promises.forEach(promise => {
            Promise.resolve(promise).then(res => {
                resolve(res)
            }, err => {
                reject(err)
            })
        })
    })
}

//
function myOn(promises){

}

//
function myAllsetter(promises){

}

十五、手撕快排

PS: 常见的排序算法，像冒泡，选择，插入排序这些最好也背一下，堆排序归并排序能写则写。万一考到了呢，要是写不出就直接回去等通知了

const _quickSort = array => {
    // 补全代码
    quickSort(array, 0, array.length - 1)
    // 别忘了返回数组
    return array
}

const quickSort = (array, start, end) => {
    // 注意递归边界条件
    if(end - start < 1)    return
    // 取第一个数作为基准
    const base = array[start]
    let left = start
    let right = end
    while(left < right){
        // 从右往左找小于基准元素的数，并赋值给右指针 array[right]
        while(left < right &&  array[right] >= base)    right--
        array[left] = array[right]
        // 从左往右找大于基准元素的数，并赋值给左指针 array[left]
        while(left < right && array[left] <= base)    left++
        array[right] = array[left]
    }
    // 双指针重合处，将基准元素填到这个位置。基准元素已经事先保存下来了，因此不用担心上面的赋值操作会覆盖掉基准元素的值
    // array[left] 位置已经确定，左边的都比它小，右边的都比它大
    array[left] = base
    quickSort(array, start, left - 1)
    quickSort(array, left + 1, end)
    return array
}

十六、手写 JSONP

// 动态的加载js文件
function addScript(src) {
  const script = document.createElement('script');
  script.src = src;
  script.type = "text/javascript";
  document.body.appendChild(script);
}
addScript("http://xxx.xxx.com/xxx.js?callback=handleRes");
// 设置一个全局的callback函数来接收回调结果
function handleRes(res) {
  console.log(res);
}

// 接口返回的数据格式，加载完js脚本后会自动执行回调函数
handleRes({a: 1, b: 2});

十七、手写寄生组合继承

function Parent(name) {
  this.name = name;
  this.say = () => {
    console.log(111);
  };
}
Parent.prototype.play = () => {
  console.log(222);
};
function Children(name,age) {
  Parent.call(this,name);
  this.age = age
}
Children.prototype = Object.create(Parent.prototype);
Children.prototype.constructor = Children;

十八、手写二分查找

//  迭代版
function search(nums, target) {
  // write code here
    if(nums.length === 0)    return -1
    let left = 0,right = nums.length - 1
        // 注意这里的边界，有等号
    while(left <= right){
        let mid = Math.floor((left + right) / 2)
        if(nums[mid] < target)    left = mid + 1
        else if(nums[mid] > target)    right = mid - 1
        else    return mid
    }
    return -1
}
// 递归版
function binary_search(arr, low, high, key) {
    if (low > high) {
        return -1;
    }
    var mid = parseInt((high + low) / 2);
    if (arr[mid] == key) {
        return mid;
    } else if (arr[mid] > key) {
        high = mid - 1;
        return binary_search(arr, low, high, key);
    } else if (arr[mid] < key) {
        low = mid + 1;
        return binary_search(arr, low, high, key);
    }
};

十九、手写函数柯里化

function sum(x,y,z) {
    return x + y + z
}

function hyCurrying(fn) {
    // 判断当前已经接收的参数的个数，和函数本身需要接收的参数是否一致
    function curried(...args) {
        // 1.当已经传入的参数 大于等于 需要的参数时，就执行函数
        if(args.length >= fn.length){
            // 如果调用函数时指定了this，要将其绑定上去
            return fn.apply(this, args)
        }
        else{
            // 没有达到个数时，需要返回一个新的函数，继续来接收参数
            return function(...args2) {
                //return curried.apply(this, [...args, ...args2])
                // 接收到参数后，需要递归调用 curried 来检查函数的个数是否达到
                return curried.apply(this, args.concat(args2))
            }
        }
    }
    return curried
}

var curryAdd = hyCurry(sum)

curryAdd(10,20,30)
curryAdd(10,20)(30)
curryAdd(10)(20)(30)

二十、CSS水平垂直居中

• 不定宽高div，实现子元素垂直、水平居中，三种以上3

二十一、CSS画三角形

二十二、CSS实现两栏和三栏布局

二十三、手写发布-订阅模式 || EventEmitter

on

发布和订阅
发布和订阅。在type上添加订阅者

emit

执行该订阅下的所有函数
执行该订阅下的所有函数。遍历type下的订阅者，执行。

off

取消某个函数的订阅
取消某个函数的订阅。在订阅者中找到fn然后删除

once
只执行一次订阅事件
once方法将handler函数挂载了type这个发布者上，如果执行emit就会执行handler函数中的内容，会先删除type上的所有的函数，然后执行fn。

class EventBus {
  constructor() {
    this.tasks = {}; // 按事件名称创建任务队列
  }

  /**
   * 注册事件（订阅）
   * @param {String} type  事件名称
   * @param {Function} fn  回调函数
   */
  on(type, fn) {
    // 如果还没有注册过该事件，则创建对应事件的队列
    if (!this.tasks[type]) {
      this.tasks[type] = [];
    }
    // 将回调函数加入队列
    this.tasks[type].push(fn);
  }
  
  /**
   * 注册一个只能执行一次的事件
   * @params type[String] 事件类型
   * @params fn[Function] 回调函数
   */
  once(type, fn) {
    if (!this.tasks[type]) {
      this.tasks[type] = [];
    }

    const that = this;
    // 注意该函数必须是具名函数，因为需要删除，但该名称只在函数内部有效
    function _once(...args) {
      fn(...args);
      that.off(type, _once); // 执行一次后注销
    }

    this.tasks[type].push(_once);
  }

  /**
   * 触发事件（发布）
   * @param {String} type  事件名称
   * @param {...any} args  传入的参数，不限个数
   */
  emit(type, ...args) {
    // 如果该事件没有被注册，则返回
    if (!this.tasks[type]) {
      return;
    }
    // 遍历执行对应的回调数组，并传入参数
    this.tasks[type].forEach((fn) => fn(...args));
  }

  /**
   * 移除指定回调（取消订阅）
   * @param {String} type  事件名称
   * @param {Function} fn  回调函数
   */
  off(type, fn) {
    const tasks = this.tasks[type];
    // 校验事件队列是否存在
    if (!Array.isArray(tasks)) {
      return;
    }

    // 利用 filter 删除队列中的指定函数
    this.tasks[type] = tasks.filter((cb) => fn !== cb);
  }
}

另附：手写观察者

Subject是构造函数，new Subject() 创建一个主题对象，该对象内部维护订阅当前主题的观察者数组。主题对象上有一些方法，如添加观察者(addObserver)、删除观察者(removeObserver)、通知观察者更新(notify)。 当notify 时实际上调用全部观察者 observer 自身的 update 方法。

Observer 是构造函数，new Observer() 创建一个观察者对象，该对象有一个 update 方法，观察者可以订阅主题，实际上是把自己加入到主题的订阅者列表里。

class Subject{
    
    observers = [];
    
    addObserver(observer){
        this.observers.push(observer)
    }
    removeObserver(observer){
        let index = this.observers.indexOf(observer)
        if(index>-1){
            this.observers.splice(index,1)
        }
    }
    notify(){
        this.observers.forEach(observer=>{
            observer.update()
        })
    }

}

class Observer{
    update(){
        subscribeTo(subject){
            dubject.addObserver(this)
        }
    }
}


//测试代码
let subject = new Subject()
let observer = new Observer()
observer.update = function(){
    console.log('observer update')
}
observer.subscribeTo(subject)  //观察者订阅主题
subject.notify()

二十四、下拉框

二十五、实现一个圆绕着中心一直转

<!doctype html>
<html lang="en">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <title> 页面名称 </title>
    <style type="text/css">
        @keyframes animX{
            0% {left: 0px;}
            100% {left: 500px;}
        }
        @keyframes animY{
            0% {top: 0px;}
            100% {top: 500px;}
        }

        #ball {
            width: 100px;
            height: 100px;
            background-color: #f99;
            border-radius: 50%;
            position: absolute;
            animation:animX 4s ease-in-out -2s infinite alternate, animY 4s ease-in-out infinite alternate;
        }
    </style>
</head>
<body>
<div id="ball"></div>
</body>
</html>

二十六、手写简单轮询

轮询请求就是间隔相同的时间（如5s）后不断地向服务端发起同一个接口的请求，当然不能无限次去请求，所以轮询必须要有个停止轮询的机制。

首先能想到的就是用setInterval去实现，但是setInterval做轮询的话，会有以下严重的问题

1. 即使调用的代码报错了，setInterval会持续的调用
2. setInterval不会等到上一次的请求响应后再执行，只要到了指定的时间间隔就会执行，哪怕有报错也会执行
3. setInterval定时不准确，这个跟事件循环有关，这里不展开啦~

function setTimer () {
         let timer
        axios.post(url, params)
        .then(function (res) {
            if(res){
                console.log(res);
                timer = setTimeout(() => {
                    this.setTimer()
                }, 5000)       
            }else {
                clearTimeout(timer) //清理定时任务
            }
            
        })
        .catch(function (error) {
                console.log(error);
        });
},           

二十七、使用闭包实现数据缓存

/*
* 使用立即执行函数
* */
var cacheConfig = (function(){
    var obj={};
    return {
        setCache:function(k,v){
            obj[k]=v;
        },
        getCache:function(k){
            return obj[k];
        }
    }
})();

场景题、

1.实现sleep休眠函数

function Sleep(time){
	return new Promise(resolve=>{
		setTimeout(resolve, time);
	})
}

(async function(){
	console.log('start sleep in '+ new Date());
	await Sleep(7000);
	console.log('end sleep in ' + new Date());
})()

2.setTimeout 实现 setInterval

function setInterval(fn, time){
    var interval = function(){
    // time时间过去，这个异步被执行，而内部执行的函数正是interval，就相当于进了一个循环
        setTimeout(interval, time);
    // 同步代码
        fn();
    }
    //interval被延迟time时间执行
    setTimeout(interval,time); 
}

3.异步循环打印 1，2，3

var sleep = function (time, i) {
  return new Promise(function (resolve, reject) {
    setTimeout(function () {
      resolve(i);
    }, time);
  })
};


var start = async function () {
  for (let i = 1; i <= 3; i++) {
    let result = await sleep(1000, i);
    console.log(result);
  }
};

start();

4.循环打印红、黄、绿

function red() {
    console.log('red');
}
function green() {
    console.log('green');
}
function yellow() {
    console.log('yellow');
}

const task = (timer, light) => {
    new Promise((resolve, reject) => {
        setTimeout(() => {
            if (light === 'red') {
                red()
            }
            else if (light === 'green') {
                green()
            }
            else if (light === 'yellow') {
                yellow()
            }
            resolve()
        }, timer)
    })
}
const taskRunner =  async () => {
    await task(3000, 'red')
    await task(2000, 'green')
    await task(2100, 'yellow')
    taskRunner()
}
taskRunner()

中频

1.手写事件委托

function delegateEvent(parent,selector,type,fn){}

parent:事件绑定的父级

selector:选择器

type:事件类型

handle:事件处理函数

写之前先了解一下事件委托的概念：
它是通过事件冒泡机制，
即子元素上触发的事件会冒泡到父级上，即父级也会触发该类型的事件，
通过父级触发的事件拿到事件源对象e.target就可以知道真正触发事件的元素是什么。

举个例子，一个ul下面有1000个li，我们要给li绑定点击事件，如果给每个li都绑定一个点击事件会大量占用内存，不利于性能优化，这种情况下我们只需要在ul上绑定一个点击事件，通过class或者id来识别每个li，这样就大大减少了事件注册，而且再有新增的li时我们也无需再去注册点击事件

功能：点击li,哪个变成绿色,再次点击取消

HTML

<ul id="parent">
	  <li>1</li>
	  <li>1</li>
	  <li>1</li>
</ul>

CSS

.active{
	background-color:green;
}

JS

const parent = document.getElementById('parent')
function changeColor(){
	if(this.classList.contains('active')){
		this.classList.remove('active')
	}else{
		this.classList.add('active');
	}
}
delegateEvent(parent,'li','click',changeColor)

事件委托函数

// ============ 简单的事件委托
function  delegateEvent(parent, selector, type, fn) {
	 
     
     if (parent.addEventListener){
     parent.addEventListener(type, eventfn,false);
     } else {//兼容老IE
     parent.attachEvent( "on" + type, eventfn);
     }
     
     function  eventfn(e){
         //兼容老IE
         const  e = e || window.event;    
         //兼容老IE
         const  target = e.target || e.srcElement;
        //如果目标元素与选择器匹配则执行函数
         if  (matchSelector(target, selector)) {
                 if (fn) {//将fn内部的this指向target（在此之前this都是指向的绑定事件的元素即interfaceEle）
                     fn.call(target, e); 
                 }
         }
     }
    
    
}


/**
  * only support #id, tagName, .className
  * and it's simple single, no combination
  */
//比较函数：判断事件的作用目标是否与选择器匹配；匹配则返回true
function  matchSelector(ele, selector) {
     // 如果选择器为ID
     if  (selector.charAt(0) ===  "#" ) {            
         return  ele.id === selector.slice(1);   
     }
      //charAt(0),返回索引为0的字符
    //slice(a，b),从已有的数组或字符串返回从索引从a处开始，截取到索引b之前的子数组或子字符串；
    
     //如果选择器为Class
     if  (selector.charAt(0) ===  "." ) {
         return  ( " "  + ele.className +  " " ).indexOf( " "  + selector.slice(1) +  " " ) != -1;
     }
     // 如果选择器为tagName
     return  ele.tagName.toLowerCase() === selector.toLowerCase();
}
//toLowerCase()将字符串转换成小写

2.DOM操作相关题目

3.手写列表转树

4.日期时间格式化

5.数字千分位

6.URL参数解析

7.大数相加

8.手写 Promise（进阶)

原文地址：http://www.cnblogs.com/guibi/p/16870463.html