尾递归

/** 当一个函数直接返回另一个函数调用的结果时，我们说这个函数是尾递归的  */

// 非尾递归版本
function factorial(n) {
  if (n === 1) {
    return 1;
  }
  return n * factorial(n - 1);
}

// 尾递归版本
function factorial(n, acc = 1) {
  if (n === 1) {
    return acc;
  }
  return factorial(n - 1, n * acc);
}

手写 instanceof

function _instanceof(obj, constructor) {
  // 获取对象的原型
  let proto = obj.__proto__;
  // 获取构造函数的原型
  let prototype = constructor.prototype;
  // 循环查找原型链
  while (proto) {
    if (proto === prototype) {
      // 如果找到相同的原型，则返回true
      return true;
    }
    
    proto = proto.__proto__; 
  }
  // 如果原型链末端都没有找到，则返回false
  return false;
}

手写 new

function _new () {
  // 1. 创建一个空对象
  const obj = {};
  
  // 获取构造函数
  const con = [].shift().call(arguments);
  
  // 2. 新对象的隐式原型 __proto__ 链接到构造函数的显式原型 prototype
  obj.__proto__ = con.prototype;

  // 3.构造函数内部的 this 绑定到这个新创建的对象 执行构造函数
  const result = con.apply(obj, arguments);

  // 4.如果构造函数没有返回非空对象，则返回创建的新对象
  return result instanceof Object ?  result : obj;
}

手写 call

Function.prototype._call = function (ctx = window) {
	ctx._fn = this
	const args = Array.from(arguments).slice(1)
	const res = ctx._fn(...args)
	delete ctx._fn
	return res
}

手写 bind

Function.prototype._bind = function(thisArg, ...args){
  let that = this
  return function () {
    return that.call(thisArg, ...args)
  }
}

深拷贝

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

  let newObj = Array.isArray(obj) ? [] : {};

  for (let key in obj) {
    // 用来检测属性是否为对象的自有属性
    if (obj.hasOwnProperty(key)) {
      newObj[key] = deepCopy(obj[key]);
    }
  }

  return newObj;
}


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

快速排序

function quickSort(arr = []) {
  const len = arr.length;

  if (arr.length <= 1) {
    return arr;
  }

  const pivotIndex = Math.floor(len / 2);
  const pivot = arr[pivotIndex];
  const less = [];
  const greater = [];

  for (let i = 0; i < len; i++) {
    if (i === pivotIndex) {
      continue;
    }

    if (arr[i] < pivot) {
      less.push(arr[i]);
    } else {
      greater.push(arr[i]);
    }
  }

  return [...quickSort(less), pivot, ...quickSort(greater)];
}

数组转树

function array2Tree(arr = []) {
  const mapping = {};

  arr.forEach((it) => (mapping[it?.id] = it));

  const roots = [];

  arr.forEach((it) => {
    const parent = mapping[it.pid];
    if (parent) {
      (parent.children || (parent.children = [])).push(it);
    } else {
      roots.push(it);
    }
  });

  return roots;
}

var list = [
  { id: 1, pid: 0, name: "1" },
  { id: 2, pid: 1, name: "1-1" },
  { id: 3, pid: 1, name: "1-2" },
  { id: 4, pid: 2, name: "1-1-1" },
];

冒泡排序

function bubbleSort(arr) {
  let len = arr.length;
  let temp;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - 1 - i; j++) {
      if (arr[j] > arr[j + 1]) {
        temp = arr[j + 1];
        arr[j + 1] = arr[j];
        arr[j] = temp;
      }
    }
  }

  return arr;
}

function bubbleSort() {
  let low = 0;
  let high = arr.length - 1;
  let tmp;
  let j;

  while (low < high) {
    // 正向冒泡,找到最大者
    for (j = low; j < high; ++j)
      if (arr[j] > arr[j + 1]) {
        tmp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = tmp;
      }
    // 修改high值, 前移一位
    --high;

    // 反向冒泡,找到最小者
    for (j = high; j > low; --j)
      if (arr[j] < arr[j - 1]) {
        tmp = arr[j];
        arr[j] = arr[j - 1];
        arr[j - 1] = tmp;
      }
    // 修改low值,后移一位
    ++low;
  }

  return arr;
}

手写一个 redux

function createStore(initState, reducer) {
  let state = initState
  let listeners = []

  function subscribe(listener) {
    listeners.push(listener)
  }

  function dispatch(action) {
    listeners.forEach(it => it())

    state = reducer(state, action())
  }


  function getState() {
    return state
  }

  return {
    subscribe,
    dispatch,
    getState
  }

}

const initState = {
  count: 1
}

function reducer(state, action) {
  switch (action.type) {
    case 'ADD':
      return {
        ...state,
        count: state.count + 1
      }
    default:
      return state
  }
}

const store = createStore(initState, reducer)

const ADD = 'ADD'

function add() {
  return {
    type: ADD
  }
}

store.dispatch(add())

回文数

function isPlalindrome(input = "") {
  if (typeof input !== "string") return false;
  return input.split("").reverse().join("") === input;
}

全排列

function permute(arr, memo = []) {  
  let result = [];  

  // 如果数组为空，则当前memo是一个有效的全排列  
  if (arr.length === 0) {  
    result.push(memo);
  } else {  
    for (let i = 0; i < arr.length; i++) {  
      let current = arr.slice(); // 复制当前数组  
      let next = current.splice(i, 1); // 移除当前元素  
      let remaining = permute(current, memo.concat(next)); // 递归处理剩余元素  
      result = result.concat(remaining); // 合并结果  
    }  
  }  

  return result;  
} 


function permute(nums = []) {
  let len = nums.length;
  const result = [];
  const visited = new Array(len).fill(false);

  const dfs = (nums, len, depth, path, visited) => {
    // 遍历到叶子结点了，可以返回了
    if (depth === len) {
      result.push([...path]);
    }

    for (let i = 0; i < len; i++) {
      // 如果没遍历过
      if (!visited[i]) {
        // 压入 path 数组，然后是否遍历过的数组此下标处变为 true
        path.push(nums[i]);
        visited[i] = true;
        // 继续 dfs，直到最后一层
        dfs(nums, len, depth + 1, path, visited);
        // 进行回溯，还原，以便下一次使用
        visited[i] = false;
        path.pop();
      }
    }
  };

  dfs(nums, len, 0, [], visited);
  return result;
}

翻转二叉树

function invertTree(root) {
  if (root === null) {
    return null;
  }
  const left = invertTree(root.left);
  const right = invertTree(root.right);
  root.left = right;
  root.right = left;
  return root;
}

洗牌算法

[1, 2, 3, 4, 5, 6].sort(function () {
  return 0.5 - Math.random();
});

function shuffle(arr) {
  let length = arr.length;
  let temp;
  let random;

  while (0 != length) {
    random = Math.floor(Math.random() * length);
    length--;
    // swap
    temp = arr[length];
    arr[length] = arr[random];
    arr[random] = temp;
  }

  return arr;
}

function shuffle(arr) {
  let len = arr.length;
  let random;

  while (0 != len) {
    random = (Math.random() * len--) >>> 0; // 无符号右移位运算符向下取整
    [arr[len], arr[random]] = [arr[random], arr[len]]; // ES6的结构赋值实现变量互换
  }

  return arr;
}

EventBus

class EventBus {

  constructor () {
    this._eq = {}
  }

  on (ev, cb) {
    this._eq?.[ev] ? this._eq?.[ev].push(cb) : this._eq?.[ev] = [cb]
  }

  emit (ev, ...args) {
    this._eq?.[ev].forEach(cb => cb?.(...args))
  }

  off (ev) {
    delete this._eq?.[ev]
  }

  once (ev, cb) {
    this.on(ev, (...args) => {
      cb(...args)
      this.off(ev)
    })
  }
}

最短编辑距离问题

function minEditDistance(source, target) {  
  const m = source.length;
  const n = target.length;
  const dp = Array(m + 1).fill(0).map(() => Array(n + 1).fill(0));

  // 初始化第一行和第一列  
  for (let i = 0; i <= m; i++) {
    dp[i][0] = i;  
  }

  for (let j = 0; j <= n; j++) {  
    dp[0][j] = j;  
  }  

  // 动态规划计算最短编辑距离  
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {  
      const cost = (source[i - 1] === target[j - 1]) ? 0 : 1;  

      dp[i][j] = Math.min(  
        dp[i - 1][j] + 1,    // 删除  
        dp[i][j - 1] + 1,    // 插入  
        dp[i - 1][j - 1] + cost // 替换  
      );  
    }  
  }  
  
  return dp[m][n];  
}

路径总和

function hasPathSum(root, targetSum) {
  if (!root) {
    return false;
  }

  if (!root.left && !root.right) {
    return root.val === targetSum;
  }

  return (
    hasPathSum(root.left, targetSum - root.val) ||
    hasPathSum(root.right, targetSum - root.val)
  );
}

防抖

function debounce(fn, wait) {
  let timer = null;

  return function () {
    clearTimeout(timer);

    timer = setTimeout(() => {
      fn.apply(this, arguments);
    }, wait);
  };
}

once

function once(fn) {
  let called = false;
  return function () {
    if (!called) {
      called = true;
      fn.apply(this, arguments);
    }
  };
}

位运算

function swapNumber(a, b) {
  a = a ^ b;
  b = a ^ b;
  a = a ^ b;
  return {
    a,
    b,
  };
}

function oddCountNumber(arr = []) {
  let num = 0;
  const len = arr.length;
  for (let i = 0; i < len; i++) {
    num = num ^ arr[i];
  }
  return num;
}

sleep

function sleep(ms) {
  return new Promise((resolve) => setTimeout(resolve, ms));
}

// 性能很差
function sleep(delay) {
  for (let timer = Date.now(); Date.now() - timer <= delay; );
}

生成随机数

function randomNum(min, max) {
  return min + Math.floor(Math.random() * (max - min + 1));
}

flat

function flat(list = []) {
  return list.reduce((R, c) => {
    return R.concat(Array.isArray(c) ? flat(c) : c);
  }, []);
}

function flat(arr = []) {
  return arr.reduce((R, c) => {
    return Array.isArray(c) ? [...R, ...flat(c)] : [...R, c];
  }, []);
}

uniq

function uniq(list = []) {
  return list.reduce((R, c) => {
    R.indexOf(c) < 0 ? R.push(c) : null;
    return R;
  }, []);
}

counter

function counter(list = []) {
  return list.reduce((R, c) => {
    R[c] ? R[c]++ : (R[c] = 1);
  }, {});
}

max

function max(list = []) {
  return list.reduce((R, c) => {
    return Math.max(R, c);
  });
}

compose

const compose = (...args) => {
  let start = args.length - 1
  return function () {
    let result = args[start].apply(this, arguments)
    while(start) {
      result = args[--start].call(this, result)
    }
    return result
  }
}


function compose(...fns) {
  return fns.reduce(
    (a, b) =>
      (...args) =>
        a(b(...args))
  );
}

defineProperty

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

if (a == 1 && a == 2 && a == 3) {
  console.info(`i am ok.`)
}

let num = 0

Object.defineProperty(window, 'a', {
  get () {
    return ++num
  }
})

if (a == 1 && a == 2 && a == 3) {
  console.log('i am ok.')
}

isRepeat

const isRepeat = (list = []) {
  let hash = {}
  for (let i of list) {
    if(hash[i]) {
      return true
    }
    hash[i] = true
  }
  return false
}

不同类型的数组去重

function uniqArray (arr = []) {
  const cache = new Set();
  const result = [];
  
  arr.forEach(it => {
    let str = JSON.stringify(it);
    if (!cache.has(str)) {
      cache.add(str);
      result.push(it);
    }
  })

  return result
}

嵌套数组扁平化

function flatObj(obj, prefix = "") {
  return Object.keys(obj).reduce((acc, key) => {
    const value = obj[key];
    const keyPrefix = prefix ? `${prefix}.${key}` : key;

    if (Array.isArray(value)) {
      acc = value.reduce((acc, item, index) => {
        return typeof item === "number"
          ? { ...acc, [`${keyPrefix}[${index}]`]: item }
          : Object.assign(acc, flatObj(item, `${keyPrefix}[${index}]`));
      }, acc);
    } else if (typeof value === "object" && value !== null) {
      acc = Object.assign(acc, flatObj(value, keyPrefix));
    } else {
      acc[keyPrefix] = value;
    }

    return acc;
  }, {});
}