手写题

promise

实现promise

// MyPromise.js

// 先定义三个常量表示状态
const PENDING = 'pending';
const FULFILLED = 'fulfilled';
const REJECTED = 'rejected';

// 新建 MyPromise 类
class MyPromise {
  constructor(executor){
    // executor 是一个执行器，进入会立即执行
    // 并传入resolve和reject方法
    try {
      executor(this.resolve, this.reject)
    } catch (error) {
      this.reject(error)
    }
  }

  // 储存状态的变量，初始值是 pending
  status = PENDING;
  // 成功之后的值
  value = null;
  // 失败之后的原因
  reason = null;

  // 存储成功回调函数
  onFulfilledCallbacks = [];
  // 存储失败回调函数
  onRejectedCallbacks = [];

  // 更改成功后的状态
  resolve = (value) => {
    // 只有状态是等待，才执行状态修改
    if (this.status === PENDING) {
      // 状态修改为成功
      this.status = FULFILLED;
      // 保存成功之后的值
      this.value = value;
      // resolve里面将所有成功的回调拿出来执行
      while (this.onFulfilledCallbacks.length) {
        // Array.shift() 取出数组第一个元素，然后（）调用，shift不是纯函数，取出后，数组将失去该元素，直到数组为空
        this.onFulfilledCallbacks.shift()(value)
      }
    }
  }

  // 更改失败后的状态
  reject = (reason) => {
    // 只有状态是等待，才执行状态修改
    if (this.status === PENDING) {
      // 状态成功为失败
      this.status = REJECTED;
      // 保存失败后的原因
      this.reason = reason;
      // resolve里面将所有失败的回调拿出来执行
      while (this.onRejectedCallbacks.length) {
        this.onRejectedCallbacks.shift()(reason)
      }
    }
  }

  then(onFulfilled, onRejected) {
    const realOnFulfilled = typeof onFulfilled === 'function' ? onFulfilled : value => value;
    const realOnRejected = typeof onRejected === 'function' ? onRejected : reason => {throw reason};

    // 为了链式调用这里直接创建一个 MyPromise，并在后面 return 出去
    const promise2 = new MyPromise((resolve, reject) => {
      const fulfilledMicrotask = () =>  {
        // 创建一个微任务等待 promise2 完成初始化
        queueMicrotask(() => {
          try {
            // 获取成功回调函数的执行结果
            const x = realOnFulfilled(this.value);
            // 传入 resolvePromise 集中处理
            resolvePromise(promise2, x, resolve, reject);
          } catch (error) {
            reject(error)
          }
        })
      }

      const rejectedMicrotask = () => {
        // 创建一个微任务等待 promise2 完成初始化
        queueMicrotask(() => {
          try {
            // 调用失败回调，并且把原因返回
            const x = realOnRejected(this.reason);
            // 传入 resolvePromise 集中处理
            resolvePromise(promise2, x, resolve, reject);
          } catch (error) {
            reject(error)
          }
        })
      }
      // 判断状态
      if (this.status === FULFILLED) {
        fulfilledMicrotask()
      } else if (this.status === REJECTED) {
        rejectedMicrotask()
      } else if (this.status === PENDING) {
        // 等待
        // 因为不知道后面状态的变化情况，所以将成功回调和失败回调存储起来
        // 等到执行成功失败函数的时候再传递
        this.onFulfilledCallbacks.push(fulfilledMicrotask);
        this.onRejectedCallbacks.push(rejectedMicrotask);
      }
    })

    return promise2;
  }

  // resolve 静态方法
  static resolve (parameter) {
    // 如果传入 MyPromise 就直接返回
    if (parameter instanceof MyPromise) {
      return parameter;
    }

    // 转成常规方式
    return new MyPromise(resolve =>  {
      resolve(parameter);
    });
  }

  // reject 静态方法
  static reject (reason) {
    return new MyPromise((resolve, reject) => {
      reject(reason);
    });
  }
}

function resolvePromise(promise2, x, resolve, reject) {
  // 如果相等了，说明return的是自己，抛出类型错误并返回
  if (promise2 === x) {
    return reject(new TypeError('Chaining cycle detected for promise #<Promise>'))
  }
  // 判断x是不是 MyPromise 实例对象
  if(x instanceof MyPromise) {
    // 执行 x，调用 then 方法，目的是将其状态变为 fulfilled 或者 rejected
    // x.then(value => resolve(value), reason => reject(reason))
    // 简化之后
    x.then(resolve, reject)
  } else{
    // 普通值
    resolve(x)
  }
}

module.exports = MyPromise;

实现promise.all

function PromiseAll(promises){
    return new Promise((resolve, reject)=>{
        if(!Array.isArray(promises)){
            throw new TypeError("promises must be an array")
        }
        let result = []
        let count = 0
        promises.forEach((promise, index) => {
            promise.then((res)=>{
                result[index] = res
                count++
                count === promises.length && resolve(result)
            }, (err)=>{
                reject(err)
            })
        })
    })
}

实现 promise.finally

Promise.prototype.finally = function (cb) {
  return this.then(function (value) {
    return Promise.resolve(cb()).then(function () {
      return value
    })
  }, function (err) {
    return Promise.resolve(cb()).then(function () {
      throw err
    })
  })
}

实现promise.allSettled

function allSettled(promises) {
  if (promises.length === 0) return Promise.resolve([])

  const _promises = promises.map(
    item => item instanceof Promise ? item : Promise.resolve(item)
    )

  return new Promise((resolve, reject) => {
    const result = []
    let unSettledPromiseCount = _promises.length

    _promises.forEach((promise, index) => {
      promise.then((value) => {
        result[index] = {
          status: 'fulfilled',
          value
        }

        unSettledPromiseCount -= 1
        // resolve after all are settled
        if (unSettledPromiseCount === 0) {
          resolve(result)
        }
      }, (reason) => {
        result[index] = {
          status: 'rejected',
          reason
        }

        unSettledPromiseCount -= 1
        // resolve after all are settled
        if (unSettledPromiseCount === 0) {
          resolve(result)
        }
      })
    })
  })
}

实现promise.race

Promise.race = function(promiseArr) {
    return new Promise((resolve, reject) => {
        promiseArr.forEach(p => {
            Promise.resolve(p).then(val => {
                resolve(val)
            }, err => {
                rejecte(err)
            })
        })
    })
}

来说一下如何串行执行多个Promise

// 一个封装的延迟函数，然后一个装有3,4,5的数组，需求就是在开始执行时依次等待3, 4, 5秒，并在之后打印对应输出

function delay(time) {
  return new Promise((resolve, reject) => {
    console.log(`wait ${time}s`)
    setTimeout(() => {
      console.log('execute');
      resolve()
    }, time * 1000)
  })
}

const arr = [3, 4, 5];

// wait 3s // 等待3s

// execute
// wait 4s // 等待4s

// execute
// wait 5s // 等待5s

// execute

方式1. reduce

arr.reduce((s, v) => {
  return s.then(() => delay(v))
}, Promise.resolve())

方式2. async + 循环 + await

(
  async function () {
    for (const v of arr) {
      await delay(v)
    }
  }
)()

方式3. 普通循环

let p = Promise.resolve()
for (const i of arr) {
  p = p.then(() => delay(i))
}

方式4. 递归

function dispatch(i, p = Promise.resolve()) {
  if (!arr[i]) return Promise.resolve()
  return p.then(() => dispatch(i + 1, delay(arr[i])))
}
dispatch(0)

方式5. for await of

function createAsyncIterable(arr) {
  return {
    [Symbol.asyncIterator]() {
      return {
        i: 0,
        next() {
          if (this.i < arr.length) {
            return delay(arr[this.i]).then(() => ({ value: this.i++, done: false }));
          }

          return Promise.resolve({ done: true });
        }
      };
    }
  }
}

(async function () {
  for await (i of createAsyncIterable(arr)) { }
})();

方式6. generator

function* gen() {
  for (const v of arr) {
    yield delay(v)
  }
}

function run(gen) {
  const g = gen()

  function next(data) {
    const result = g.next(data)
    if (result.done) return result.value
    result.value.then(function(data) {
      next(data)
    })
  }

  next()
}

run(gen)

Promise.any

Promise.any = function(promiseArr) {
    let index = 0
    return new Promise((resolve, reject) => {
        if (promiseArr.length === 0) return
        promiseArr.forEach((p, i) => {
            Promise.resolve(p).then(val => {
                resolve(val)
            }, err => {
                index++
                if (index === promiseArr.length) {
                  reject(new AggregateError('All promises were rejected'))
                }
            })
        })
    })
}

Resolve

Promise.resolve = function(value) {
    if(value instanceof Promise){
        return value
    }
    return new Promise(resolve => resolve(value))
}

Reject

Promise.reject = function(reason) {
    return new Promise((resolve, reject) => reject(reason))
}

Array篇

数组去重

使用双重 for 和 splice

function unique(arr){
    for(var i=0; i<arr.length; i++){
        for(var j=i+1; j<arr.length; j++){
            if(arr[i]==arr[j]){
            //第一个等同于第二个，splice方法删除第二个
                arr.splice(j,1);
                // 删除后注意回调j
                j--;
            }
        }
    }
return arr;
}

使用 indexOf 或 includes 加新数组

//使用indexof
function unique(arr) {
    var uniqueArr = []; // 新数组
    for (let i = 0; i < arr.length; i++) {
        if (uniqueArr.indexOf(arr[i]) === -1) {
            //indexof返回-1表示在新数组中不存在该元素
            uniqueArr.push(arr[i])//是新数组里没有的元素就push入
        }
    }
    return uniqueArr;
}
// 使用includes
function unique(arr) {
    var uniqueArr = [];
    for (let i = 0; i < arr.length; i++) {
        //includes 检测数组是否有某个值
        if (!uniqueArr.includes(arr[i])) {
            uniqueArr.push(arr[i])//
        }
    }
    return uniqueArr;
}

sort 排序后，使用快慢指针的思想

function unique(arr) {
    arr.sort((a, b) => a - b);
    var slow = 1,
        fast = 1;
    while (fast < arr.length) {
        if (arr[fast] != arr[fast - 1]) {
            arr[slow ++] = arr[fast];
        }
        ++ fast;
    }
    arr.length = slow;
    return arr;
}

Sort 方法用于从小到大排序(返回一个新数组)，其参数中不带以上回调函数就会在两位数及以上时出现排序错误(如果省略，元素按照转换为的字符串的各个字符的 Unicode 位点进行排序。两位数会变为长度为二的字符串来计算)。

ES6 提供的 Set 去重

function unique(arr) {
    const result = new Set(arr);
    return [...result];
    //使用扩展运算符将Set数据结构转为数组
}

使用哈希表存储元素是否出现(ES6 提供的 map)

function unique(arr) {
    let map = new Map();
    let uniqueArr = new Array();  // 数组用于返回结果
    for (let i = 0; i < arr.length; i++) {
      if(map.has(arr[i])) {  // 如果有该key值
        map.set(arr[i], true);
      } else {
        map.set(arr[i], false);   // 如果没有该key值
        uniqueArr.push(arr[i]);
      }
    }
    return uniqueArr ;
}

filter 配合 indexOf

function unique(arr) {
    return arr.filter(function (item, index, arr) {
        //当前元素，在原始数组中的第一个索引==当前索引值，否则返回当前元素
        //不是那么就证明是重复项，就舍弃
        return arr.indexOf(item) === index;
    })
}

reduce 配合 includes

function unique(arr){
    let uniqueArr = arr.reduce((acc,cur)=>{
        if(!acc.includes(cur)){
            acc.push(cur);
        }
        return acc;
    },[]) // []作为回调函数的第一个参数的初始值
    return uniqueArr
}

数组扁平化

Array.prototype.flat()
遍历数组的方案

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }];
// 遍历数组的方法有太多，本文只枚举常用的几种
// for 循环
for (let i = 0; i < arr.length; i++) {
  console.log(arr[i]);
}
// for...of
for (let value of arr) {
  console.log(value);
}
// for...in
for (let i in arr) {
  console.log(arr[i]);
}
// forEach 循环
arr.forEach(value => {
  console.log(value);
});
// entries（）
for (let [index, value] of arr.entries()) {
  console.log(value);
}
// keys()
for (let index of arr.keys()) {
  console.log(arr[index]);
}
// values()
for (let value of arr.values()) {
  console.log(value);
}
// reduce()
arr.reduce((pre, cur) => {
  console.log(cur);
}, []);
// map()
arr.map(value => console.log(value));

判断元素是数组的方案
- instanceof
- constructor
- Object.prototype.toString
- isArray

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }];
// concat + 递归
function flat(arr) {
  let arrResult = [];
  arr.forEach(item => {
    if (Array.isArray(item)) {
      arrResult = arrResult.concat(arguments.callee(item));   // 递归
      // 或者用扩展运算符
      // arrResult.push(...arguments.callee(item));
    } else {
      arrResult.push(item);
    }
  });
  return arrResult;
}
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学" }];

用 reduce 实现 flat 函数

const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }]

// 首先使用 reduce 展开一层
arr.reduce((pre, cur) => pre.concat(cur), []);
// [1, 2, 3, 4, 1, 2, 3, [1, 2, 3, [1, 2, 3]], 5, "string", { name: "弹铁蛋同学" }];

// 用 reduce 展开一层 + 递归
const flat = arr => {
  return arr.reduce((pre, cur) => {
    return pre.concat(Array.isArray(cur) ? flat(cur) : cur);
  }, []);
};
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学" }];

使用栈的思想实现 flat 函数

// 栈思想
function flat(arr) {
  const result = [];
  const stack = [].concat(arr);  // 将数组元素拷贝至栈，直接赋值会改变原数组
  //如果栈不为空，则循环遍历
  while (stack.length !== 0) {
    const val = stack.pop();
    if (Array.isArray(val)) {
      stack.push(...val); //如果是数组再次入栈，并且展开了一层
    } else {
      result.unshift(val); //如果不是数组就将其取出来放入结果数组中
    }
  }
  return result;
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }]
flat(arr)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学" }];

通过传入整数参数控制“拉平”层数

// reduce + 递归
function flat(arr, num = 1) {
  return num > 0
    ? arr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? flat(cur, num - 1) : cur),
        []
      )
    : arr.slice();
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }]
flat(arr, Infinity);
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学" }];

使用 Generator 实现 flat 函数

function* flat(arr, num) {
  if (num === undefined) num = 1;
  for (const item of arr) {
    if (Array.isArray(item) && num > 0) {   // num > 0
      yield* flat(item, num - 1);
    } else {
      yield item;
    }
  }
}
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }]
// 调用 Generator 函数后，该函数并不执行，返回的也不是函数运行结果，而是一个指向内部状态的指针对象。
// 也就是遍历器对象（Iterator Object）。所以我们要用一次扩展运算符得到结果
[...flat(arr, Infinity)]
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学" }];

实现在原型链上重写 flat 函数

Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = this.concat();    // 获得调用 fakeFlat 函数的数组
  while (num > 0) {
    if (arr.some(x => Array.isArray(x))) {
      arr = [].concat.apply([], arr);	// 数组中还有数组元素的话并且 num > 0，继续展开一层数组
    } else {
      break; // 数组中没有数组元素并且不管 num 是否依旧大于 0，停止循环。
    }
    num--;
  }
  return arr;
};
const arr = [1, 2, 3, 4, [1, 2, 3, [1, 2, 3, [1, 2, 3]]], 5, "string", { name: "弹铁蛋同学" }]
arr.fakeFlat(Infinity)
// [1, 2, 3, 4, 1, 2, 3, 1, 2, 3, 1, 2, 3, 5, "string", { name: "弹铁蛋同学" }];

考虑数组空位的情况

// reduce + 递归
Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = [].concat(this);
  return num > 0
    ? arr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? cur.fakeFlat(--num) : cur),
        []
      )
    : arr.slice();
};
const arr = [1, [3, 4], , ,];
arr.fakeFlat()
// [1, 3, 4]

// foEach + 递归
Array.prototype.fakeFlat = function(num = 1) {
  if (!Number(num) || Number(num) < 0) {
    return this;
  }
  let arr = [];
  this.forEach(item => {
    if (Array.isArray(item)) {
      arr = arr.concat(item.fakeFlat(--num));
    } else {
      arr.push(item);
    }
  });
  return arr;
};
const arr = [1, [3, 4], , ,];
arr.fakeFlat()
// [1, 3, 4]

ForEach

Array.prototype.myForEach = function (callbackFn) {
    // 判断this是否合法
    if (this === null || this === undefined) {
        throw new TypeError("Cannot read property 'myForEach' of null");
    }
    // 判断callbackFn是否合法
    if (Object.prototype.toString.call(callbackFn) !== "[object Function]") {
        throw new TypeError(callbackFn + ' is not a function')
    }
    // 取到执行方法的数组对象和传入的this对象
    var _arr = this, thisArg = arguments[1] || window;
    for (var i = 0; i < _arr.length; i++) {
        // 执行回调函数
        callbackFn.call(thisArg, _arr[i], i, _arr);
    }
}

Reduce

Array.prototype.myReduce = function(callbackFn) {
    var _arr = this, accumulator = arguments[1];
    var i = 0;
    // 判断是否传入初始值
    if (accumulator === undefined) {
        // 没有初始值的空数组调用reduce会报错
        if (_arr.length === 0) {
            throw new Error('initVal and Array.length>0 need one')
        }
        // 初始值赋值为数组第一个元素
        accumulator = _arr[i];
        i++;
    }
    for (; i<_arr.length; i++) {
        // 计算结果赋值给初始值
        accumulator = callbackFn(accumulator,  _arr[i], i, _arr)
    }
    return accumulator;
}

Map

Array.prototype.myMap = function(callbackFn) {
    var _arr = this, thisArg = arguments[1] || window, res = [];
    for (var i = 0; i<_arr.length; i++) {
        // 存储运算结果
        res.push(callbackFn.call(thisArg, _arr[i], i, _arr));
    }
    return res;
}

Filter

Array.prototype.myFilter = function(callbackFn) {
    var _arr = this, thisArg = arguments[1] || window, res = [];
    for (var i = 0; i<_arr.length; i++) {
        // 回调函数执行为true
        if (callbackFn.call(thisArg, _arr[i], i, _arr)) {
            res.push(_arr[i]);
        }
    }
    return res;
}

Every

Array.prototype.myEvery = function(callbackFn) {
    var _arr = this, thisArg = arguments[1] || window;
    // 开始标识值为true
    // 遇到回调返回false，直接返回false
    // 如果循环执行完毕，意味着所有回调返回值为true，最终结果为true
    var flag = true;
    for (var i = 0; i<_arr.length; i++) {
        // 回调函数执行为false，函数中断
        if (!callbackFn.call(thisArg, _arr[i], i, _arr)) {
            return false;
        }
    }
    return flag;
}

Some

Array.prototype.mySome = function(callbackFn) {
    var _arr = this, thisArg = arguments[1] || window;
    // 开始标识值为false
    // 遇到回调返回true，直接返回true
    // 如果循环执行完毕，意味着所有回调返回值为false，最终结果为false
    var flag = false;
    for (var i = 0; i<_arr.length; i++) {
        // 回调函数执行为false，函数中断
        if (callbackFn.call(thisArg, _arr[i], i, _arr)) {
            return true;
        }
    }
    return flag;
}

Find/findIndex

Array.prototype.myFind = function(callbackFn) {
    var _arr = this, thisArg = arguments[1] || window;
    // 遇到回调返回true，直接返回该数组元素
    // 如果循环执行完毕，意味着所有回调返回值为false，最终结果为undefined
    for (var i = 0; i<_arr.length; i++) {
        // 回调函数执行为false，函数中断
        if (callbackFn.call(thisArg, _arr[i], i, _arr)) {
            return _arr[i];
        }
    }
    return undefined;
}

IndexOf

function indexOf(findVal, beginIndex = 0) {
    if (this.length < 1 || beginIndex > findVal.length) {
        return -1;
    }
    if (!findVal) {
        return 0;
    }
    beginIndex = beginIndex <= 0 ? 0 : beginIndex;
    for (let i = beginIndex; i < this.length; i++) {
        if (this[i] == findVal) return i;
    }
    return -1;
}

实现sort

const sort = (arr, comparefn) => {
  let array = Object(arr);
  let length = array.length >>> 0;
  return InnerArraySort(array, length, comparefn);
}

const InnerArraySort = (array, length, comparefn) => {
  // 比较函数未传入
  if (Object.prototype.toString.call(comparefn) !== "[object Function]") {
    comparefn = function (x, y) {
      if (x === y) return 0;
      x = x.toString();
      y = y.toString();
      if (x == y) return 0;
      else return x < y ? -1 : 1;
    };
  }
  const insertSort = (arr, start = 0, end) => {
    end = end || arr.length;
    for (let i = start; i < end; i++) {
      let e = arr[i];
      let j;
      for (j = i; j > start && comparefn(arr[j - 1], e) > 0; j--)
        arr[j] = arr[j - 1];
      arr[j] = e;
    }
    return;
  }
  const getThirdIndex = (a, from, to) => {
    let tmpArr = [];
    // 递增量，200~215 之间，因为任何正数和15做与操作，不会超过15，当然是大于0的
    let increment = 200 + ((to - from) & 15);
    let j = 0;
    from += 1;
    to -= 1;
    for (let i = from; i < to; i += increment) {
      tmpArr[j] = [i, a[i]];
      j++;
    }
    // 把临时数组排序，取中间的值，确保哨兵的值接近平均位置
    tmpArr.sort(function (a, b) {
      return comparefn(a[1], b[1]);
    });
    let thirdIndex = tmpArr[tmpArr.length >> 1][0];
    return thirdIndex;
  };

  const _sort = (a, b, c) => {
    let arr = [];
    arr.push(a, b, c);
    insertSort(arr, 0, 3);
    return arr;
  }

  const quickSort = (a, from, to) => {
    //哨兵位置
    let thirdIndex = 0;
    while (true) {
      if (to - from <= 10) {
        insertSort(a, from, to);
        return;
      }
      if (to - from > 1000) {
        thirdIndex = getThirdIndex(a, from, to);
      } else {
        // 小于1000 直接取中点
        thirdIndex = from + ((to - from) >> 2);
      }
      let tmpArr = _sort(a[from], a[thirdIndex], a[to - 1]);
      a[from] = tmpArr[0]; a[thirdIndex] = tmpArr[1]; a[to - 1] = tmpArr[2];
      // 现在正式把 thirdIndex 作为哨兵
      let pivot = a[thirdIndex];
      [a[from], a[thirdIndex]] = [a[thirdIndex], a[from]];
      // 正式进入快排
      let lowEnd = from + 1;
      let highStart = to - 1;
      a[thirdIndex] = a[lowEnd];
      a[lowEnd] = pivot;
      // [lowEnd, i)的元素是和pivot相等的
      // [i, highStart) 的元素是需要处理的
      for (let i = lowEnd + 1; i < highStart; i++) {
        let element = a[i];
        let order = comparefn(element, pivot);
        if (order < 0) {
          a[i] = a[lowEnd];
          a[lowEnd] = element;
          lowEnd++;
        } else if (order > 0) {
          do{
            highStart--;
            if (highStart === i) break;
            order = comparefn(a[highStart], pivot);
          }while (order > 0) ;
          // 现在 a[highStart] <= pivot
          // a[i] > pivot
          // 两者交换
          a[i] = a[highStart];
          a[highStart] = element;
          if (order < 0) {
            // a[i] 和 a[lowEnd] 交换
            element = a[i];
            a[i] = a[lowEnd];
            a[lowEnd] = element;
            lowEnd++;
          }
        }
      }
      // 永远切分大区间
      if (lowEnd - from > to - highStart) {
        // 单独处理小区间
        quickSort(a, highStart, to);
        // 继续切分lowEnd ~ from 这个区间
        to = lowEnd;
      } else if (lowEnd - from <= to - highStart) {
        quickSort(a, from, lowEnd);
        from = highStart;
      }
    }
  }
  quickSort(array, 0, length);
}

防抖节流

实现防抖函数debounce

function debounce(func, wait, immediate) {

    var timeout, result;

    var debounced = function () {
        var context = this;
        var args = arguments;

        if (timeout) clearTimeout(timeout);
        if (immediate) {
            // 如果已经执行过，不再执行
            var callNow = !timeout;
            timeout = setTimeout(function(){
                timeout = null;
            }, wait)
            if (callNow) result = func.apply(context, args)
        }
        else {
            timeout = setTimeout(function(){
                result = func.apply(context, args)
            }, wait);
        }
        return result;
    };

    debounced.cancel = function() {
        clearTimeout(timeout);
        timeout = null;
    };

    return debounced;
}

实现节流函数throttle

// 第四版
function throttle(func, wait, options) {
    var timeout, context, args, result;
    var previous = 0;
    if (!options) options = {};

    var later = function() {
        previous = options.leading === false ? 0 : new Date().getTime();
        timeout = null;
        func.apply(context, args);
        if (!timeout) context = args = null;
    };

    var throttled = function() {
        var now = new Date().getTime();
        if (!previous && options.leading === false) previous = now;
        var remaining = wait - (now - previous);
        context = this;
        args = arguments;
        if (remaining <= 0 || remaining > wait) {
            if (timeout) {
                clearTimeout(timeout);
                timeout = null;
            }
            previous = now;
            func.apply(context, args);
            if (!timeout) context = args = null;
        } else if (!timeout && options.trailing !== false) {
            timeout = setTimeout(later, remaining);
        }
    };
    return throttled;
}

Object篇

能不能写一个完整的深拷贝

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

实现new

function createObject(Con) {
    // 创建新对象obj
    // var obj = {};也可以
    var obj = Object.create(null);

    // 将obj.__proto__ -> 构造函数原型
    // (不推荐)obj.__proto__ = Con.prototype
    Object.setPrototypeOf(obj, Con.prototype);

    // 执行构造函数，并接受构造函数返回值
    const ret = Con.apply(obj, [].slice.call(arguments, 1));

    // 若构造函数返回值为对象，直接返回该对象
    // 否则返回obj
    return typeof(ret) === 'object' ? ret: obj;
}

继承

原型链继承

function Parent () {
    this.name = 'kevin';
}

Parent.prototype.getName = function () {
    console.log(this.name);
}

function Child () {

}

Child.prototype = new Parent();

var child1 = new Child();

console.log(child1.getName()) // kevin

问题：

引用类型的属性被所有实例共享，举个例子：

function Parent () {
    this.names = ['kevin', 'daisy'];
}

function Child () {

}

Child.prototype = new Parent();

var child1 = new Child();

child1.names.push('yayu');

console.log(child1.names); // ["kevin", "daisy", "yayu"]

var child2 = new Child();

console.log(child2.names); // ["kevin", "daisy", "yayu"]

在创建 Child 的实例时，不能向Parent传参

借用构造函数(经典继承)

function Parent () {
    this.names = ['kevin', 'daisy'];
}

function Child () {
    Parent.call(this);
}

var child1 = new Child();

child1.names.push('yayu');

console.log(child1.names); // ["kevin", "daisy", "yayu"]

var child2 = new Child();

console.log(child2.names); // ["kevin", "daisy"]

优点：

避免了引用类型的属性被所有实例共享
可以在 Child 中向 Parent 传参

举个例子：

function Parent (name) {
    this.name = name;
}

function Child (name) {
    Parent.call(this, name);
}

var child1 = new Child('kevin');

console.log(child1.name); // kevin

var child2 = new Child('daisy');

console.log(child2.name); // daisy

缺点：

方法都在构造函数中定义，每次创建实例都会创建一遍方法。

组合继承

原型链继承和经典继承双剑合璧。

function Parent (name) {
    this.name = name;
    this.colors = ['red', 'blue', 'green'];
}

Parent.prototype.getName = function () {
    console.log(this.name)
}

function Child (name, age) {

    Parent.call(this, name);

    this.age = age;

}

Child.prototype = new Parent();

var child1 = new Child('kevin', '18');

child1.colors.push('black');

console.log(child1.name); // kevin
console.log(child1.age); // 18
console.log(child1.colors); // ["red", "blue", "green", "black"]

var child2 = new Child('daisy', '20');

console.log(child2.name); // daisy
console.log(child2.age); // 20
console.log(child2.colors); // ["red", "blue", "green"]

优点：融合原型链继承和构造函数的优点，是 JavaScript 中最常用的继承模式。

原型式继承

function createObj(o) {
    function F(){}
    F.prototype = o;
    return new F();
}

就是 ES5 Object.create 的模拟实现，将传入的对象作为创建的对象的原型。

缺点：

包含引用类型的属性值始终都会共享相应的值，这点跟原型链继承一样。

var person = {
    name: 'kevin',
    friends: ['daisy', 'kelly']
}

var person1 = createObj(person);
var person2 = createObj(person);

person1.name = 'person1';
console.log(person2.name); // kevin

person1.firends.push('taylor');
console.log(person2.friends); // ["daisy", "kelly", "taylor"]

注意：修改person1.name的值，person2.name的值并未发生改变，并不是因为person1和person2有独立的 name 值，而是因为person1.name = 'person1'，给person1添加了 name 值，并非修改了原型上的 name 值。

寄生式继承

创建一个仅用于封装继承过程的函数，该函数在内部以某种形式来做增强对象，最后返回对象。

function createObj (o) {
    var clone = object.create(o);
    clone.sayName = function () {
        console.log('hi');
    }
    return clone;
}

缺点：跟借用构造函数模式一样，每次创建对象都会创建一遍方法。

寄生组合式继承

为了方便大家阅读，在这里重复一下组合继承的代码：

function Parent (name) {
    this.name = name;
    this.colors = ['red', 'blue', 'green'];
}

Parent.prototype.getName = function () {
    console.log(this.name)
}

function Child (name, age) {
    Parent.call(this, name);
    this.age = age;
}

Child.prototype = new Parent();

var child1 = new Child('kevin', '18');

console.log(child1)

组合继承最大的缺点是会调用两次父构造函数。

一次是设置子类型实例的原型的时候：

Child.prototype = new Parent();

一次在创建子类型实例的时候：

var child1 = new Child('kevin', '18');

回想下 new 的模拟实现，其实在这句中，我们会执行：

Parent.call(this, name);

在这里，我们又会调用了一次 Parent 构造函数。所以，在这个例子中，如果我们打印 child1 对象，我们会发现 Child.prototype 和 child1 都有一个属性为colors，属性值为['red', 'blue', 'green']。

那么我们该如何精益求精，避免这一次重复调用呢？

如果我们不使用 Child.prototype = new Parent() ，而是间接的让 Child.prototype 访问到 Parent.prototype 呢？

看看如何实现：

function Parent (name) {
    this.name = name;
    this.colors = ['red', 'blue', 'green'];
}

Parent.prototype.getName = function () {
    console.log(this.name)
}

function Child (name, age) {
    Parent.call(this, name);
    this.age = age;
}

// 关键的三步
var F = function () {};

F.prototype = Parent.prototype;

Child.prototype = new F();


var child1 = new Child('kevin', '18');

console.log(child1);

最后我们封装一下这个继承方法：

function object(o) {
    function F() {}
    F.prototype = o;
    return new F();
}

function prototype(child, parent) {
    var prototype = object(parent.prototype);
    prototype.constructor = child;
    child.prototype = prototype;
}

// 当我们使用的时候：
prototype(Child, Parent);

Class实现继承

class Animal {
    constructor(name) {
        this.name = name
    }
    getName() {
        return this.name
    }
}
class Dog extends Animal {
    constructor(name, age) {
        super(name)
        this.age = age
    }
}

实现object.create

function newCreate(proto, propertiesObject) {
    if (typeof proto !== 'object' && typeof proto !== 'function') {
        throw TypeError('Object prototype may only be an Object: ' + proto)
    }
    function F() { }
    F.prototype = proto
    const o = new F()

    if (propertiesObject !== undefined) {
        Object.keys(propertiesObject).forEach(prop => {
            let desc = propertiesObject[prop]
            if (typeof desc !== 'object' || desc === null) {
                throw TypeError('Object prorotype may only be an Object: ' + desc)
            } else {
                Object.defineProperty(o, prop, desc)
            }
        })
    }

    return o
}

Function篇

Call

Function.prototype.myCall = function (thisArg) {
    thisArg = thisArg || window;
    thisArg.func = this;
    const args = []
    for (let i = 1; i<arguments.length; i++) {
        args.push('arguments['+ i + ']')
    }
    const result = eval('thisArg.func(' + args +')')
    delete thisArg.func;
    return result;
}

Bind

Function.prototype.sx_bind = function (obj, ...args) {
    obj = obj || window

    const fn = Symbol()
    obj[fn] = this
    const _this = this

    const res = function (...innerArgs) {
        console.log(this, _this)
        if (this instanceof _this) {
            this[fn] = _this
            this[fn](...[...args, ...innerArgs])
            delete this[fn]
        } else {
            obj[fn](...[...args, ...innerArgs])
            delete obj[fn]
        }
    }
    res.prototype = Object.create(this.prototype)
    return res
}

Apply

Function.prototype.myApply = function (thisArg, arr) {
    thisArg = thisArg || window;
    thisArg.func = this;
    const args = []
    for (let i = 0; i<arr.length; i++) {
        args.push('arr['+ i + ']')
    }
    const result = eval('thisArg.func(' + args +')')
    delete thisArg.func;
    return result;
}

实现柯里化

举个例子：

function add(a, b) {
    return a + b;
}

// 执行 add 函数，一次传入两个参数即可
add(1, 2) // 3

// 假设有一个 curry 函数可以做到柯里化
var addCurry = curry(add);
addCurry(1)(2) // 3

用途

我们会讲到如何写出这个 curry 函数，并且会将这个 curry 函数写的很强大，但是在编写之前，我们需要知道柯里化到底有什么用？

// 举个例子：

// 示意而已
function ajax(type, url, data) {
    var xhr = new XMLHttpRequest();
    xhr.open(type, url, true);
    xhr.send(data);
}

// 虽然 ajax 这个函数非常通用，但在重复调用的时候参数冗余
ajax('POST', 'www.test.com', "name=kevin")
ajax('POST', 'www.test2.com', "name=kevin")
ajax('POST', 'www.test3.com', "name=kevin")

// 利用 curry
var ajaxCurry = curry(ajax);

// 以 POST 类型请求数据
var post = ajaxCurry('POST');
post('www.test.com', "name=kevin");

// 以 POST 类型请求来自于 www.test.com 的数据
var postFromTest = post('www.test.com');
postFromTest("name=kevin");

第一版

// 第一版
var curry = function (fn) {
    var args = [].slice.call(arguments, 1);
    return function() {
        var newArgs = args.concat([].slice.call(arguments));
        return fn.apply(this, newArgs);
    };
};

// 我们可以这样使用：
function add(a, b) {
    return a + b;
}

var addCurry = curry(add, 1, 2);
addCurry() // 3
//或者
var addCurry = curry(add, 1);
addCurry(2) // 3
//或者
var addCurry = curry(add);
addCurry(1, 2) // 3

已经有柯里化的感觉了，但是还没有达到要求，不过我们可以把这个函数用作辅助函数，帮助我们写真正的 curry 函数。

第二版

// 第二版
function sub_curry(fn) {
    var args = [].slice.call(arguments, 1);
    return function() {
        return fn.apply(this, args.concat([].slice.call(arguments)));
    };
}

function curry(fn, length) {

    length = length || fn.length;

    var slice = Array.prototype.slice;

    return function() {
        if (arguments.length < length) {
            var combined = [fn].concat(slice.call(arguments));
            return curry(sub_curry.apply(this, combined), length - arguments.length);
        } else {
            return fn.apply(this, arguments);
        }
    };
}

更易懂的实现

function curry(fn, args) {
    length = fn.length;

    args = args || [];

    return function() {

        var _args = args.slice(0),

            arg, i;

        for (i = 0; i < arguments.length; i++) {

            arg = arguments[i];

            _args.push(arg);

        }
        if (_args.length < length) {
            return curry.call(this, fn, _args);
        }
        else {
            return fn.apply(this, _args);
        }
    }
}


var fn = curry(function(a, b, c) {
    console.log([a, b, c]);
});

fn("a", "b", "c") // ["a", "b", "c"]
fn("a", "b")("c") // ["a", "b", "c"]
fn("a")("b")("c") // ["a", "b", "c"]
fn("a")("b", "c") // ["a", "b", "c"]

第三版

// 第三版
function curry(fn, args, holes) {
    length = fn.length;

    args = args || [];

    holes = holes || [];

    return function() {

        var _args = args.slice(0),
            _holes = holes.slice(0),
            argsLen = args.length,
            holesLen = holes.length,
            arg, i, index = 0;

        for (i = 0; i < arguments.length; i++) {
            arg = arguments[i];
            // 处理类似 fn(1, _, _, 4)(_, 3) 这种情况，index 需要指向 holes 正确的下标
            if (arg === _ && holesLen) {
                index++
                if (index > holesLen) {
                    _args.push(arg);
                    _holes.push(argsLen - 1 + index - holesLen)
                }
            }
            // 处理类似 fn(1)(_) 这种情况
            else if (arg === _) {
                _args.push(arg);
                _holes.push(argsLen + i);
            }
            // 处理类似 fn(_, 2)(1) 这种情况
            else if (holesLen) {
                // fn(_, 2)(_, 3)
                if (index >= holesLen) {
                    _args.push(arg);
                }
                // fn(_, 2)(1) 用参数 1 替换占位符
                else {
                    _args.splice(_holes[index], 1, arg);
                    _holes.splice(index, 1)
                }
            }
            else {
                _args.push(arg);
            }

        }
        if (_holes.length || _args.length < length) {
            return curry.call(this, fn, _args, _holes);
        }
        else {
            return fn.apply(this, _args);
        }
    }
}

var _ = {};

var fn = curry(function(a, b, c, d, e) {
    console.log([a, b, c, d, e]);
});

// 验证 输出全部都是 [1, 2, 3, 4, 5]
fn(1, 2, 3, 4, 5);
fn(_, 2, 3, 4, 5)(1);
fn(1, _, 3, 4, 5)(2);
fn(1, _, 3)(_, 4)(2)(5);
fn(1, _, _, 4)(_, 3)(2)(5);
fn(_, 2)(_, _, 4)(1)(3)(5)

实现链式调用

function Class1() {
    console.log('初始化')
}
Class1.prototype.method = function(param) {
    console.log(param)
    return this
}
let cl = new Class1()
//由于new 在实例化的时候this会指向创建的对象， 所以this.method这个方法会在原型链中找到。
cl.method('第一次调用').method('第二次链式调用').method('第三次链式调用')

var obj = {
    a: function() {
        console.log("a");
        return this;
    },
    b: function() {
        console.log("b");
        return this;
    },
};
obj.a().b();

// 类
class Math {
    constructor(value) {
        this.hasInit = true;
        this.value = value;
        if (!value) {
            this.value = 0;
            this.hasInit = false;
        }
    }
    add() {
        let args = [...arguments]
        let initValue = this.hasInit ? this.value : args.shift()
        const value = args.reduce((prev, curv) => prev + curv, initValue)
        return new Math(value)
    }
    minus() {
        let args = [...arguments]
        let initValue = this.hasInit ? this.value : args.shift()
        const value = args.reduce((prev, curv) => prev - curv, initValue)
        return new Math(value)
    }
    mul() {
        let args = [...arguments]
        let initValue = this.hasInit ? this.value : args.shift()
        const value = args.reduce((prev, curv) => prev * curv, initValue)
        return new Math(value)
    }
    divide() {
        let args = [...arguments]
        let initValue = this.hasInit ? this.value : args.shift()
        const value = args.reduce((prev, curv) => prev / (+curv ? curv : 1), initValue)
        return new Math(value)
    }
}

let test = new Math()
const res = test.add(222, 333, 444).minus(333, 222).mul(3, 3).divide(2, 3)
console.log(res.value)

// 原型链
Number.prototype.add = function() {
    let _that = this
    _that = [...arguments].reduce((prev, curv) => prev + curv, _that)
    return _that
}
Number.prototype.minus = function() {
    let _that = this
    _that = [...arguments].reduce((prev, curv) => prev - curv, _that)
    return _that
}
Number.prototype.mul = function() {
    let _that = this
    _that = [...arguments].reduce((prev, curv) => prev * curv, _that)
    return _that
}
Number.prototype.divide = function() {
    let _that = this
    _that = [...arguments].reduce((prev, curv) => prev / (+curv ? curv : 1), _that)
    return _that
}
let num = 0;
let newNum = num.add(222, 333, 444).minus(333, 222).mul(3, 3).divide(2, 3)
console.log(newNum)

偏函数

什么是偏函数？偏函数就是将一个 n 参的函数转换成固定 x 参的函数，剩余参数（n - x）将在下次调用全部传入。举个例子：

function add(a, b, c) {
    return a + b + c
}
let partialAdd = partial(add, 1)
partialAdd(2, 3)

发现没有，其实偏函数和函数柯里化有点像，所以根据函数柯里化的实现，能够能很快写出偏函数的实现：

function partial(fn, ...args) {
    return (...arg) => {
        return fn(...args, ...arg)
    }
}

如上这个功能比较简单，现在我们希望偏函数能和柯里化一样能实现占位功能，比如：

function clg(a, b, c) {
    console.log(a, b, c)
}
let partialClg = partial(clg, '_', 2)
partialClg(1, 3)  // 依次打印：1, 2, 3

占的位其实就是 1 的位置。相当于：partial(clg, 1, 2)，然后 partialClg(3)。明白了原理，我们就来写实现：

function partial(fn, ...args) {
    return (...arg) => {
        args[index] =
        return fn(...args, ...arg)
    }
}

instanceof

const _instanceof = (target, Fn) => {
    if ((typeof target !== 'object' && typeof target !== 'function') || target === null)
    return false

    let proto = target.__proto__
    while (true) {
        if (proto === null) return false
        if (proto === Fn.prototype) return true
        proto = proto.__proto__
    }
}
function A() {}
const a = new A()
console.log(_instanceof(a, A)) // true
console.log(_instanceof(1, A)) // false

浅拷贝

const _shallowClone = target => {
    // 基本数据类型直接返回
    if (typeof target === 'object' && target !== null) {
        // 获取target 的构造体
        const constructor = target.constructor
        // 如果构造体为以下几种类型直接返回
        if (/^(Function|RegExp|Date|Map|Set)$/i.test(constructor.name)) return target
        // 判断是否是一个数组
        const cloneTarget = Array.isArray(target) ? [] : {}
        for (prop in target) {
        // 只拷贝其自身的属性
        if (target.hasOwnProperty(prop)) {
            cloneTarget[prop] = target[prop]
        }
        }
        return cloneTarget
    } else {
        return target
    }
}

深拷贝

const _completeDeepClone = (target, map = new WeakMap()) => {
    // 基本数据类型，直接返回
    if (typeof target !== 'object' || target === null) return target
    // 函数 正则 日期 ES6新对象,执行构造题，返回新的对象
    const constructor = target.constructor
    if (/^(Function|RegExp|Date|Map|Set)$/i.test(constructor.name)) return new constructor(target)
    // map标记每一个出现过的属性，避免循环引用
    if (map.get(target)) return map.get(target)
    map.set(target, true)
    const cloneTarget = Array.isArray(target) ? [] : {}
    for (prop in target) {
        if (target.hasOwnProperty(prop)) {
        cloneTarget[prop] = _completeDeepClone(target[prop], map)
        }
    }
    return cloneTarget
}

New 关键字

const _new = function(constructor) {
    // 创建一个空对象
    const obj = {}
    // 原型链挂载
    obj.__proto__ = constructor.prototype;
    // 将obj 复制给构造体中的 this，并且返回结果
    const result = constructor.call(obj)
    // 如果返回对象不为一个对象则直接返回刚才创建的对象
    return typeof result === 'object' && result !== null ? : result : obj
}

寄生组合式继承

function Parent(name) {
    this.name = name
}
Parent.prototype.getName = function () {
    return this.name
}

function Son(name, age) {
    // 这里其实就等于 this.name = name
    Parent.call(this, name)
    this.age = age
}

Son.prototype.getAge = function () {
    return this.age
}
Son.prototype.__proto__ = Object.create(Parent.prototype)

const son1 = new Son('shao', 20)

console.log(son1.getName()) // shao
console.log(son1.getAge()) // 20

节流

节流函数（throttle）就是让事件处理函数（handler）在大于等于执行周期时才能执行，周期之内不执行，即事件一直被触发，那么事件将会按每小段固定时间一次的频率执行。

function throttle(fn, delay = 300) {
    // 这里始终记得字节二面的时候，建议我不写 flag 好家伙
    let isThrottling = false
    // 核心思路，函数多次执行只有当 isThrottling 为 false 时才会进入函数体
    return function (...args) {
        if (!isThrottling) {
        isThrottling = true
        setTimeout(() => {
            isThrottling = false
            fn.apply(this, args)
        }, delay)
        }
    }
}

防抖

事件响应函数在一段时间后才执行，如果这段时间内再次调用，则重新计算执行时间

function debounce(fn, delay = 300) {
    let timer = null
    return function (...args) {
        // 每次进来都会清空定时器，所以在 delay 事件中重复执行之后执行最后一次
        clearInterval(timer)
        timer = setTimeout(() => {
        fn.apply(this, args)
        }, delay)
    }
}

once 函数

const once = (fn) => {
    let res, isFirst = true
    return function (...args) {
        if (!isFirst) return res
        res = fn.call(this, ...args)
        isFirst = false
        return res
    }
}

const f = (x) => x;
const onceF = once(f);
//=> 3
onceF(3);
//=> 3
onceF(4);

累加函数应用

function sum(...args) {
    let params = args
    const _sum = (...newArgs) => {
        if (newArgs.length === 0) {
        return params.reduce((pre, cur) => pre + cur, 0)
        } else {
        params = [...params, ...newArgs]
        return _sum
        }
    }
    return _sum
}

console.log(sum(1, 2)(3)()) // 6
console.log(sum(1)(2)(3)()) // 6
console.log(sum(1, 2, 4)(4)()) // 11

实现 repeat 方法

function repeat(fn, times, delay) {
    return async function (...args) {
        for (let i = 0; i < times; i++) {
        await new Promise((resolve, reject) => {
            setTimeout(() => {
            fn.call(this, ...args)
            resolve()
            }, delay)
        })
        }
    }
}
const repeatFn = repeat(console.log, 4, 1000)
// 函数调用四次，每次间隔 1s 打印 hello
repeatFn('hello')

ajax 与 jsonp

实现ajax

function ajax({
    url= null,
	method = 'GET',
	dataType = 'JSON',
	async = true}){
	return new Promise((resolve, reject) => {
		let xhr = new XMLHttpRequest()
		xhr.open(method, url, async)
		xhr.responseType = dataType
		xhr.onreadystatechange = () => {
			if(!/^[23]\d{2}$/.test(xhr.status)) return;
			if(xhr.readyState === 4) {
				let result = xhr.responseText
				resolve(result)
			}
		}
		xhr.onerror = (err) => {
			reject(err)
		}
		xhr.send()
	})
}

实现jsonp

const jsonp = ({ url, params, callbackName }) => {
    const generateUrl = () => {
        let dataSrc = ''
        for (let key in params) {
            if (params.hasOwnProperty(key)) {
                dataSrc += `${key}=${params[key]}&`
            }
        }
        dataSrc += `callback=${callbackName}`
        return `${url}?${dataSrc}`
    }
    return new Promise((resolve, reject) => {
        const scriptEle = document.createElement('script')
        scriptEle.src = generateUrl()
        document.body.appendChild(scriptEle)
        window[callbackName] = data => {
            resolve(data)
            document.removeChild(scriptEle)
        }
    })
}

ES6篇

实现set

class Set {
  constructor() {
    this.items = {};
    this.size = 0;
  }

  has(element) {
    return element in this.items;
  }

  add(element) {
    if(! this.has(element)) {
      this.items[element] = element;
      this.size++;
    }
    return this;
  }

  delete(element) {
    if (this.has(element)) {
      delete this.items[element];
      this.size--;
    }
    return this;
  }

  clear() {
    this.items = {}
    this.size = 0;
  }

  values() {
    let values = [];
    for(let key in this.items) {
      if(this.items.hasOwnProperty(key)) {
        values.push(key);
      }
    }
    return values;
  }
}

实现 map

function defaultToString(key) {
  if(key === null) {
    return 'NULL';
  } else if (key === undefined) {
    return 'UNDEFINED'
  } else if (Object.prototype.toString.call(key) === '[object Object]' || Object.prototype.toString.call(key) === '[object Array]') {
    return JSON.stringify(key);
  }
  return key.toString();
}

class Map {
  constructor() {
    this.items = {};
    this.size = 0;
  }

  set(key, value) {
    if(!this.has(key)) {
      this.items[defaultToString(key)] = value;
      this.size++;
    }
    return this;
  }

  get(key) {
    return this.items[defaultToString(key)];
  }

  has(key) {
    return this.items[defaultToString(key)] !== undefined;
  }

  delete(key) {
    if (this.has(key)) {
      delete this.items[key];
      this.size--;
    }
    return this;
  }

  clear() {
    this.items = {}
    this.size = 0;
  }

  keys() {
    let keys = [];
    for(let key in this.items) {
      if(this.has(key)) {
        keys.push(key)
      }
    }
    return keys;
  }

  values() {
    let values = [];
    for(let key in this.items) {
      if(this.has(key)) {
        values.push(this.items[key]);
      }
    }
    return values;
  }
}

实现es6的class

先来看看class怎么用

// 父类
class Animal{
    constructor(type){
        // 写在这里的属性都相当于给实例加的属性
        this.type = type
    }
    // 写在这里的属性都相当于es5中写在原型上的属性
    drink(){
        console.log('会喝奶');
    }
}
// 子类继承父类
class Dog extends Animal{
    // 里面内置了call 也实现了继承公有属性
    constructor(type){
        super(type);
        // 相当于 Animal.call(this,type)
    }
}
let dog = new Dog('哺乳类');
console.log(dog); // Dog { type: '哺乳类' }
console.log(dog.drink()) // 会喝奶
/*
    从执行输出了可以看到子类继承了父类原型上的公有方法以及给实例加的属性
*/

实现

// 为类依次增加方法
var _createClass = function(){
    function defineProperties(target,props){
        for(let i=0;i<props.length;i++){
            let item = props[i];
            Object.defineProperty(target,item.key,{
                // 此处可以给属性配置是否可配置、是否可检举、是否可写入
                // configurable  enumerable  writable
                // value:item.value
                ...item
            })
        }
    }
    return function(Constructor,protoProps,staticProps){
        // 源 动态 静态
        if(protoProps) defineProperties(Constructor.prototype,protoProps);
        if(staticProps) defineProperties(Constructor,staticProps);
    }
}();
// 类型检测
function _classCallCheck (instance,Constructor){
    // 检测instance 是否是 Constructor 的一个实例
    // if(!(instance instanceof Constructor)){
    //     // 如果不是通过new出来的  就抛出一个类型错误
    //     throw new TypeError('Cannot with new')
    // }
    if(!(instance instanceof Constructor)){
        // 如果实例不是父类的一个实例
        throw new Error('Cannot with new')
    }
}
// 父级
let Animal = function(){
    function Animal (type){
        // 检测实例是new出来的还是直接执行的(此处判断依据是this如果是Animal的实例那么就是通过new出来的，如果是直接执行的那么this是window)
        _classCallCheck(this,Animal);
        // 实例属性
        this.type = type;
        return {message:'I LOVE YOU'}
    }
    // target 公用方法  静态方法
    _createClass(Animal,[
        {
            key: 'drink',
            value: function(){
                console.log('会喝奶')
            }
        },
        {
            key: 'eat',
            value: function(){
                console.log('会吃面包');
            }
        }
    ],[
        {
            key: 'drinkFlag',
            value:function(){
                console.log('你才不会喝奶呢!');
            }
        },
        {
            key:'eatFlag',
            value:function(){
                console.log('你才不会喝面包呢！');
            }
        }
    ]);
    return Animal;
}()
// let animal = new Animal('哺乳类');
// console.log(animal.drink());
// console.log(animal.eat());
// console.log(Animal.drinkFlag());
// console.log(Animal.eatFlag());

// 子级继承父级的公有方法
function _inherits(subClass,parentClass){
    // 让子类继承父类的公有方法
    subClass.prototype = Object.create(parentClass.prototype,{Constructor:{value:subClass}});
    // 让子类继承父类的静态方法
    // 原理就是：subClass.__proto__ = parentClass;
    Object.setPrototypeOf(subClass,parentClass)
}

// 子级
let Dog = function(Animal){ // 把要继承的父级传进来
    _inherits(Dog,Animal);// 继承父级的公用方法
    function Dog(type){
        // 检测子类是否是通过new调用的
        _classCallCheck(this,Dog);
        let that = this;
        // 继承父级的私有方法
        let val = Animal.call(this,type);
        // 如果父级返回了一个对象类型，则把this指向为这个返回的对象
        if(typeof val === 'object'){
            that = val;
        }
        return that;
    }
    return Dog;
}(Animal)
let dog = new Dog('哺乳类');
// console.log(Dog.drinkFlag());
// console.log(Dog.eatFlag());
// console.log(dog.drink());
// console.log(dog.eat());
console.log(dog);
// console.log(Animal.prototype)

其他

Instanceof

function instance_of(Case, Constructor) {
    // 基本数据类型返回false
    // 兼容一下函数对象
    if ((typeof(Case) != 'object' && typeof(Case) != 'function') || Case == 'null') return false;
    let CaseProto = Object.getPrototypeOf(Case);
    while (true) {
        // 查到原型链顶端，仍未查到，返回false
        if (CaseProto == null) return false;
        // 找到相同的原型
        if (CaseProto === Constructor.prototype) return true;
        CaseProto = Object.getPrototypeOf(CaseProto);
    }
}

实现千分位分隔符

var str = "100000000000",
    reg = /(?=(\B\d{3})+$)/g;
str.replace(reg, ",")

把一个JSON对象的key从下划线形式（Pascal）转换到小驼峰形式（Camel）

正则表达式

function getCamelCase(str) {
    return str.replace(/_([a-z])/g, function(all, i) {
        return i.toLowerCase();
    })
}

利用数组方法

function getCamelCase(str) {
    let arr = str.split('_');
    return arr.map((item, index) => {
        if (index === 0) {
            return item;
        } else {
           return item.chartAt(0).toUpperCase() + item.slice(1);
        }
    }).join('');
}

Camel To Pascal

正则表达式

function getKebabCase(str) {
    let temp = str.replace(/[A-Z]/g, function(i) {
        return '_' + i.toLowerCase();
    })
    if (temp.slice(0,1) === '_') {
        temp = temp.slice(1);   //如果首字母是大写，执行replace时会多一个_，需要去掉
    }
    return temp;
}

利用数组方法

function getKebabCase(str) {
    let arr = str.split('');
    let result = arr.map((item) => {
        if (item.toUpperCase() === item) {
            return '_' + item.toLowerCase();
        } else {
            return item;
        }
    }).join('');
    return result;
}

实现数据类型判断函数

function myTypeof(obj) {
   return Object.prototype.toString.call(obj).slice(8, -1).toLowerCase()
}

实现数组转树

let input = [
  {
    id: 1,
    val: "学校",
    parentId: null,
  },
  {
    id: 2,
    val: "班级1",
    parentId: 1,
  },
  {
    id: 3,
    val: "班级2",
    parentId: 1,
  },
  {
    id: 4,
    val: "学生1",
    parentId: 2,
  },
  {
    id: 5,
    val: "学生2",
    parentId: 3,
  },
  {
    id: 6,
    val: "学生3",
    parentId: 3,
  },
];
function buildTree(arr, parentId, childrenArray) {
  arr.forEach((item) => {
    if (item.parentId === parentId) {
      item.children = [];
      buildTree(arr, item.id, item.children);
      childrenArray.push(item);
    }
  });
}
function arrayToTree(input, parentId) {
  const array = [];
  buildTree(input, parentId, array);
  return array.length > 0 ? (array.length > 1 ? array : array[0]) : {};
}
const obj = arrayToTree(input, null);
console.log(obj);

实现sleep函数

// promise
const sleep = time => {
  return new Promise(resolve => setTimeout(resolve,time))
}
sleep(1000).then(()=>{
  console.log(1)
})
// ES5
function sleep(callback,time) {
  if(typeof callback === 'function')
    setTimeout(callback,time)
}

function output(){
  console.log(1);
}
sleep(output,1000);

实现发布订阅模式

class EventEmitter {
    constructor() {
        this.cache = {}
    }
    on(name, fn) {
        if (this.cache[name]) {
            this.cache[name].push(fn)
        } else {
            this.cache[name] = [fn]
        }
    }
    off(name, fn) {
        let tasks = this.cache[name]
        if (tasks) {
            const index = tasks.findIndex(f => f === fn || f.callback === fn)
            if (index >= 0) {
                tasks.splice(index, 1)
            }
        }
    }
    emit(name, once = false, ...args) {
        if (this.cache[name]) {
            // 创建副本，如果回调函数内继续注册相同事件，会造成死循环
            let tasks = this.cache[name].slice()
            for (let fn of tasks) {
                fn(...args)
            }
            if (once) {
                delete this.cache[name]
            }
        }
    }
}

观察者模式

class Observerd {
    constructor() {
        // 我要看看到底有多少人在观察俺
        this.observerList = []
    }
    addObserver(observer) {
        // 添加一个观察俺的人
        this.observerList.push(observer)
    }
    notify() {
        // 我要闹点动静，所有观察者都会知道这个信息，具体怎么做就是他们自己的事情了
        this.observerList.forEach(observer => observer.update())
    }
}


class Observer {
    constructor(doSome) {
        // 观察到小白鼠有动静之后，观察者做的事情
        this.doSome = doSome
    }
    update() {
        console.log(this.doSome)
    }
}

const ob1 = new Observer('我是ob1，我观察到小白鼠有反应了，太饿了，我得去吃个饭了')
const ob2 = new Observer('我是ob2，我观察到小白鼠有反应了，我要继续工作！')
const xiaoBaiShu = new Observerd()
xiaoBaiShu.addObserver(ob1)
xiaoBaiShu.addObserver(ob2)
xiaoBaiShu.notify() // .... ....

全排列

const _permute = string => {
    const result = []
    const map = new Map()
    const dfs = (path) => {
        if (path.length === string.length) {
        result.push(path)
        return
        }
        for (let i = 0; i < string.length; i++) {
        if (map.get(string[i])) continue
        map.set(string[i], true)
        path += string[i]
        dfs(path)
        path = path.substring(0, path.length - 1)
        map.set(string[i], false)
        }
    }
    dfs('')
    return result
}
console.log(_permute('abc')) // [ 'abc', 'acb', 'bac', 'bca', 'cab', 'cba' ]

整数千分位加逗号

function toThousands(num) {
    num = num.toString()
    let result = ''
    while (num.length > 3) {
        result = ',' + num.substring(num.length - 3) + result
        num = num.substring(0, num.length - 3)
    }
    result = num + result
    return result
}
console.log(toThousands(1234567)) // 1,234,567
console.log(toThousands(123456)) // 123,456

洗牌函数

const shuffle = (arr) => {
    // 不影响原来的数组
    const result = [...arr]
    for (let i = result.length; i > 0; i--) {
        // 随机从 [0,i - 1] 产生一个 index, 将 i - 1 于 index 对应数组的值进行交换
        const index = Math.floor(Math.random() * i);
        [result[index], result[i - 1]] = [result[i - 1], result[index]]
    }
    return result
}
const arr = [1, 2, 3, 4, 5]
console.log(shuffle(arr)) // [ 3, 1, 2, 5, 4 ]
console.log(shuffle(arr)) // [ 2, 3, 5, 1, 4 ]
console.log(shuffle(arr)) // [ 4, 2, 3, 1, 5 ]
console.log(shuffle(arr)) // [ 5, 4, 2, 3, 1 ]

a == 1 && a == 2 && a == 3

如何让 a == 1 && a == 2 && a == 3 返回 true 呢

利用隐式转换会调用 valueOf

const a = {
    value: 1,
    valueOf() {
        return this.value++
    }
}
console.log(a == 1 && a == 2 && a == 3) // true

在对象 valueOf 函数不存在的情况下会调用 toString 方法

const a = {
    value: 1,
    toString() {
        return this.value++
    }
}

console.log(a == 1 && a == 2 && a == 3) // true

利用Object.defineProperty 在全局 window 上挂载一个 a 属性

let _a = 1
Object.defineProperty(window, 'a', {
    get() {
        return _a++
    }
})

console.log(a == 1 && a == 2 && a == 3)

手写LRU

/**
 * @param {number} capacity
 */
var LRUCache = function(capacity) {
    this.map = new Map()
    this.capacity = capacity
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function(key) {
    if(this.map.has(key)){
        const value = this.map.get(key)
        // 更新存储位置
        this.map.delete(key)
        this.map.set(key,value)
        return value
    }
    return - 1
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function(key, value) {
    if(this.map.has(key)){
        this.map.delete(key)
    }
    this.map.set(key,value)
    // 如果此时超过了最长可存储范围
    if(this.map.size > this.capacity){
        // 删除 map 中最久未使用的元素
        this.map.delete(this.map.keys().next().value)
    }
}

asyncPool ES6 实现

function asyncPool(poolLimit, array, iteratorFn) {
    let i = 0;
    const ret = []; // 存储所有的异步任务
    const executing = []; // 存储正在执行的异步任务
    const enqueue = function () {
        if (i === array.length) {
        return Promise.resolve();
        }
        const item = array[i++]; // 获取新的任务项
        const p = Promise.resolve().then(() => iteratorFn(item, array));
        ret.push(p);

        let r = Promise.resolve();

        // 当poolLimit值小于或等于总任务个数时，进行并发控制
        if (poolLimit <= array.length) {
        // 当任务完成后，从正在执行的任务数组中移除已完成的任务
        const e = p.then(() => executing.splice(executing.indexOf(e), 1));
        executing.push(e);
        if (executing.length >= poolLimit) {
            r = Promise.race(executing);
        }
        }

        // 正在执行任务列表 中较快的任务执行完成之后，才会从array数组中获取新的待办任务
        return r.then(() => enqueue());
    };
    return enqueue().then(() => Promise.all(ret));
}

asyncPool ES7 实现

async function asyncPool(poolLimit, array, iteratorFn) {
    const ret = []; // 存储所有的异步任务
    const executing = []; // 存储正在执行的异步任务
    for (const item of array) {
        // 调用iteratorFn函数创建异步任务
        const p = Promise.resolve().then(() => iteratorFn(item, array));
        ret.push(p); // 保存新的异步任务

        // 当poolLimit值小于或等于总任务个数时，进行并发控制
        if (poolLimit <= array.length) {
        // 当任务完成后，从正在执行的任务数组中移除已完成的任务
        const e = p.then(() => executing.splice(executing.indexOf(e), 1));
        executing.push(e); // 保存正在执行的异步任务
        if (executing.length >= poolLimit) {
            await Promise.race(executing); // 等待较快的任务执行完成
        }
        }
    }
    return Promise.all(ret);
}

# 手写题

# promise

# 实现promise

# 实现promise.all

# 实现 promise.finally

# 实现promise.allSettled

# 实现promise.race

# 来说一下如何串行执行多个Promise

# Promise.any

# Array篇

# 数组去重

# 数组扁平化

# ForEach

# Reduce

# Map

# Filter

# Every

# Some

# Find/findIndex

# IndexOf

# 实现sort

# 防抖节流

# 实现防抖函数debounce

# 实现节流函数throttle

# Object篇

# 能不能写一个完整的深拷贝

# 实现new

# 继承

# 实现object.create

# Function篇

# Call

# Bind

# Apply

# 实现柯里化

# 实现链式调用

# 偏函数

# instanceof

# 浅拷贝

# 深拷贝

# New 关键字

# 寄生组合式继承

# 节流

# 防抖

# once 函数

# 累加函数应用

# 实现 repeat 方法

# ajax 与 jsonp

# 实现ajax

# 实现jsonp

# ES6篇

# 实现set

# 实现 map

# 实现es6的class

# 其他

# Instanceof

# 实现千分位分隔符

# 把一个JSON对象的key从下划线形式（Pascal）转换到小驼峰形式（Camel）

# Camel To Pascal

# 实现数据类型判断函数

# 实现数组转树

# 实现sleep函数

# 实现发布订阅模式

# 观察者模式

# 全排列

# 整数千分位加逗号

# 洗牌函数

# a == 1 && a == 2 && a == 3

# 手写LRU

# asyncPool ES6 实现

# asyncPool ES7 实现

手写题