模拟实现 call

// 必须在Function.prototype上实现, 且不能用箭头函数
Function.prototype.myCall = function (context, ...args) {
  const ctx = context || window; // 如果没有传参，则指向window
  ctx.func = this; // ctx.func只是一个名字，可以随便取。this是被调用的函数，因为函数调用call方法，call里面的this就指向那个函数。所以ctx.func就是那个函数。
  const result = ctx.func(...args); // 调用该方法并传入参数，此时该方法的this指向ctx
  delete ctx.func; // 删除该方法，不然会在传入的对象上添加这个方法。
  return result;
};

模拟实现 apply

Function.prototype.myApply = function (context, args = []) {
  const ctx = context || window;
  ctx.func = this;
  const result = ctx.func(...args); // 跟call唯一的区别是参数不一样
  delete ctx.func;
  return result;
};

模拟实现 bind

Function.prototype.myBind = function (context, ...args) {
  const ctx = context || window;
  ctx.func = this;
  return () => {
    // 跟call的区别是不立即执行，而是返回一个函数。
    const result = ctx.func(...args);
    delete ctx.func;
    return result;
  };
};

模拟实现 new

const myNew = (Constructor, ...args) => {
  // 旧的写法，已不推荐使用
  // let obj = {};
  // obj.__proto__ = Constructor.prototype; // 不用主动指定obj.constructor
  let obj = Object.create(Constructor.prototype);
  let result = Constructor.apply(obj, args);
  // 判断构造函数的返回值类型，如果没有返回值或者返回值是值类型，返回obj这个新创建的实例（相当于this）。如果返回值时是引用类型比如return {x: 'a'}，就返回这个引用类型的对象。
  return result instanceof Object ? result : obj;
};

模拟实现 instanceof

// instanceof 用于检测构造函数的 prototype 属性是否出现在某个实例对象的原型链上
const myInstanceof = (instance, Ctor) => {
  let right = Ctor.prototype;
  let left = instance.__proto__;
  while (left != null) {
    // 找到最顶层，原型链的最顶层是null，obj.__proto__.__proto__ === null
    if (left === right) {
      return true;
    }
    left = left.__proto__;
  }
  return false;
};

// 使用 isPrototypeOf 方法。isPrototypeOf() 方法允许你检查一个对象是否存在于另一个对象的原型链上。
const myInstanceof2 = (instance, Ctor) => {
  return Ctor?.prototype?.isPrototypeOf(instance) || false;
};

实现深拷贝，可以克隆下面的对象

let a = {
  a: { b: "b" },
  c: () => {
    console.log("c");
  },
  d: [1, 2],
  e: undefined,
  i: null,
  f: 1,
  K: true,
};
a.g = a;
a.h = new Date();

const deepClone = (obj) => {
  if (obj === null) return obj;
  if (obj instanceof Date) return new Date(obj);
  if (obj instanceof RegExp) return new RegExp(obj);

  let result;
  if (Object.prototype.toString.call(obj) === "[object Object]") {
    result = {};
    for (let key in obj) {
      // 对象并且循环引用
      if (
        Object.prototype.toString.call(obj[key]) === "[object Object]" &&
        obj[key] === obj
      ) {
        result[key] = obj;
      } else {
        result[key] = deepClone(obj[key]); // 递归处理元素
      }
    }
  } else if (Object.prototype.toString.call(obj) === "[object Array]") {
    result = [];
    for (let item of obj) {
      result.push(deepClone(item)); // 递归数组元素
    }
  } else if (Object.prototype.toString.call(obj) === "[object Function]") {
    result = new Function("return " + obj.toString())();
  } else {
    result = obj; // 直接复制
  }
  return result;
};

实现节流 throttle

function throttle(method, delay) {
  let startTime = Date.now();
  return function (...args) {
    const ctx = this; // 要将this传递下去
    let currentTime = Date.now();
    if (currentTime - startTime >= delay) {
      // 靠两次运行的时间戳对比，时间没到不执行
      method.call(ctx, ...args);
      startTime = currentTime;
    }
  };
}
const handle = () => {
  console.log("test");
};
const handleThrottle = throttle(handle, 1000);

window.addEventListener("scroll", handleThrottle);

实现防抖 debounce

function debounce(method, delay) {
  let timer;
  return function () {
    const ctx = this; // 要将this传递下去
    if (timer) clearTimeout(timer); // 靠setTimout等待一定的时间执行，时间未到，清空timer重新等待
    timer = setTimeout(() => {
      method.apply(ctx, arguments);
    }, delay);
  };
}
const handle = () => {
  console.log("test");
};
const handleDebounce = debounce(handle, 1000);

window.addEventListener("scroll", handleDebounce);

实现 Promise

/*
    总结:
    1. 一个 class 类，有个constructor，参数是excutor，构造函数中执行这个excutor，excutor接受参数resolve， reject，用try catch包裹执行。
    2. 同时有4个实例属性，status, result, successCallbacks, errorCallbacks。
    3. 两个实例方法，then, catch。
    4. then里面判断状态，直接执行或者放入数组，因为要链式调用，所以返回的promise，等回调函数执行后才resolve
    5. catch中调用then
    */
class MyPromise {
  constructor(excutor) {
    this.status = "pending";
    this.result = undefined;
    // 存放成功的回调
    this.successCallbacks = [];
    // 存放失败的回调
    this.errorCallbacks = [];

    let resolve = (result) => {
      if (this.status !== "pending") return;
      this.status = "fullfilled";
      this.result = result;
      // 依次将对应的函数执行
      this.successCallbacks.forEach((fn) => fn.call(this, result));
    };

    let reject = (error) => {
      if (this.status !== "pending") return;
      this.status = "rejected";
      this.result = error;
      this.errorCallbacks.forEach((fn) => fn.call(this, error));
    };

    try {
      excutor(resolve, reject);
    } catch (e) {
      reject(e);
    }
  }

  then(success, error) {
    // 解决值穿透问题
    success = typeof success !== "function" ? (v) => v : success;
    error =
      typeof error !== "function"
        ? (err) => {
            throw err;
          }
        : error;
    // 为了保持链式调用，继续返回promise
    return new MyPromise((resolve, reject) => {
      // 如果promise的状态是 pending，需要将 onFulfilled 和 onRejected 函数存放起来，等待状态确定后，再依次将对应的函数执行
      if (this.status === "pending" && success) {
        this.successCallbacks.push((val) => {
          try {
            const res = success(val);
            res instanceof MyPromise ? res.then(resolve, reject) : resolve(res);
          } catch (e) {
            reject(e);
          }
        });
      }
      if (this.status === "pending" && error) {
        this.errorCallbacks.push((val) => {
          try {
            const res = error(val);
            res instanceof MyPromise ? res.then(resolve, reject) : resolve(res);
          } catch (e) {
            reject(e);
          }
        });
      }
      if (this.status === "fullfilled" && success) {
        try {
          const res = success(this.result);
          res instanceof MyPromise ? res.then(resolve, reject) : resolve(res);
        } catch (e) {
          reject(e);
        }
      }
      if (this.status === "rejected" && error) {
        try {
          const res = error(this.result);
          res instanceof MyPromise ? res.then(resolve, reject) : resolve(res);
        } catch (e) {
          reject(e);
        }
      }
    });
  }
  catch(error) {
    return this.then(undefined, error);
  }
}

自定义实现 Promise.all

const promiseAll = (promiseList) => {
  let result = [];
  let count = 0;
  return new Promise((resolve, reject) => {
    for (let i = 0; i < promiseList.length; i++) {
      // 不能直接promiseList[i].then()， 因为promiseList[i]可能是普通数据
      Promise.resolve(promiseList[i])
        .then((res) => {
          count++;
          result[i] = res;
          if (count === promiseList.length) {
            resolve(result);
          }
        })
        .catch((e) => {
          reject(e);
        });
    }
  });
};

实现一个带并发限制的异步调度器 Scheduler，保证同时运行的任务最多有两个

class Scheduler {
    add(promiseCreator) { ... }
    // ...
}

const timeout = (time) => new Promise(resolve => {
    setTimeout(resolve, time)
})

const scheduler = new Scheduler()
const addTask = (time, order) => {
    scheduler.add(() => timeout(time)).then(() => console.log(order))
}

addTask(1000, '1')
addTask(500, '2')
addTask(300, '3')
addTask(400, '4')

// 打印顺序是：2 3 1 4
// 一开始，1、2两个任务进入队列
// 500ms时，2完成，输出2，任务3进队
// 800ms时，3完成，输出3，任务4进队
// 1000ms时，1完成，输出1
// 1200ms时，4完成，输出4

/*
    1. add方法要返回一个promise，如果执行的数量<2，要执行promise，否则放入list
    2. add方法的resolve，要在promise执行之后，所以要将resolve传下去
    3. 执行方法中执行promise，控制count，并检查list中是否还有未执行的promise
*/
class Scheduler {
  constructor() {
    this.max = 2;
    this.count = 0;
    this.list = [];
  }
  add(promise) {
    return new Promise((resolve) => {
      promise.end = resolve;
      if (this.count < this.max) {
        this.excute(promise);
      } else {
        this.list.push(promise);
      }
    });
  }
  async excute(promise) {
    this.count++;
    await promise();
    promise.end();
    this.count--;
    if (this.list.length) {
      this.excute(this.list.shift());
    }
  }
}

实现一个对象的 flatten 方法，将层级嵌套的属性拉平

const obj = {
  a: {
    b: 1,
    c: 2,
    d: { e: 5 },
  },
  b: [1, 3, { a: 2, b: 3 }],
  c: 3,
};

flatten(obj);
// 结果返回如下
// {
//     'a.b': 1,
//     'a.c': 2,
//     'a.d.e': 5,
//     'b[0]': 1,
//     'b[1]': 3,
//     'b[2].a': 2,
//     'b[2].b': 3
//     c: 3
// }

const flatten = (obj) => {
  let result = {};
  const dfs = (current, prefix) => {
    if (Object.prototype.toString.call(current) === "[object Object]") {
      for (const key in current) {
        // 对象的前缀
        result = dfs(current[key], `${prefix}${prefix ? "." : ""}${key}`);
      }
    } else if (Object.prototype.toString.call(current) === "[object Array]") {
      current.forEach((item, index) => {
        // 数组的前缀
        result = dfs(item, `${prefix}[${index}]`);
      });
    } else {
      result[prefix] = current;
    }
    return result;
  };

  return dfs(obj, "");
};

实现一个方法，将平级的对象转成层级嵌套对象

const obj = {
  "a.b": 1,
  "a.c": 2,
  "a.d.e": 5,
  "a.d.f": 6,
  c: 3,
};
convert(obj);
// 结果返回如下
// {
//     a: {
//         b: 1,
//         c: 2,
//         d: {
//             e: 5,
//             f: 6
//         }
//     },
//     c: 3
// }

const convert = (obj) => {
  let result = {};
  const keys = Object.keys(obj);
  keys.forEach((key) => {
    const arr = key.split(".");
    // 嵌套的多级
    if (arr.length > 1) {
      arr.reduce((prev, next, index) => {
        // 如果目标对象不存在该子级，应该给该子级赋值。赋值为最终值或者新的对象
        if (!prev[next]) {
          if (index === arr.length - 1) {
            prev[next] = obj[key];
          } else {
            prev[next] = {};
          }
        }
        return prev[next];
      }, result);
    } else {
      // 只有一级
      result[key] = obj[key];
    }
  });

  return result;
};

实现一个数组的 flatten 方法

const flatten = (arr) => {
  let result = [];
  for (let item of arr) {
    if (Array.isArray(item)) {
      result = result.concat(flatten(item));
    } else {
      result.push(item);
    }
  }
  return result;
};
// 或者
const myFlattern = (arr, result = []) => {
  arr.forEach((item) => {
    if (Array.isArray(item)) {
      myFlattern(item, result);
    } else {
      result.push(item);
    }
  });
  return result;
};

实现一个数组的 reduce 方法

Array.prototype.myReduce = function (cb, initValue) {
  const array = this;
  let acc = initValue || array[0];
  const startIndex = initValue ? 0 : 1;

  for (let i = startIndex; i < array.length; i++) {
    const cur = array[i];
    acc = cb(acc, cur, i, array);
  }
  return acc;
};

实现一个 curry 函数，可以满足下面的逻辑

const sum = (a, b, c) => a + b + c;
const fn = curry(sum);

fn(1, 2, 3); // 6
fn(1, 2)(3); // 6
fn(1)(2, 3); // 6
fn(1)(2)(3); // 6

const curry = (fn) => {
  /*
        思路解析：
        1. 接受一个原函数，返回一个柯里化后的函数
        2. 如果柯里化后的函数接受的参数个数大于等于原函数的参数个数，直接调用原函数，返回结果
        3. 否则的话，说明参数还未接受完毕，返回一个函数，继续接受新的参数，旧参数+新的参数 去递归
    */
  const nest = (...args) => {
    if (args.length >= fn.length) {
      return fn(...args);
    } else {
      return (...restArgs) => {
        return nest(...[...args, ...restArgs]);
      };
    }
  };
  return nest;
};

实现一个函数 sum，接受多个参数，sum(a)(b)…(n)()，返回 a 到 n 的和

const sum = (a) => {
  // 返回一个函数，如果没有参数就返回当前值，有参数就递归
  return (x) => {
    if (x) {
      return sum(a + x);
    } else {
      return a;
    }
  };
};

实现一个函数 sum，接受多个参数，sum(a)(b)…(n).count()，调用 count()返回 a 到 n 的和

const sum = (a) => {
  let args = [a];

  const add = (x) => {
    args.push(x);
    return add;
  };

  add.count = () => {
    return args.reduce((total, next) => {
      return total + next;
    }, 0);
  };

  return add;
};

实现一个 compose 函数，它接受任意多个函数作为参数（这些函数都只接受一个参数），然后 compose 返回的也是一个函数，达到以下的效果

const add1 = (x) => x + 1;
const mul3 = (x) => x * 3;
const div2 = (x) => x / 2;
div2(mul3(add1(add1(0)))); // => 3

const operate = compose(div2, mul3, add1, add1);
operate(0); // => 3 相当于div2(mul3(add1(add1(0))))
operate(2); // => 6 相当于div2(mul3(add1(add1(2))))
// compose(f,g)(x) === f(g(x))
// compose(f,g,m)(x) === f(g(m(x)))
// compose(f,g,m)(x) === f(g(m(x)))
// compose(f,g,m,n)(x) === f(g(m(n(x))))

const compose = (...args) => {
  return (x) => {
    return args.reduceRight((prev, next) => {
      // reduceRight，从右向左执行。不能用args.reverse().reduce，会改变args参数，每次执行会不一样
      return next(prev);
    }, x);
  };
};
const compose = (...args) => {
  const temp = args.reverse();
  return (x) => {
    return temp.reduce((prev, next) => {
      return next(prev);
    }, x);
  };
};

setTimeout 模拟实现 setTnterval(带清除定时器的版本)

function mySetInterval(fn, delay) {
  let timer;
  const interval = () => {
    timer = setTimeout(() => {
      fn(); // setInterval第一次执行的时候，就是延迟执行，所以fn放在里面
      interval();
    }, delay);
  };
  interval();
  return () => clearTimeout(timer);
}

let cancel = mySetInterval(() => {
  console.log(2);
}, 1000);

cancel();

实现发布订阅模式

class EventBus {
  constructor() {
    this.map = new Map();
  }
  on = (topic, fn) => {
    if (this.map.has(topic)) {
      this.map.get(topic).push(fn);
    } else {
      this.map.set(topic, [fn]);
    }
  };
  off = (topic, fn) => {
    if (this.map.has(topic)) {
      const list = this.map.get(topic);
      if (fn) {
        const index = list.findIndex((item) => item === fn);
        list.splice(index, 1);
      } else {
        this.map.delete(topic);
      }
    }
  };
  trigger = (topic) => {
    if (this.map.has(topic)) {
      this.map.get(topic).forEach((fn) => {
        fn();
      });
    }
  };
}

继承和原型链

// ES5组合寄生继承
var Father = function () {
  this.name = "爸爸";
};

var Son = function () {
  Father.call(this);
  this.name = "儿子";
};
Son.prototype = Object.create(Father.prototype);
Son.prototype.constructor = Son;
var son = new Son();

// ES6继承
class Father {
  constructor() {
    this.name = "爸爸";
  }
}
class Son extends Father {
  constructor() {
    super();
    this.name = "儿子";
  }
}
var son = new Son();

// 实例的，父类的prototype.__proto__直接指向Object.prototype
console.log(son.__proto__ === Son.prototype);
console.log(Son.prototype.__proto__ === Father.prototype);
console.log(Father.prototype.__proto__ === Object.prototype);
console.log(Object.prototype.__proto__ === null);

// 类的，类的__proto__属性指向父类，没有父类或者ES5中指向Function.prototype
console.log(Son.__proto__ === Father); // ES5指向Function.prototype
console.log(Father.__proto__ === Function.prototype);
console.log(Function.prototype.__proto__ === Object.prototype);
console.log(Object.prototype.__proto__ === null);

变量提升相关，问输出

/*
    1. var变量声明 和 函数声明都会变量提升
    2. 函数声明是整体提升，优先级高于var声明，且直接赋值
    3. 具体的执行是什么取决于赋值是什么。
*/
function Foo() {
  log = function () {
    console.log(1);
  };
  return this;
}
Foo.log = function () {
  console.log(2);
};
Foo.prototype.log = function () {
  console.log(3);
};
var log = function () {
  console.log(4);
};
function log() {
  console.log(5);
}

Foo.log(); // 2
log(); // 4
Foo().log(); // 1
log(); // 1
new Foo.log(); // 2
new Foo().log(); // 3

this 指向问题，问输出

var x = 0;
var obj = {
  x: 10,
  bar() {
    var x = 20;
    console.log(this.x);
  },
};

obj.bar(); // 10
var foo = obj.bar;
foo(); // 0
obj.bar.call(window); // 0
obj.bar.call(obj); // 10
foo.call(obj); // 10

事件循环相关，问输出

console.log(1);
setTimeout(() => {
  console.log(2);
}, 1000);
setTimeout(() => {
  var p = new Promise((resolve, reject) => {
    console.log(3);
    resolve();
    console.log(3.5); // resolve 后面的代码跟前面的代码一样，都在同一个时间执行
  }).then(() => {
    console.log(4);
  });
  Promise.resolve().then(() => {
    console.log(5);
  });
}, 0);
setTimeout(() => {
  Promise.resolve().then(() => {
    console.log(6);
  });
}, 0);
new Promise((resolve, reject) => {
  console.log(7);
  resolve();
}).then(() => {
  console.log(8);
});
Promise.resolve().then(() => {
  console.log(9);
});
async function async1() {
  await async2();
  console.log(10);
}
async function async2() {
  await async3();
  console.log(11);
}
async function async3() {
  console.log(12);
}
async1();
console.log(13);

// 1, 7, 12, 13, 8, 9, 11, 10, 3, 3.5, 4, 5, 6, 2

promise then 的输出

// 当then 返回promise 的时候，需将返回的promise 丢进微队列，并且当它完成，才能让包裹他的promise 变fufilled 状态，才能将输出res 的promise 丢进微任务。
// 所以一开始微任务队列里面是[0, 1]，输出0后，队列变成[1, promise.resolve(4).then(()=>完成p0], 输出1后，变成[promise.resolve(4).then(()=>完成p0, 2]，接下来执行第一个微任务后，队列变成[2, ()=>完成p0], 然后输出2，队列变成[()=>完成p0, 3], 然后，队列变成[3, 4]。
Promise.resolve()
  .then(() => {
    console.log(0);
    return Promise.resolve(4); // 重点在这里
  })
  .then((res) => {
    console.log(res);
  });

Promise.resolve()
  .then(() => {
    console.log(1);
  })
  .then(() => {
    console.log(2);
  })
  .then(() => {
    console.log(3);
  })
  .then(() => {
    console.log(5);
  })
  .then(() => {
    console.log(6);
  });

// 0 1 2 3 4 5 6

用 React hook 实现一个计数器组件，每秒自动加 1

fucntion Counter() {
  const [count, setCount] = useState(0);
  useEffect(() => {
    const timer = setInterval(() => {
      setCount(count => count+1)
    }, 1000)
  },[])
  return () => {
    clearInterval(timer)
  }
}

如何实现一个自定义 hook，useEventListener，给某个 dom 元素添加特定的 event 事件

function useEventListener(eventName, handler, dom) {
  const savedHandler = useRef();

  useEffect(() => {
    savedHandler.current = handler;
  }, [handler]);

  useEffect(() => {
    const eventListener = (event) => savedHandler.current(event);
    dom.addEventLister(eventName, eventListener);
    return () => {
      dom.removeEventListener(eventName, eventListener);
    };
  }, [eventName, dom]);
}

Proxy 用法

var target = {};
var proxy = new Proxy(target, {
  set(target, key, value, receiver) {
    return Reflect.set(target, key, value, receiver);
  },
  get(target, key, receiver) {
    return Reflect.get(target, key, receiver);
  },
});

实现一个自定义 webpack plugin

// console-log-on-build-webpack-plugin.js

const pluginName = "ConsoleLogOnBuildWebpackPlugin";

class ConsoleLogOnBuildWebpackPlugin {
  constructor(options = {}) {
    this.options = options;
  }

  // Compiler 对象包含了 Webpack 环境所有的的配置信息，包含 options，loaders，plugins 这些信息，这个对象在 Webpack 启动时候被实例化，它是全局唯一的
  // Compilation 对象包含了当前的模块资源、编译生成资源、变化的文件等。当 Webpack 以开发模式运行时，每当检测到一个文件变化，一次新的 Compilation 将被创建。
  apply(compiler) {
    // tap 或者 tapAsync 可以用来同步或者异步执行
    compiler.hooks.run.tap(pluginName, (compiler) => {
      console.log("webpack 构建过程开始！");
    });

    compiler.hooks.compile.tap(pluginName, (compilationParams) => {
      console.log("程序即将创建compilation对象！");
    });

    compiler.hooks.compilation.tap(pluginName, (compilation) => {
      console.log("compilation对象创建完成！");
      // 现在可以通过 compilation 对象绑定各种compilation钩子
      compilation.hooks.optimize.tap(pluginName, () => {
        console.log("资源已经优化完毕。");
      });
    });

    compiler.hooks.make.tap(pluginName, (compilation) => {
      console.log("compilation实例启动对代码的编译和构建!");
    });

    compiler.hooks.emit.tap(pluginName, (compilation) => {
      console.log(
        "所有打包生成的文件内容已经在内存中按照相应的数据结构处理完毕,下一步会将文件内容输出到output目录!"
      );
    });

    compiler.hooks.done.tap(pluginName, (stats) => {
      console.log("编译后的文件已经输出到output目录，编译完成");
    });
  }
}

module.exports = ConsoleLogOnBuildWebpackPlugin;

实现一个自定义 webpack loader

// my-sass-loader.js

// loader-utils是专门用于自定义loader时的一些工具函数
const { getOptions } = require("loader-utils");
const sass = require("sass");

module.exports = function (source) {
  const options = getOptions(this); // getOptions用于获取配置
  const sassOptions = options.sassOptions || {};

  const result = sass.compile({
    data: source,
    ...sassOptions,
  });

  return result.css;
};

冒泡排序

// 数组中有 n 个数，比较每相邻两个数，如果前者大于后者，就把两个数交换位置；这样一来，第一轮就可以选出一个最大的数放在最后面；那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。
const bubbleSort = (arr) => {
  const max = arr.length - 1; // 外层最多循环的次数
  for (let i = 0; i < max; i++) {
    for (let j = 0; j < max - i; j++) {
      // 内层循环最多循环max-i次，因为后面的元素已经有序了
      if (arr[j] > arr[j + 1]) {
        // 一定要注意是相邻元素比较，不能拿 arr[i] 去依次比较，那样相当于将最小元素换到0位
        let temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
};

选择排序

// 数组中有 n 个数，用数组的第一个元素，依次比较其他所有元素，找到最小的元素，就把两个数交换位置；这样第一轮就可以选出一个最小的数；那么经过 n-1（数组的 length - 1） 轮，就完成了所有数的排序。
const selectSort = (arr) => {
  const max = arr.length - 1; // 外层最多循环的次数
  for (let i = 0; i < max; i++) {
    let min = arr[i]; // 记录最小元素
    let minIndex = i; // 记录最小元素的位置
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[j] < min) {
        min = arr[j];
        minIndex = j;
      }
    }
    const temp = arr[i];
    arr[i] = min;
    arr[minIndex] = temp;
  }
  return arr;
};

插入排序

// 对于一个数组，把第二个数插入到前面或者不动，这样前两个数就相当于是有序数组。再取第三个数，插入到前面的有序数列中，从后往前比较。
const insertSort = (arr) => {
  for (let i = 1; i < arr.length; i++) {
    let current = arr[i];
    let preIndex = i - 1;
    while (preIndex >= 0 && current < arr[preIndex]) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }

  return arr;
};

快速排序

// 快速排序就是利用二分法和递归的思想，找一个基准点，比如第一个元素，将数组分成两个数组，分别是小于和大于这个基准点的两个数组。然后对这两个数组采用同样的方式递归
const quickSort = (arr) => {
  if (arr.length <= 1) return arr;
  const temp = arr[0];
  let left = [];
  let right = [];

  for (let i = 1; i < arr.length; i++) {
    if (arr[i] >= temp) {
      right.push(arr[i]);
    } else {
      left.push(arr[i]);
    }
  }

  return [...quickSort(left), temp, ...quickSort(right)];
};

实现一个双向链表，包含节点的添加，插入，删除

/**
 * const l = new LinkList();
 * l.append(1);
 * l.insert(0, 0)
 * l.insert(2, 3)
 * l.insert(2, 2)
 * l.removeAt(0)
 * l.removeAt(1)
 * l.removeAt(1)
 * */
class Node {
  constructor(data) {
    this.data = data;
    this.prev = null; // 前驱指针
    this.next = null; // 后继指针
  }
}

class LinkList {
  constructor() {
    this.length = 0;
    this.head = null; // 头指针
    this.end = null; // 尾指针
  }
  append(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
      this.end = node;
    } else {
      node.prev = this.end;
      this.end.next = node;
      this.end = node;
    }
    this.length++;
    return this;
  }
  insert(position, data) {
    if (
      position === null ||
      position === undefined ||
      position < 0 ||
      position > this.length
    ) {
      return;
    }

    const node = new Node(data);
    if (position === 0) {
      // 第一个位置插入
      if (!this.head) {
        this.head = node;
        this.end = node;
      } else {
        // 用新的node替换head
        node.next = this.head;
        this.head.prev = node;
        this.head = node;
      }
    } else if (position === this.length) {
      // 最后一个位置插入
      this.end.next = node;
      node.prev = this.end;
      this.end = node;
    } else {
      // 中间位置插入
      let index = 0;
      let previous = null;
      let current = this.head;
      // 从头遍历
      while (index < position) {
        index++;
        previous = current;
        current = current.next;
      }
      // 交换元素
      node.next = current;
      node.prev = previous;
      previous.next = node;
      current.prev = node;
    }
    this.length++;
    return node;
  }
  removeAt(position) {
    if (
      position === null ||
      position === undefined ||
      position < 0 ||
      position > this.length
    ) {
      return;
    }
    let current = this.head;
    if (position === 0) {
      // 删除第一个
      if (this.length === 1) {
        this.head = null;
        this.end = null;
      } else {
        this.head = this.head.next;
        this.head.prev = null;
      }
    } else if (position === this.length - 1) {
      // 删除最后一个
      current = this.end;
      this.end = this.end.prev;
      this.end.next = null;
    } else {
      // 删除中间的
      let index = 0;
      let previous = null;
      while (index < position) {
        index++;
        previous = current;
        current = current.next;
      }
      previous.next = current.next;
      current.next.prev = previous;
    }
    this.length--;
    return current;
  }
}

实现一个二叉搜索树，左边数据全部小于右边，包含前中后序遍历和插入节点

class Node {
  constructor(data) {
    this.data = data;
    this.left = null;
    this.right = null;
  }
}

class Tree {
  constructor() {
    this.root = null;
  }

  insert(data) {
    const node = new Node(data);
    if (!this.root) {
      this.root = node;
    } else {
      this.insertToNode(node, this.root);
    }
  }

  insertToNode(node, root) {
    if (node.data > root.data) {
      if (!root.right) {
        root.right = node;
      } else {
        this.insertToNode(node, root.right);
      }
    } else {
      if (!root.left) {
        root.left = node;
      } else {
        this.insertToNode(node, root.left);
      }
    }
  }

  // 前序遍历。前序、中序、后序遍历是对二叉树进行深度优先遍历的几种方式。所以需要递归。
  preOrder() {
    let result = [];
    this.preOrderNode(this.root, result);
    return result;
  }
  preOrderNode(node, result) {
    if (!node) return result;
    result.push(node.data);
    this.preOrderNode(node.left, result);
    this.preOrderNode(node.right, result);
  }

  // 中序遍历
  inOrder() {
    let result = [];
    this.inOrderNode(this.root, result);
    return result;
  }
  inOrderNode(node, result) {
    if (!node) return result;
    this.preOrderNode(node.left, result);
    result.push(node.data);
    this.preOrderNode(node.right, result);
  }

  // 后序遍历
  postOrder() {
    let result = [];
    this.postOrderNode(this.root, result);
    return result;
  }
  postOrderNode(node, result) {
    if (!node) return result;
    this.preOrderNode(node.left, result);
    this.preOrderNode(node.right, result);
    result.push(node.data);
  }
}

双指针

双指针的思想

左右指针

给定一个长度为 n 的整数数组  height ，代表  n  条垂线，每个元素代表一条垂线的高度。找出其中的两条线，使得它们与  x  轴共同构成的容器可以容纳最多的水。返回容器可以储存的最大水量。

// 两条线之间的容量，取决于x轴宽度乘以最低的线。
var maxArea = function (height) {
  if (height.length <= 1) return 0;

  let i = 0;
  let j = height.length - 1;
  let max = 0;
  while (j > i) {
    if (height[j] > height[i]) {
      temp = (j - i) * height[i];
      i++; // 移动低的线
    } else {
      temp = (j - i) * height[j];
      j--;
    }

    if (temp > max) {
      max = temp;
    }
  }
  return max;
};

中心扩散指针

给你一个字符串 s，找到 s 中最长的回文子串。如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。

var longestPalindrome = function (s) {
  if (s.length <= 1) return s;

  let result = "";
  for (let i = 0; i < s.length; i++) {
    handler(i, i);
    handler(i, i + 1);
  }

  function handler(left, right) {
    // 满足条件时就一直往两边扩散，不满足时跳出循环
    while (
      left <= right &&
      left >= 0 &&
      right <= s.length - 1 &&
      s.charAt(left) === s.charAt(right)
    ) {
      left--;
      right++;
    }
    // 跳出循环时正好不满足条件
    const str = s.substring(left + 1, right);
    result = str.length > result.length ? str : result;
  }

  return result;
};

快慢指针（滑动窗口）

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。

var lengthOfLongestSubstring = function (s) {
  // 滑动窗口，窗口用数组存储，左侧指针固定，移动右侧指针（往数组中添加），当右指针的字符在数组中存在时，左侧指针移动到窗口内存在的那个字符处。这样再取窗口长度的最大值即可
  if (s.length <= 1) return s.length;
  let temp = [];
  const arr = s.split("");
  let max = 0;
  for (let i = 0; i < arr.length; i++) {
    if (!temp.includes(arr[i])) {
      // 往窗口中添加
      temp.push(arr[i]);
    } else {
      max = temp.length > max ? temp.length : max; // 当遇见重复字符时，记录窗口的长度
      while (temp.includes(arr[i])) {
        // 从窗口中删除
        temp.shift();
      }
      temp.push(arr[i]);
    }
  }
  return temp.length > max ? temp.length : max;
};

深度优先搜索算法 DFS，也叫回溯，递归

给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径，这条路径上所有节点值相加等于目标和 targetSum 。如果存在，返回 true ；否则，返回 false 。

var hasPathSum = function (root, targetSum) {
  const result = [];

  // 深度优先搜索遍历，每遍历一个节点，累加其值。如果当前节点是叶子节点，则将该路径值添加到结果集。不是叶子节点，继续遍历子节点。
  var dfs = function (root, total) {
    if (root) {
      total += root.val; // 值累加
      if (!root.left && !root.right) {
        result.push(total); // 添加到结果集
      } else {
        dfs(root.left, total);
        dfs(root.right, total);
      }
    }
  };

  dfs(root, 0);
  return result.includes(targetSum);
};

广度优先搜索算法 BFS

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。（即逐层地，从左到右访问所有节点）。

var levelOrder = function (root) {
  // BFS 广度优先搜索，借助队列。队列存储每一层的节点，依次出队列，记录在数组中，并将该节点的子节点入队列，开始下一层。
  const result = [];
  if (root === null) return result;

  const queue = [];
  queue.push(root);

  while (queue.length) {
    result.push([]); // 每层开始前，push个空数组，用于下面记录
    const size = queue.length;
    for (let i = 0; i < size; i++) {
      const node = queue.shift(); // 从头开始出队列
      result[result.length - 1].push(node.val); // 记录该层数据
      if (node.left) queue.push(node.left); // 子节点入队列
      if (node.right) queue.push(node.right);
    }
  }

  return result;
};

动态规划

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

var climbStairs = function (n) {
  const dp = [];
  dp[0] = 1; // 确定好起始点 0 和 1 的值
  dp[1] = 1;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // 根据公式，循环得出每一个位置的值
  }
  return dp[n]; // 取特定位置的值
};

一个机器人位于一个 m x n  网格的左上角，机器人每次只能向下或者向右移动一步，机器人试图达到网格的右下角。问总共有多少条不同的路径？

var uniquePaths = function (m, n) {
  // 构造一个矩阵，矩阵中的数字代表走到这个格子的步数。
  const f = new Array(m).fill(0).map(() => new Array(n).fill(0));
  // 对于第一行 dp[0][j]，或者第一列 dp[i][0]，由于都是在边界，所以只能为 1
  for (let i = 0; i < m; i++) {
    f[i][0] = 1;
  }
  for (let j = 0; j < n; j++) {
    f[0][j] = 1;
  }
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      f[i][j] = f[i - 1][j] + f[i][j - 1]; // 动态方程
    }
  }
  return f[m - 1][n - 1];
};