All 手写算法解集

链表

二叉树

回文

子串

括号

字符

重复

最大

最小

删除

手写-CSS

手写-通用

手写-模拟实现

手写-排序

手写-设计模式

OD 题库

重置

1

addTwoNumbers 两数相加（链表）

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]

var addTwoNumbers = function (l1, l2) {
  const l3 = new ListNode(0)
  let p1 = l1
  let p2 = l2
  let p3 = l3
  let carry = 0

  while (p1 || p2) {
    const val1 = p1 ? p1.val : 0
    const val2 = p2 ? p2.val : 0
  const sum = val1 + val2 + carry
    carry = Math.floor(sum / 10)
    p3.next = new ListNode(sum % 10)
    if (p1) {
      p1 = p1.next
    }
    if (p2) {
      p2 = p2.next
    }
    p3 = p3.next
  }

  if (carry) {
    p3.next = new ListNode(carry)
  }

  return l3.next
};

averageOfLevels 二叉树的层平均值

输入：root = [3,9,20,null,null,15,7]
输出：[3.00000,14.50000,11.00000]

输入：root = [3,9,20,15,7]
输出：[3.00000,14.50000,11.00000]

var averageOfLevels = function(root) {
  /**
   * 该方案使用广度优先遍历数组节点，然后计算每层节点
   * 的平均值，并记录
   *
   * 广度优先算法依靠一个队列，先将根节点入队，然后循环
   * 不断将队列中的节点出队，然后将出队节点不为空的左右
   * 节点再次入队。如此往复直到队列为空
   *
   */
  if (!root) return [];
  let quene = [root],
    out = [];
  // 当队列不为空则继续遍历
  while (quene.length) {
    let divisor = (count = quene.length),
      // 记录本层节点值总和
      sum = 0;
    // 遍历当前层级的所有节点
    while (count--) {
      // 出队
      let node = quene.shift();
      // 加上当前节点值
      sum += node.val;
      // 将出队节点不为空的左右节点再次入队
      if (node.left) quene.push(node.left);
      if (node.right) quene.push(node.right);
    }
    out.push(sum / divisor);
  }
  // 返回结果
  return out;
}

buildTree 从前序与中序遍历序列构造二叉树

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出: [3,9,20,null,null,15,7]

//把每个preorder中的节点依次当作根节点
// 将其对应的子树
// 从 inorder 中分离出来
// 递归地解决整个问题
var buildTree = function (preorder, inorder) {
  // 当 preorder 和 inorder 均为空时
  // 说明已经到了空节点
  if (!preorder.length ||
      !inorder.length) {
    return null;
  }
  // 创建根节点 -> preorder[0]
  let node = 
    new TreeNode(preorder[0]);
// 找到preoder[0]对应inorder中的位置
let index = 
inorder.indexOf(preorder.shift());

  // 左右子树递归
  node.left = 
    buildTree(
      preorder,
      inorder.slice(0, index)
    );
  node.right = 
    buildTree(
      preorder,
      inorder.slice(index + 1)
    );
  // 返回根节点
  return node;
};

buildTree 从中序与后序遍历序列构造二叉树

输入：inorder = [9,3,15,20,7], postorder = [9,15,7,20,3]
输出：[3,9,20,null,null,15,7]

输入：inorder = [-1], postorder = [-1]
输出：[-1]

var buildTree = function (inorder, postorder) {
  const n = inorder.length;
  const index = new Map();
  for (let i = 0; i < n; i++) {
    index.set(inorder[i], i);
  }

  function dfs(inL, inR, postL, postR) {
    if (postL === postR) {
      // 空节点
      return null;
    }
    // 左子树的大小
    const leftSize = 
      index.get(postorder[postR - 1]) - inL;
    const left =
      dfs(inL, inL + leftSize, postL, postL + leftSize);
    const right =
      dfs(inL + leftSize + 1, inR, postL + leftSize, postR - 1);
    return new TreeNode(postorder[postR - 1], left, right);
  }
  return dfs(0, n, 0, n); // 左闭右开区间
};

// 时间复杂度：O(n)，其中 n 为 inorder 的长度。递归 O(n) 次，每次只需要 O(1) 的时间。
// 空间复杂度：O(n)。

BSTIterator 二叉搜索树迭代器

输入
["BSTIterator", "next", "next", "hasNext", "next", "hasNext", "next", "hasNext", "next", "hasNext"]
[[[7, 3, 15, null, null, 9, 20]], [], [], [], [], [], [], [], [], []]
输出
[null, 3, 7, true, 9, true, 15, true, 20, false]

/**
 * 本方案使用深度优先的方式，首先使用递归实现
 * 深度优先中序遍历，然后使用数组记录遍历的树
 * 的节点，最后定义一个索引，表示next()函数已
 * 经调用到的数组索引位置，当索引超出数组大小
 * 即hasNext()函数为false
 */

var BSTIterator = function (root) {
  // 记录中序遍历的节点
  this.searchList = [];
  // 记录next()函数已经调用到的数组的索引
  this.index = 0;
  let that = this;
  /**
   * 递归回溯实现深度优先中序遍历
   */
  function dfs(root) {
    if (!root) return;
    dfs(root.left);
    // 记录遍历的节点
    that.searchList.push(root.val);
    dfs(root.right);
  }
  // 执行深度优先中心遍历
  dfs(root);
};

BSTIterator.prototype.next = function () {
  // 当索引未超过数组大小
  if (this.index < this.searchList.length) {
    // 索引+1
    this.index++;
    // 返回元素
    return this.searchList[this.index - 1];
  }
  return null;
};

BSTIterator.prototype.hasNext = function () {
  // 当索引未超过数组大小，证明还有下一个元素，返回true
  if (this.index < this.searchList.length) {
    return true;
  }
  // 否则，返回false
  else return false;
};

canCompleteCircuit 加油站

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3

var canCompleteCircuit = function (gas, cost) {
  let totalGas = 0;
  let totalCost = 0;
  for (let i = 0;
    i < gas.length; i++) {
    totalGas += gas[i];
    totalCost += cost[i];
  }
  // 总油量小于总油耗 肯定不能走一圈
  if (totalGas < totalCost) {
    return -1;
  }
  let currentGas = 0;
  let start = 0;
  for (let i = 0;
    i < gas.length; i++) {
    currentGas = currentGas
      - cost[i] + gas[i];
    // 如果到达下一站的时候油量为负数
    // 就以这个站为起点 重新计算
    if (currentGas < 0) {
      currentGas = 0;
      start = i + 1;
    }
  }

  return start;
};
// 时间复杂度：O(N)
// 空间复杂度：O(1)

canConstruct 赎金信

输入：ransomNote = "a", magazine = "b"
输出：false

输入：ransomNote = "aa", magazine = "ab"
输出：false

输入：ransomNote = "aa", magazine = "aab"
输出：true

var canConstruct = function (ransomNote, magazine) {
  if (ransomNote.length > magazine.length) {
    return false;
  }
  const cnt = Array(26).fill(0);
  const ordA = "a".charCodeAt(0);
  for (const c of magazine) {
    cnt[c.charCodeAt(0) - ordA]++;
  }
  for (const c of ransomNote) {
    if (--cnt[c.charCodeAt(0) - ordA] < 0) {
      return false;
    }
  }
  return true;
};

candy 分发糖果

输入：ratings = [1,0,2]
输出：5

输入：ratings = [1,2,2]
输出：4

var candy = function (ratings) {
  const n = ratings.length;
  let ans = n; // 先给每人分一个
  for (let i = 0; i < n; i++) {
    let start = i > 0 &&
      ratings[i - 1] < ratings[i] ? i - 1 : i;

    // 找严格递增段
    while (i + 1 < n && ratings[i] < ratings[i + 1]) {
      i++;
    }
    const top = i; // 峰顶

    // 找严格递减段
    while (i + 1 < n && ratings[i] > ratings[i + 1]) {
      i++;
    }

    const inc = top - start; // start 到 top 严格递增
    const dec = i - top; // top 到 i 严格递减
    ans += (
      inc * (inc - 1) + dec * (dec - 1)) / 2 +
      Math.max(inc, dec);
  }
  return ans;
};
// 时间复杂度：O(n)，其中 n 是 ratings 的长度，
// 因为注意变量 i 只会增加，不会重置也不会减少
// 空间复杂度：O(1)。

calcEquation 除法求值

输入：equations = [["a","b"],["b","c"]], values = [2.0,3.0], queries = [["a","c"],["b","a"],["a","e"],["a","a"],["x","x"]]
输出：[6.00000,0.50000,-1.00000,1.00000,-1.00000]

var calcEquation = function (equations, values, queries) {
  let map = new Map(), res = [];
  //visit数组标记在搜索过程中是否访问过
  let visit = new Map();
  const dfs = (src, dst) => {
    // 若可达，且找到了目的节点
    // 返回 1.0 表示成功到达
    if (src === dst) {
      return 1.0;
    }
    let adjs = map.get(src);
// 遍历 src 的所有边，若未访问过
// 则对其调用 dfs 获取路径积
for (let i = 0; i < adjs.length; ++i) {
  let next = adjs[i];
  if (!visit.get(next[0])) {
    visit.set(next[0], true);
    let ret = dfs(next[0], dst);
    visit.set(next[0], false);
    // 若可达 dst
//则返回当前边权与后续的边权积 ret的乘积
    if (ret !== -1.0) {
      return next[1] * ret;
    }
  }
}
    // 否则，不可达，返回 -1.0
    return -1.0;
  };
  // 创建邻接表
  for (let i = 0; i < equations.length; ++i) {
    let e = equations[i],
        v = values[i];
    if (!map.has(e[0])) {
      map.set(e[0], []);
      visit.set(e[0], false);
    }
    if (!map.has(e[1])) {
      map.set(e[1], []);
      visit.set(e[1], false);
    }
    let adj1 = map.get(e[0]);
    let adj2 = map.get(e[1]);
    adj1.push([e[1], v]);
    adj2.push([e[0], 1 / v]);
  }
  for (let q of queries) {
    let n0 = q[0], n1 = q[1];
if (map.has(n0) && map.has(n1)) {
  visit.set(n0, true);
  res.push(dfs(n0, n1));
  visit.set(n0, false);
} else {
  res.push(-1.0);
}
  }
  return res;
};

calculate 基本计算器

输入：s = "1 + 1"
输出：2

输入：s = " 2-1 + 2 "
输出：3

输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

var calculate = function (s) {
  // 栈+递归的方式
  // 遇到(递归计算括号内结果，传入字符串位置
  function recusion(index) {
    let stack = [],
      // 前面的符号
      sign = "+",
      // 数值
      number = 0,
      // 遍历到字符串的位置
      i = index;
    while (i < s.length) {
      let char = s[i];
      // 当前字符如果是数字，那么使用number记录
      if (!isNaN(char) && char != " ") {
        number = number * 10 + char * 1;
      }
      // 当前字符如果不是数字，但是左括号，此时递归获取括号的数字
      else if (char == "(") {
        let temp = recusion(i + 1);
        number = temp[0];
        i = temp[1];
      }
      // 当前字符如果不是数字且不为空格，或者当前字符为最后一个字符
      // 此时需要将数字push到栈中，并重置number与sign
      if ((isNaN(char) && char != " ") || s.length - 1 <= i) {
        switch (sign) {
          case "+":
            stack.push(number);
            break;
          case "-":
            stack.push(-number);
            break;
          case "*":
            stack.push(stack.pop() * number);
            break;
          case "/":
            stack.push(stack.pop() / number);
            break;
        }
        number = 0;
        sign = char;
      }
      // 如果当前字符为右括号，那么需要结束递归
      if (char == ")") break;
      i++;
    }
    number = 0;
    // 将栈中元素求和
    stack.forEach((val) => (number += val));
    return [number, i];
  }

  // 执行递归，返回结果
  return recusion(0)[0];
}

calculate 基本计算器 II

输入：s = "3+2*2"
输出：7

输入：s = " 3/2 "
输出：1

输入：s = " 3+5 / 2 "
输出：5

var calculate = function (s) {
  s = s.trim();
  const stack = new Array();
  let preSign = '+';
  let num = 0;
  const n = s.length;
  for (let i = 0; i < n; ++i) {
    if (!isNaN(Number(s[i])) &&
      s[i] !== ' ') {
      num = num * 10 +
        s[i].charCodeAt() -
        '0'.charCodeAt();
    }
    if (isNaN(Number(s[i])) ||
      i === n - 1) {
      switch (preSign) {
        case '+':
          stack.push(num);
          break;
        case '-':
          stack.push(-num);
          break;
        case '*':
          stack.push(
            stack.pop() * num
          );
          break;
        default:
          stack.push(
            stack.pop() / num | 0
          );
      }
      preSign = s[i];
      num = 0;
    }
  }
  let ans = 0;
  while (stack.length) {
    ans += stack.pop();
  }
  return ans;
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

canFinish 课程表

输入：numCourses = 2, prerequisites = [[1,0]]
输出：true

输入：numCourses = 2, prerequisites = [[1,0],[0,1]]
输出：false

// BFS 拓扑排序
var canFinish = function (numCourses, prerequisites) {
  // 入度数组
  const inDegree =
    new Array(numCourses).fill(0);
  // 邻接表
  const map = {};
for (let i = 0;
  i < prerequisites.length; i++) {
  // 求课的初始入度值
  inDegree[prerequisites[i][0]]++;
  // 当前课已经存在于邻接表
  if (map[prerequisites[i][1]]) {
    // 添加依赖它的后续课
    map[prerequisites[i][1]].push(
      prerequisites[i][0]
    );
  } else {
    // 当前课不存在于邻接表
    map[prerequisites[i][1]] =
      [prerequisites[i][0]];
  }
}
  const queue = [];
  // 所有入度为0的课入列
  for (let i = 0;
    i < inDegree.length; i++) {
    if (inDegree[i] == 0) {
      queue.push(i);
    }
  }
  let count = 0;
while (queue.length) {
// 当前选的课，出列
const selected = queue.shift();
// 选课数+1 
count++;
// 获取这门课对应的后续课
const toEnQueue = map[selected];
// 确实有后续课
if (toEnQueue && toEnQueue.length) {
  for (let i = 0;
    i < toEnQueue.length; i++) {
    // 依赖它的后续课的入度-1
    inDegree[toEnQueue[i]]--;
    // 如果因此减为0，入列
if (inDegree[toEnQueue[i]] == 0) {
  queue.push(toEnQueue[i]);
}
  }
}
  }
// 选了的课等于总课数，true，否则false
  return count == numCourses;
};

canJump 跳跃游戏

输入：nums = [2,3,1,1,4]
输出：true

输入：nums = [3,2,1,0,4]
输出：false

var canJump = function (nums) {
  // 必须到达 end 下标的数字
  let end = nums.length - 1;
  for (
    let i = nums.length - 2;
    i >= 0; i--) {
    if (end - i <= nums[i]) {
      end = i;
    }
  }

  return end == 0;
};

canJump 跳跃游戏 II

输入: nums = [2,3,1,1,4]
输出: 2

输入: nums = [2,3,0,1,4]
输出: 2

var jump = function (nums) {
  let curIndex = 0;
  let nextIndex = 0;
  let steps = 0;
  for (let i = 0; i < nums.length - 1; i++) {
    nextIndex = Math.max(nums[i] + i, nextIndex);
    if (i === curIndex) {
      curIndex = nextIndex;
      steps++;
    }
  }

  return steps;
};

canJump 跳跃游戏 III

输入：arr = [4,2,3,0,3,1,2], start = 5
输出：true

输入：arr = [4,2,3,0,3,1,2], start = 0
输出：true

输入：arr = [3,0,2,1,2], start = 2
输出：false

var canReach = function (arr, start) {
  const queue = [start];
  const visited = [];

  while (queue.length) {
    const i = queue.shift();
    visited.push(i);
    if (arr[i] === 0) return true;

    const left = i - arr[i];
    if (left >= 0 && !visited.includes(left)) {
      queue.push(left);
    }
    const right = i + arr[i];
    if (right < arr.length && !visited.includes(right)) {
      queue.push(right);
    }
  }
  return false;
};

canPartition 分割等和子集

输入：nums = [1,5,11,5]
输出：true

输入：nums = [1,2,3,5]
输出：false

var canPartition = (nums) => {
  let sum = 0;
  for (const n of nums) {//求数组和
    sum += n;
  }
  // 如果 sum 为奇数，直接返回 false
  if (sum % 2 != 0) {
    return false
  };
  const target = sum / 2; // 目标和
  // curSum是当前累加和，i是指针
const dfs = (curSum, i) => {
  if (i == nums.length ||
      curSum > target) {
    return false;
  }
  if (curSum == target) {
    return true;
  }
// 选nums[i]当前和变为curSum+nums[i]
// 考察的指针移动一位
// 不选 nums[i]，当前和还是 curSum
// 考察的指针移动一位
  return dfs(curSum + nums[i],
    i + 1) || dfs(curSum, i + 1);
};
  // 递归的入口，当前和为0，指针为0
  return dfs(0, 0);
};

climbStairs 爬楼梯

输入：n = 2
输出：2

输入：n = 3
输出：3

var climbStairs = function (n) {
  let p = 0,
    q = 0,
    r = 1;
  for (let i = 1; i <= n; ++i) {
    p = q;
    q = r;
    r = p + q;
  }
  return r;
};
// 时间复杂度 O(n)
// 空间复杂度为 O(1)

closedIsland 统计封闭岛屿的数目

输入：grid = [[1,1,1,1,1,1,1,0],[1,0,0,0,0,1,1,0],[1,0,1,0,1,1,1,0],[1,0,0,0,0,1,0,1],[1,1,1,1,1,1,1,0]]
输出：2

输入：grid = [[0,0,1,0,0],[0,1,0,1,0],[0,1,1,1,0]]
输出：1

var closedIsland = function (grid) {
  let res = 0
  let directions = [
    [-1, 0], [1, 0],
    [0, -1], [0, 1]
  ]
  const m = grid.length,
        n = grid[0].length
  const dfs = (i, j) => {
    if (i < 0 || i >= m ||
      j < 0 || j >= n) return
    if (grid[i][j] == '1') return
    grid[i][j] = '1'
    for (let d of directions) {
      dfs(i + d[0], j + d[1])
    }
  }
  for (let i = 0; i < m; i++) {
    dfs(i, 0)
    dfs(i, n - 1)
  }
  for (let j = 0; j < n; j++) {
    dfs(0, j)
    dfs(m - 1, j)
  }
  for (let i=1; i < m - 1; i++){
    for (let j=1; j<n - 1; j++){
      if (grid[i][j] == '0') {
        res++
        dfs(i, j)
      }
    }
  }
  return res
};

coinChange 零钱兑换

输入：coins = [1, 2, 5], amount = 11
输出：3

输入：coins = [2], amount = 3
输出：-1

输入：coins = [1], amount = 0
输出：0

var coinChange = function (coins, amount) {
  let dp = new Array(amount + 1)
    .fill(Infinity); // 初始化dp数组
  dp[0] = 0; // 面额0只需要0个硬币兑换
  // 循环面额
for (let i = 1; i <= amount; i++){
  // 循环硬币数组
  for (let coin of coins) {
    // 当面额大于硬币价值时
    if (i - coin >= 0) {
// dp[i - coin]
// 当前面额i减当前硬币价值所需的最少硬币
// dp[i] 可由 dp[i-coin]+1 转换而来
      dp[i] = Math.min(
        dp[i], dp[i - coin] + 1
      );
    }
  }
}
//如果dp[amount]===Infinity则无法兑换
  return dp[amount] === Infinity ?
    -1 : dp[amount];
};
// 时间复杂度是 O(sn)
// s 是兑换金额，n 是硬币数组长度
// 空间复杂度是 O(s) 即 dp 数组长度

change 零钱兑换 II

输入：amount = 5, coins = [1, 2, 5]
输出：4

输入：amount = 3, coins = [2]
输出：0

输入：amount = 10, coins = [10] 
输出：1

var change = function (amount, coins) {
  function recur(coins, index, amount) {
    // 终止条件 选完最后一个硬币，如果剩下的钱为0，说明是一种合格方法，返回1 否则返回0
    if (index === coins.length) {
      return amount === 0 ? 1 : 0;
    }
    let cnt = 0;
    // 只选 i 个 index 位置的硬币，然后从 index + 1 继续做选择
    // 在 for 循环里面保证的剩下的钱一定会大于等于0的
    for (let i = 0; coins[index] * i <= amount; i++) {
      // 加上从 index+1 位置前，兑换数量为 amount - coins[index] * i 的方法
      cnt += recur(
        coins, index + 1, amount - coins[index] * i
      );
    }
    return cnt;
  }

  return recur(coins, 0, amount);
};

combine 组合

输入：n = 4, k = 2
输出：
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

输入：n = 1, k = 1
输出：[[1]]

var combine = (n, k) => {
  const res = [];
  // start 是枚举选择的起点
  // path 是当前构建的路径（组合）
  const helper = (start,path)=>{
    if (path.length == k) {
      // 拷贝一份 path，推入 res
      res.push(path.slice());
      // 结束当前递归
      return;
    }
    // 枚举出所有选择
    for (let i=start; i<=n; i++){
      // 选择
      path.push(i);
      // 向下继续选择
      helper(i + 1, path);
      // 撤销选择
      path.pop();
    }
  };
  // 递归的入口，从数字 1 开始选
  helper(1, []);
  return res;
}

combinationSum 组合总和

输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]

输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]

输入: candidates = [2], target = 1
输出: []

var combinationSum = function (candidates, target) {
  const res = [];
  // start 是当前选择的起点索引
  // temp 是当前的集合
  // sum 是当前求和
const dfs = (start, temp, sum) => { 
  if (sum >= target) {
    if (sum == target) {
      // temp 的拷贝 加入解集
      res.push(temp.slice());
    }
    // 结束当前递归
    return;
  }
  // 枚举当前可选的数，从start开始
  for (let i = start; i < candidates.length; i++) {
    // 选这个数
    temp.push(candidates[i]);
    // 基于此继续选择，传 i
    // 下一次就不会选到 i 左边的数
    dfs(i, temp, sum + candidates[i]);
// 撤销选择
// 回到选择 candidates[i] 之前的状态
// 继续尝试选同层右边的数
    temp.pop();
  }
};
  // 最开始可选的数是从第 0 项开始的
  // 传入一个空集合，sum 也为 0
  dfs(0, [], 0);
  return res;
};

connect 填充每个节点的下一个右侧节点指针（二叉树）

输入：root = [1,2,3,4,5,6,7]
输出：[1,#,2,3,#,4,5,6,7,#]

输入：root = []
输出：[]

var connect = function (root) {
  if (root === null) {
    return root;
  }
// 初始化队列同时将第一层节点加入队列中
// 即根节点
  const queue = [root];
  // 外层的 while 循环迭代的是层数
  while (queue.length > 0) {
    // 记录当前队列大小
    const size = queue.length;
    // 遍历这一层的所有节点
    for (let i=0; i < size; i++) {
      // 从队首取出元素
      const node = queue.shift();
      // 连接
      if (i < size - 1) {
        node.next = queue[0];
      }
      // 拓展下一层节点
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
  }
  // 返回根节点
  return root;
};
// 时间复杂度：O(N)
// 空间复杂度：O(N)

connect 填充每个节点的下一个右侧节点指针 II（二叉树）

输入：root = [1,2,3,4,5,null,7]
输出：[1,#,2,3,#,4,5,7,#]

输入：root = []
输出：[]

var connect = function (root) {
  if (!root) return null;
  const queue = [root];
  let cur;
  let level;
  while (queue.length) {
    level = queue.length;
    let i = 0;
    const temp = [];
    while (i++ < level) {
      cur = queue.shift();
      temp.push(cur);
      cur.left &&
        queue.push(cur.left);
      cur.right &&
        queue.push(cur.right);
    }
    temp.forEach((v, k) => {
      v.next=temp[k + 1] || null;
    });
  }
  return root;
};

copyRandomList 随机链表的复制

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

输入：head = [[1,1],[2,1]]
输出：[[1,1],[2,1]]

输入：head = [[3,null],[3,0],[3,null]]
输出：[[3,null],[3,0],[3,null]]

var copyRandomList = function (head) {
  if (!head) return head;
  let cur = head;
  const map = new Map();
// 第一次遍历 生成一个具有val属性的链表
  while (cur) {
    map.set(cur, new Node(cur.val))
    cur = cur.next
  }
  // 第二次遍历，根据 map 映射关系
  // 将 random 和 next 指针
  // 指向对应的节点或 null
  cur = head
  while (cur) {
    map.get(cur).next =
      map.get(cur.next) || null
    map.get(cur).random =
      map.get(cur.random) || null
    cur = cur.next
  }
  return map.get(head);
};

countAndSay 外观数列

输入：n = 4
输出："1211"

输入：n = 1
输出："1"

var countAndSay = function (n) {
  let prev = '1'
  for (let i = 1; i < n; i++) {
    prev =
      prev.replace(
        /(\d)\1*/g,
        item =>
        `${item.length}${item[0]}`
      )
  }
  return prev
};

countBits 比特位计数

输入：n = 2
输出：[0,1,1]

输入：n = 5
输出：[0,1,1,2,1,2]

var countBits = function (n) {
  const bits = new Array(n + 1)
    .fill(0);
  const countOnes = (x) => {
    let ones = 0;
    while (x > 0) {
      x &= (x - 1);
      ones++;
    }
    return ones;
  }
  for (let i = 0; i <= n; i++) {
    bits[i] = countOnes(i);
  }
  return bits
};

countBinarySubstrings 计数二进制子串

输入：s = "00110011"
输出：6

输入：s = "10101"
输出：4

var countBinarySubstrings = function (s) {
  let result = 0;

  // 字符串匹配算法
  const match = (subString) => {
    // 先找到开头的连续数字[0|1]
    let startStr =
      subString.match(/^((0+)|(1+))/)[0];
    subString =
      subString.slice(0, startStr.length * 2);
    // 推算出组合字符串
    let endStr = (startStr[0] ^ 1).toString()
      .repeat(startStr.length);
    // 查看字符串中是否匹配组合字符串
    return subString.startsWith(
      `${startStr}${endStr}`
    );
  };

  // 循环计算每个子串中出现符合条件的字符情况
  // 如果找到就+1，并break到下一个子串
  for (let index = 0; index < s.length - 1; index++) {
    let subString = s.slice(index);
    if (match(subString)) {
      result += 1;
    }
  }

  return result;
};

countNodes 完全二叉树的节点个数

输入：root = [1,2,3,4,5,6]
输出：6

输入：root = []
输出：0

输入：root = [1]
输出：1

var countNodes = function (root) {
  if (!root) return 0;

  let count = 1;
  const dfs = function (node) {
    if (node.left) {
      count++;
      dfs(node.left);
    }
    if (node.right) {
      count++;
      dfs(node.right);
    }
  };
  dfs(root);
  return count;
};

countPrimes 计数质数

输入：n = 10
输出：4

输入：n = 0
输出：0

输入：n = 1
输出：0

var countPrimes = function (n) {
  let result = 0;
  const isPrime = (x) => {
    for (let i=2; i*i <= x; i++){
      if (x % i == 0) {
        return false;
      }
    }
    return true;
  }
  for (let i = 2; i < n; i++) {
    result += isPrime(i);
  }
  return result;
};
// 时间复杂度：O(n根号n)
// 空间复杂度：O(1)

countSmaller 计算右侧小于当前元素的个数

输入：nums = [5,2,6,1]
输出：[2,1,1,0]

输入：nums = [-1]
输出：[0]

输入：nums = [-1,-1]
输出：[0,0]

// 暴力法
var countSmaller = function(nums) {
  const counts = new Array(
    nums.length
  );
  for (let i = 0; i < nums.length; i++) {
    let count = 0;
    for (let j = i + 1;
      j < nums.length; j++) {
      if (nums[j] < nums[i]) {
        count++;
      }
    }
    counts[i] = count;
  }
  return counts;
};

countSubarrays 统计中位数为 K 的子数组

输入：nums = [3,2,1,4,5], k = 4
输出：3

输入：nums = [2,3,1], k = 3
输出：1

var countSubarrays = function (nums, k) {
  let index = 0
  // 将数字转换成大于、等于、小于
  const arr=nums.map((item,i)=>{
    if (item === k) {
      index = i
      return 0
    } else if (item < k) {
      return -1
    } else {
      return 1
    }
  })
  // 记录前缀和
  const sum = new Array(
    nums.length + 1).fill(0)
  for (let i=1;i<sum.length;i++){
    sum[i] = sum[i-1] + arr[i-1]
  }
  // 记录上一次出现的次数
  const pos = {}
  let ans = 0
  for (let i=0;i<sum.length;i++){
    const n = sum[i]
    if (i <= index) {
      pos[n] = (pos[n] ?? 0) + 1
      continue
    }
    // 在中间 || 在中间靠左
    ans += (pos[n] ?? 0)
    ans += (pos[n - 1] ?? 0)
  }
  return ans
};

countSubstrings 回文子串

输入：s = "abc"
输出：3

输入：s = "aaa"
输出：6

// 两层循环
var countSubstrings = function (s) {
  let count = 0;
  const isPalindrome = (s) => {
    let i = 0;
    let j = s.length - 1;
    while (i < j) {
      if (s[i] != s[j]) {
        return false;
      }
      i++;
      j--;
    }
    return true;
  };
  for (let i = 0;
    i < s.length; i++) {
    for (let j = i;
      j < s.length; j++) {
      if (isPalindrome(
        s.substring(i, j + 1)
      )) {
        count++;
      }
    }
  }
  return count;
};

containsNearbyDuplicate 存在重复元素 II

输入：nums = [1,2,3,1], k = 3
输出：true

输入：nums = [1,0,1,1], k = 1
输出：true

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

var containsNearbyDuplicate = function (nums, k) {
  const last = new Map();
  for (let i = 0; i < nums.length; i++) {
    const x = nums[i];
    if (last.has(x) && i - last.get(x) <= k) {
      return true;
    }
    last.set(x, i);
  }
  return false;
};

convert Z 字形变换

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"

var convert = function (s, numRows) {
  if (numRows === 1) return s;
  const rows = new Array(numRows).fill("");
  const n = 2 * numRows - 2;
  for (let i = 0; i < s.length; i++) {
    const x = i % n;
    rows[Math.min(x, n - x)] += s[i];
  }
  return rows.join("");
};

convertBST 把二叉搜索树转换为累加树

输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]

输入：root = [0,null,1]
输出：[1,null,1]

输入：root = [1,0,2]
输出：[3,3,2]

输入：root = [3,2,4,1]
输出：[7,9,4,10]

var convertBST = function (root) {
  let sum = 0;
  const inOrder = (root) => {
    // 遍历到null节点，开始返回
    if (root == null) {
      return;
    }
    // 先进入右子树
    inOrder(root.right);
    // 节点值累加给sum
    sum += root.val;
    // 累加的结果，赋给root.val
    root.val = sum;
    // 然后才进入左子树
    inOrder(root.left);
  };
  // 递归的入口，从根节点开始
  inOrder(root);
  return root;
}

dailyTemperatures 每日温度

输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]

输入: temperatures = [30,60,90]
输出: [1,1,0]

// 暴力法
var dailyTemperatures = function(temperatures) {
  const res = new Array(T.length)
    .fill(0);
  for (let i = 0;
    i < T.length; i++) {
    for (let j = i + 1;
      j < T.length; j++) {
      if (T[j] > T[i]) {
        res[i] = j - i;
        break;
      }
    }
  }
  return res;
}

decodeString 字符串解码

输入：s = "3[a]2[bc]"
输出："aaabcbc"

输入：s = "3[a2[c]]"
输出："accaccacc"

输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"

输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"

var decodeString = function (s) {
  let numStack = [];// 存倍数的栈
  let strStack=[];// 存待拼接的str的栈
  let num = 0;  // 倍数的搬运工
  let result = '';// 字符串的搬运工
for (const char of s) {//逐字符扫描
  if (!isNaN(char)) {   // 遇到数字
    // 算出倍数
    num = num * 10 + Number(char);
  } else if (char == '[') {
    // result 串入栈
    strStack.push(result);
    result = '';  // 入栈后清零
    // 倍数 num 进入栈等待
    numStack.push(num);
    num = 0;  // 入栈后清零
  } else if (char == ']') {
    // 遇到 ]，两个栈的栈顶出栈
    // 获取拷贝次数
   let repeatTimes=numStack.pop();
    // 构建子串
    result = strStack.pop()
      +result.repeat(repeatTimes);
  } else {
    // 遇到字母，追加给 result 串
    result += char;
  }
}
  return result;
};

deleteDuplicates 删除排序链表中的重复元素

输入：head = [1,1,2]
输出：[1,2]

输入：head = [1,1,2,3,3]
输出：[1,2,3]

var deleteDuplicates = function (head) {
  let p = head
  while (p) {
    if (p.val === p.next?.val) {
      p.next = p.next.next
    } else {
      p = p.next
    }
  }
  return head
};

deleteDuplicates 删除排序链表中的重复元素 II

输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]

输入：head = [1,1,1,2,3]
输出：[2,3]

var deleteDuplicates = function (head) {
  if (!head || !head.next) {
    return head;
  }
  if (head.val === head.next.val) {
    while (head.next && head.next.val === head.val) {
      head.next = head.next.next;
    }
    return deleteDuplicates(head.next);
  } else {
    head.next = deleteDuplicates(head.next);
  }
  return head;
};

deleteNode 删除链表中的节点

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]

输入：head = [4,5,1,9], val = 1
输出：[4,5,9]

var deleteNode = function (node) {
  node.val = node.next.val
  node.next = node.next.next
};

detectCycle 环形链表

输入：head = [3,2,0,-4], pos = 1
输出：true

输入：head = [1,2], pos = 0
输出：true

输入：head = [1], pos = -1
输出：false

var hasCycle = function (head) {
  try {
    JSON.stringify(head);
  } catch {
    return true;
  }
  return false;
};

var hasCycle = function (head) {
  while (head) {
    if (head.tag) {
      return true;
    }
    head.tag = true;
    head = head.next;
  }
  return false;
};

detectCycle 环形链表 II

输入：head = [3,2,0,-4], pos = 1
输出：返回索引为 1 的链表节点

输入：head = [1,2], pos = 0
输出：返回索引为 0 的链表节点

输入：head = [1], pos = -1
输出：返回 null

var detectCycle = function (head) {
  if (!head || !head.next) {
    return null;
  }
  let slow = head.next,
      fast = head.next.next;
  while (fast &&
    fast.next &&
    fast !== slow
  ) {
    slow = slow.next;
    fast = fast.next.next;
  }
  if (!fast || !fast.next) {
    return null;
  }
  slow = head;
  while (fast !== slow) {
    slow = slow.next;
    fast = fast.next;
  }
  return slow;
};

diameterOfBinaryTree 二叉树的直径

输入：root = [1,2,3,4,5]
输出：3

输入：root = [1,2]
输出：1

var diameterOfBinaryTree = function (root) {
  let result = 0
  function getDepth(root) {
    if (!root) return 0
    const leftDepth = getDepth(
      root.left)
    const rightDepth = getDepth(
      root.right)
    result = Math.max(
      result,
      (leftDepth + rightDepth)
    )
    return Math.max(
      leftDepth,
      rightDepth
    ) + 1
  }
  getDepth(root)
  return result
};

divide 两数相除

输入: dividend = 10, divisor = 3
输出: 3

输入: dividend = 7, divisor = -3
输出: -2

const MAX = 2147483647,
  MIN = -2147483648;
var divide = function (dividend, divisor) {
  if (dividend == MIN && divisor == -1) return MAX;
  let a = Math.abs(dividend),
    b = Math.abs(divisor),
    res = 0;
  for (let i = 31; i >= 0; i--) {
    if (a >>> i >= b) {
      // 1<<31 = -2147483648，需特殊处理
      if (i == 31) {
        a -= MAX;
        a -= 1;
        res -= MIN;
      } else {
        a -= b << i;
        res += 1 << i;
      }
    }
  }
  return dividend > 0 == divisor > 0 ? res : -res;
};

evalRPN 逆波兰表达式求值

输入：tokens = ["2","1","+","3","*"]
输出：9

输入：tokens = ["4","13","5","/","+"]
输出：6

输入：tokens = ["10","6","9","3","+","-11","*","/","*","17","+","5","+"]
输出：22

var evalRPN = function (tokens) {
  const n = tokens.length;
  const stack = new Array(
    Math.floor((n + 1) / 2)
  ).fill(0);
  let index = -1;
  for (let i = 0; i < n; i++) {
    const token = tokens[i];
    if (token === '+') {
      index--;
      stack[index]
        += stack[index + 1];
    } else if (token === '-') {
      index--;
      stack[index]
        -= stack[index + 1];
    } else if (token === '*') {
      index--;
      stack[index]
        *= stack[index + 1];
    } else if (token === '/') {
      index--;
      stack[index] =
        stack[index] /
        stack[index + 1] > 0 ?
        Math.floor(stack[index] /
        stack[index + 1]) :
        Math.ceil(stack[index] /
        stack[index + 1]);
    } else {
     index++;
     stack[index]=parseInt(token);
    }
  }
  return stack[index];
}; 
// 时间复杂度 O(n) n 是数组tokens长度
// 空间复杂度 O(n)

exist 单词搜索

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "SEE"
输出：true

输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCB"
输出：false

var exist = function (board, word) {
  // 网格的长和宽
  const h = board.length,
    w = board[0].length;
  // 方向数组
  const directions = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
  ];
  // 标记是否访问过的数组
  const visited = new Array(h);
  // 初始化 visited 数组
  for (
    let i = 0;
    i < visited.length;
    ++i
  ) {
    visited[i] =
      new Array(w).fill(false);
  }
  // 检查从网格 i，j 出发是否能
  // 搜索到 0-k 的字符组成的子串
  const check = (i, j, s, k) => {
//如果 i，j 位置的字符和
// 第 k 个的字符不相等
// 则这条搜索路径搜索失败 返回 false
    if (
      board[i][j] != s.charAt(k)
    ) {
      return false;
// 如果搜索到了字符串的结尾
// 则找到了网格中的一条路径
// 这条路径上的字符正好可组成字符串s
    } else if (k == s.length - 1) {
      return true;
    }
    // 标记 i，j 被访问过了
    visited[i][j] = true;
    let result = false;
// 向 i，j 的四个方向继续尝试寻找
for (const [dx, dy] of directions) {
  let newi = i + dx,
    newj = j + dy;
  // 新的坐标位置合法检查
  if (
    newi >= 0 &&
    newi < h &&
    newj >= 0 &&
    newj < w
  ) {
    // 新的坐标不能存在于 visited 中
    // 也就是不能是访问过的
    if (!visited[newi][newj]) {
      // 继续检查新的坐标
      const flag = check(
        newi, newj, s, k + 1
      );
      // 如果在网格中找到了字符串
      // 则跳过循环
      if (flag) {
        result = true;
        break;
      }
    }
  }
}
    // 回溯状态
    visited[i][j] = false;
    return result;
  }

  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      const flag = check(i, j, word, 0);
      if (flag) {
        return true;
      }
    }
  }
  return false;
};

flatten 二叉树展开为链表

输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]

输入：root = []
输出：[]

输入：root = [0]
输出：[0]

// 将二叉树展开为单链表之后
// 单链表中的节点顺序即为
// 二叉树的前序遍历访问各节点的顺序
// 因此，可以对二叉树进行前序遍历
// 获得各节点被访问到的顺序
// 由于将二叉树展开为链表之后
// 会破坏二叉树的结构，因此
// 在前序遍历结束之后更新
// 每个节点的左右子节点的信息
// 将二叉树展开为单链表
var flatten = function (root) {
  const list = [];
  const preorderTraversal =
    (root, list) => {
    if (root != null) {
      list.push(root);
      preorderTraversal(
        root.left, list
      );
      preorderTraversal(
        root.right, list
      );
    }
  }
  preorderTraversal(root, list);
  const size = list.length;
  for (let i = 1; i < size; i++) {
    const prev = list[i - 1],
          curr = list[i];
    prev.left = null;
    prev.right = curr;
  }
};

findAnagrams 找到字符串中所有字母异位词

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]

输入: s = "abab", p = "ab"
输出: [0,1,2]

var findAnagrams = function (s, p) {
  const res = [], // 返回的结果
        //存储窗口中的字符和对应的频次
        win = {},
        //存储需要的异位词的种类和数量
        need = {},
        pLen = p.length;
  let len = 0,//need异位词的字符种类
//滑动窗口中和need中字符数相同的字符种类
      val = 0;
  for (const x of p) {
    // 如果字符在 need 中不存在
    //则初始化need数组中对应的字符数量
    // 并且让字符种类加 1
    if (need[x] === undefined) {
      need[x] = win[x] = 0;
      len++;
    }
    //need中存在该字符 则字符数量加 1
    need[x]++;
  }
  for (let i = 0; i < s.length; i++) {
    // 滑动窗口左边界
    const j = i - pLen;
  //如果进入滑动窗口的字符s[i]在need中
  // 且窗口中的该字符数量加 1 之后
  // 和 need 中的字符数量相同，
  // 说明该字符已经满足了异位字符的要求
  // 让 val 加 1
   if (s[i] in need &&
    ++win[s[i]] === need[s[i]]) {
      val++;
    }
// 如果出滑动窗口的字符 s[j] 在 need中
// 并且滑动窗口中该字符数量
// 和 need 中的字符数量相同
// 说明从窗口中移除该字符之后不满足
// 异位字符的要求了
// 让窗口中这个字符的数量减1，且val减1
   if (s[j] in need &&
    win[s[j]]-- === need[s[j]]) {
      val--;
    }
//如果need中滑动窗口中的异位字符种类一致
//说明从j+1开始就是异位字符串的一个起点
    if (val === len) {
      res.push(j + 1);
    }
  }
  return res;
};

findCircleNum 省份数量

输入：isConnected = [[1,1,0],[1,1,0],[0,0,1]]
输出：2

输入：isConnected = [[1,0,0],[0,1,0],[0,0,1]]
输出：3

var findCircleNum = function (isConnected) {
 const cities=isConnected.length;
  const visited = new Set();
  let provinces = 0;
  const queue = new Array();
  for (let i=0; i<cities; i++) {
    if (!visited.has(i)) {
      queue.push(i);
      while (queue.length) {
        const j = queue.shift();
        visited.add(j);
for (let k = 0; k < cities; k++){
  if (isConnected[j][k] === 1
    && !visited.has(k)
  ) {
    queue.push(k);
  }
}
      }
      provinces++;
    }
  }
  return provinces;
};
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)

findDisappearedNumbers 找到所有数组中消失的数字

输入：nums = [4,3,2,7,8,2,3,1]
输出：[5,6]

输入：nums = [1,1]
输出：[2]

var findDisappearedNumbers = function (nums) {
  // 题目分析：找出未出现的数字
  // 规律 1 <= a <= n
  // 标记清除法 原地 O(n)
  const ans = []
  if (nums && Array.isArray(nums)
    && nums.length > 0) {
    // 需要结合数组索引与取值范围的特性
    // [4,3,2,7,8,2,3,1]
    // 我们需要注意一个特性
    // 由于它是满足 1 <= a <= n
    // 那么就存在一个关系 a[i-1] = i
    // 每一个数都有一个索引对应
    // 假设第一个是4
    // 说明在索引为3的地方就有对应的值了
    // 通过标记为负数来记住，这个坑有人
nums.forEach(item => {
  if (nums[Math.abs(item) - 1] > 0) {
    // 标记这个位置坑已经被占了
    nums[Math.abs(item) - 1] *= -1
  }
})
    // 第二次循环找出丢失得值
    nums.forEach((item, index) =>{
      if (item > 0) {
        ans.push(index + 1)
      }
    })
  }
  return ans
};

findDuplicate 寻找重复数

输入：nums = [1,3,4,2,2]
输出：2

输入：nums = [3,1,3,4,2]
输出：3

输入：nums = [3,3,3,3,3]
输出：3

// 快慢指针法
var findDuplicate = function (nums) {
  let slow = 0;
  let fast = 0;
  while (true) {
    slow = nums[slow];
    // slow 跳一步，fast 跳两步
    fast = nums[nums[fast]];
    // 指针首次相遇 
    if (slow == fast) {
      // 让快指针回到起点
      fast = 0;
      // 开启新的循环
      while (true) {
      // 如果再次相遇，就肯定是在入口处
        if (slow == fast) {
          // 返回入口，即重复的数
          return slow;
        }
        // 两个指针每次都进1步
        slow = nums[slow];
        fast = nums[fast];
      }
    }
  }
};

findMedianSortedArrays 寻找两个正序数组的中位数

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000

// 归并排序 暴力解法
var findMedianSortedArrays = function (nums1, nums2) {
  const merged = []
  let i = 0
  let j = 0
  while (i < nums1.length
    && j < nums2.length) {
    if (nums1[i] < nums2[j]) {
      merged.push(nums1[i++])
    } else {
      merged.push(nums2[j++])
    }
  }
  while (i < nums1.length) {
    merged.push(nums1[i++])
  }
  while (j < nums2.length) {
    merged.push(nums2[j++])
  }

  const { length } = merged

return length % 2 === 1 ?
  merged[Math.floor(length / 2)] :
  (merged[length / 2] + merged[length / 2 - 1]) / 2
};

findOrder 课程表 II

输入：numCourses = 2, prerequisites = [[1,0]]
输出：[0,1]

输入：numCourses = 4, prerequisites = [[1,0],[2,0],[3,1],[3,2]]
输出：[0,2,1,3]

输入：numCourses = 1, prerequisites = []
输出：[0]

var findOrder = function (numCourses, prerequisites) {
  // 初始化 上课 需要先完成课程 的门数
  let courses = Array(numCourses)
    .fill(0)
  // 记录受该课程 影响的其他课  
  let obj = {}
  prerequisites.forEach(item => {
    // one 要上的课 two 需先完成的课
    let [one, two] = item
    // 门数 + 1
    courses[one]++
    // 存在就加, 不存在就新建
    obj[two] ? obj[two].push(one)
             : obj[two] = [one]
  })
  const res = []
  const queue = []// 队列                   
  // 往队列添加 无需先上 就可以上的课 
  courses.forEach((t, i) => {
    // 因为是从 0 开始的
    // 所以索引也能代替 课的名称
    if (t === 0) queue.push(i)
  })
  while (queue.length) {
    // 出队 表示该课已经上了
    let cur = queue.shift()
    // 把出队的放入 结果数组
    res.push(cur)
    // 获取受该课影响的 课 
    let list = obj[cur]
    list && list.forEach(item =>{
      // 因为 出队表示该课已经上了
      // 所以 要先完成的门数 - 1
      courses[item]--
      // 当这个课 要先修完的
      // 已经修完了, 入队
      if (courses[item] == 0) {
        queue.push(item)
      }
    })
  }
  // 如果不可能完成所有课程，返回空数组
 return res.length === numCourses
    ? res : []
};

findPeakElement 寻找峰值

输入：nums = [1,2,3,1]
输出：2

输入：nums = [1,2,1,3,5,6,4]
输出：1 或 5

var findPeakElement = function (nums) {
  let idx = 0;
  for (let i = 1;
    i < nums.length; ++i) {
    if (nums[i] > nums[idx]) {
      idx = i;
    }
  }
  return idx;
};
// 时间复杂度：O(n) n 是数组nums长度
// 空间复杂度：O(1)

findPeakGrid 寻找峰值 II

输入: mat = [[1,4],[3,2]]
输出: [0,1]

输入: mat = [[10,20,15],[21,30,14],[7,16,32]]
输出: [1,1]

var findPeakGrid = function (mat) {
  let i = 0,
    j = 0;
  const isMax = (x, y) => {
    let arr = [
      [0, 1],
      [1, 0],
      [0, -1],
      [-1, 0],
    ];
    let isBreak = true;
    for (let i = 0; i < arr.length; i++) {
      let [x1, y1] = arr[i];
      if (
        x1 + x > -1 &&
        x1 + x < mat.length &&
        y1 + y > -1 &&
        y1 + y < mat[x].length
      ) {
        if (mat[x][y] <= mat[x + x1][y + y1]) {
          isBreak = false;
          break;
        }
      }
    }
    return isBreak;
  };
  let bk = true;
  while (i < mat.length && bk) {
    j = 0;
    while (j < mat[i].length && bk) {
      if (isMax(i, j)) {
        bk = false;
      }
      j++;
    }
    i++;
  }
  return [i - 1, j - 1];
};

findSubstring 串联所有单词的子串

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]

var findSubstring = function (s, words) {
 const wordSize = words[0].length
  const substringLen =
    wordSize * words.length

  const wordsCount = {}
  words.forEach(w =>
    (wordsCount[w] =
      (wordsCount[w] || 0) + 1
    ))

  const res = []
  for (let i = 0;
    i <= s.length - substringLen;
    i++) {
    const tempCount =
      { ...wordsCount }
    let count = words.length

    for (let j = i;
      j < i + substringLen;
      j += wordSize) {
      const word =
        s.slice(j, j + wordSize)

      if (!(word in tempCount) ||
      tempCount[word] <= 0) break

      tempCount[word]--
      count--
    }
    if (count === 0) res.push(i)
  }
  return res
};

findTargetSumWays 目标和

输入：nums = [1,1,1,1,1], target = 3
输出：5

输入：nums = [1], target = 1
输出：1

// DFS
var findTargetSumWays = function (nums, S) {
  let count = 0;
  function dfs(i, res) {
    if (i === nums.length) {
      if (res === S) {
        count++;
      }
      return;
    };
    dfs(i + 1, res + nums[i]);
    dfs(i + 1, res - nums[i]);
  }
  dfs(1, nums[0]);
  dfs(1, -nums[0]);
  return count;
};

findUnsortedSubarray 最短无序连续子数组

输入：nums = [2,6,4,8,10,9,15]
输出：5

输入：nums = [1,2,3,4]
输出：0

输入：nums = [1]
输出：0

// 双指针
var findUnsortedSubarray = function (nums) {
  let len = nums.length
  let left = 0
  let right = len - 1
  while (left < len - 1
    && nums[left]<=nums[left + 1]
  ) {
    left++
  }
  while (right > 0 &&
    nums[right - 1]<= nums[right]
  ) {
    right--
  }
  let min = Infinity
  let max = -Infinity
  for (let i = left;
    i <= right; i++) {
    min = Math.min(min, nums[i])
    max = Math.max(max, nums[i])
  }
  while (nums[left] > min) {
    left--
  }
  while (nums[right] < max) {
    right++
  }
  return left < right ?
    right - left - 1 : 0
};

findWords 单词搜索 II

输入：board = [["o","a","a","n"],["e","t","a","e"],["i","h","k","r"],["i","f","l","v"]], words = ["oath","pea","eat","rain"]
输出：["eat","oath"]

输入：board = [["a","b"],["c","d"]], words = ["abcb"]
输出：[]

var findWords = function (board, words) {
  // 构建字典树
  class TrieNode {
    constructor() {
      this.END = false;
      this.children=new Array(26);
    }
    containsKey(letter) {
      return this.children[
        letter.charCodeAt() - 97
      ] != undefined;
    }
    put(letter, newTrieNode) {
      this.children[
        letter.charCodeAt() - 97
      ] = newTrieNode;
    }
    getNext(letter) {
      return this.children[
        letter.charCodeAt() - 97
      ];
    }
    setEnd() {
      this.END = true;
    }
    isEnd() {
      return this.END;
    }
  }
  let root = null;
  let Trie = function () {
    root = new TrieNode();
  }
  Trie.prototype.insert = word =>{
    let currNode = root;
for(let i=0; i<word.length; i++){
  if (
    !currNode.containsKey(word[i])
  ) {
    currNode.put(
      word[i], new TrieNode()
    );
  }
  currNode = currNode.getNext(
    word[i]
  );
}
    currNode.setEnd();
  }
  let searchPrefix = (word) => {
    let currNode = root;
    for (let i = 0;
      i < word.length; i++) {
      if (currNode.containsKey(
        word[i]
      )) {
        currNode =
        currNode.getNext(word[i]);
      } else {
        return null;
      }
    }
    return currNode;
  }
  Trie.prototype.search=(word)=>{
    let currNode =
      searchPrefix(word);
    return currNode != null
      && currNode.isEnd();
  }
  Trie.prototype.startsWith =
    (prefix) => {
    let currNode =
      searchPrefix(prefix);
    return currNode != null;
  }
  // 初始化变量
  let m = board.length;
  let n = board[0].length;
  // 初始化字典树
  let wordsTrie = new Trie();
  for (let i = 0;
    i < words.length; i++) {
    wordsTrie.insert(words[i]);
  }
  // 搜索方向向量
  let dx = [-1, 1, 0, 0];
  let dy = [0, 0, -1, 1];
  // DFS 搜索
  let boardDFS = (i,j,curStr)=>{
    let restore = board[i][j];
    curStr += restore;
    // 字典树中找到了
    if (wordsTrie.search(curStr)
&& result.indexOf(curStr) == -1){
      result.push(curStr);
    }
    // 减枝 - 拼接字符判断是否
    // 存在于字典树中
    // 如果前缀都不是，直接false
    if (!wordsTrie.startsWith(
      curStr)) {
      return;
    }
    // 前进
    board[i][j] = '#';
    for (let r = 0; r < 4; r++) {
      let tmp_i = dx[r] + i;
      let tmp_j = dy[r] + j;
      // 边界情况处理
if (tmp_i >= 0 && tmp_i < m
  && tmp_j >= 0 && tmp_j < n
  && board[tmp_i][tmp_j] != '#'){
  boardDFS(tmp_i, tmp_j, curStr);
}
    }
    // 还原(回溯)
    board[i][j] = restore;
  }
  // 寻找结果
  let result = [];
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      boardDFS(i, j, '');
    }
  }
  return result;
};

firstMissingPositive 缺失的第一个正数

输入：nums = [1,2,0]
输出：3

输入：nums = [3,4,-1,1]
输出：2

输入：nums = [7,8,9,11,12]
输出：1

var firstMissingPositive = function (nums) {
  if (nums.length === 0) return 1
  if (nums.length === 1 &&
    nums[0] <= 0) {
    return 1
  }
  let arr = []
  nums.forEach((v) => {
    if (v >= 1) {
      arr[v] = 1
    }
  })
  if (!arr.length) {
    return 1
  }
  for (let i=1;i<arr.length;i++){
    if (!arr[i]) {
      return i
    }
  }
  return arr.length
};

firstUniqChar 字符串中的第一个唯一字符

输入: s = "leetcode"
输出: 0

输入: s = "loveleetcode"
输出: 2

输入: s = "aabb"
输出: -1

var firstUniqChar = function (s) {
  const frequency = _.countBy(s);
  for (const [i, ch] of
    Array.from(s).entries()) {
    if (frequency[ch] === 1) {
      return i;
    }
  }
  return -1;
};

fourSumCount 四数相加 II

输入：nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出：2

输入：nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出：1

var fourSumCount = function (A, B, C, D) {
  const ABmap = new Map();
  const len = A.length;
  for (let i of A) {
    for (let j of B) {
      // 统计AB之和及对应的数量
      if (ABmap.has(i + j)) {
        ABmap.set(i + j,
          ABmap.get(i + j) + 1);
      } else {
        ABmap.set(i + j, 1);
      }
    }
  }
  let res = 0;
  for (let k of C) {
    for (let l of D) {
      // 若A[i] + B[j]
      // === -(C[k] + D[l])
      // 则将数量加入到结果中
      if (ABmap.has(-k - l)) {
        res += ABmap.get(-k - l);
      }
    }
  }
  return res;
};

fractionToDecimal 分数到小数

输入：numerator = 1, denominator = 2
输出："0.5"

输入：numerator = 2, denominator = 1
输出："2"

输入：numerator = 4, denominator = 333
输出："0.(012)"

var fractionToDecimal = function(a, b) {
  // 如果答案没有小数点，直接返回
  if (!(a % b)) return `${a / b}`;
  // 整数部分
  let res = '';
  // 如果有一个小于0，需要添加负号
  if (a * b < 0) res += '-';
  a = Math.abs(a);
  b = Math.abs(b);
  // 整数部分+小数点
  res += `${Math.floor(a / b)}.`;
  // 小数部分
  const arr = [];
  const map = new Map();
  let index = 0;
  a %= b;
  while (a && !map.has(a)) {
    map.set(a, index++);
    a *= 10;
    arr.push(Math.floor(a / b));
    a %= b;
  }
  if (a) {
    // a 不是 0，说明上面的while循环
    // 是 map 中重复了才退出的
    const insertIndex = map.get(a);
    // 在循环开始的位置插入'('
    // 后面的元素后移
  arr.splice(insertIndex, 0, '(');
    // 尾部插入')'
    arr.push(')');
  }
  // 整数部分拼接小数部分
  return res + arr.join('');
};

FreqStack 最大频率栈

输入：["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]

var FreqStack = function () {
  // 记录 FreqStack 中元素的最大频率
  this.maxFreq = 0;
  // 记录 FreqStack 中每个 val 对应的出现频率，后文就称为 VF 表
  this.valToFreq = new Map();
  // 记录频率 freq 对应的 val 列表，后文就称为 FV 表
  this.freqToVals = new Map();
};

FreqStack.prototype.push = function (val) {
  // 修改 VF 表：val 对应的 freq 加一
  let freq = (
    this.valToFreq.get(val) || 0
  ) + 1;
  this.valToFreq.set(val, freq);
  let vals = [val];
  // 修改 FV 表：在 freq 对应的列表加上 val
  if (this.freqToVals.has(freq)) {
   vals=this.freqToVals.get(freq);
    vals.push(val);
  } else {
   this.freqToVals.set(freq,vals);
  }
  // 更新 maxFreq
  this.maxFreq = Math.max(this.maxFreq, freq);
};

FreqStack.prototype.pop = function () {
  // 修改 FV 表：pop 出一个 maxFreq 对应的元素 v
  let vals = this.freqToVals.get(
    this.maxFreq);
  let v = vals.pop();
  // 修改 VF 表：v 对应的 freq 减一
  let freq =this.valToFreq.get(v)
    - 1;
  this.valToFreq.set(v, freq);
  // 更新 maxFreq
  if (!vals.length) {
    // 如果 maxFreq 对应的元素空了
    this.maxFreq--;
  }
  return v;
};

fullJustify 文本左右对齐

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]

输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
var fullJustify = function (words, maxWidth) {
  let ans = [],
    cur = 0,
    tmp = [];
  for (const w of words) {
    // 统计长度 + 当前单词长度 + 最少空格长度
    const width = cur + w.length + tmp.length;
    // 大于等于maxWidth就需要进行换行
    if (width >= maxWidth) {
      // 等于说明空格数量刚好是最少的空格长度
      if (width === maxWidth) {
        tmp.push(w), (cur += w.length);
      }
      // 所有的空格数量
      const sum = maxWidth - cur;
      // 单词间隔数量
      const cnt = tmp.length - 1;
      // 间隔平均的空格数量
      const average = (sum / cnt) | 0;
      // 多出来的空格数量，需要添加到左边
      const remain = sum % cnt;
      // 生成行
      ans.push(
        tmp
          .reduce(
            (s, w, i) => s + " ".repeat(
              average + (remain + 1 > i ? 1 : 0)
            ) + w
          )
          .padEnd(maxWidth, " ")
      );
      // 重置
      tmp.length = 0;
      cur = 0;
    }
    // 当前单词已处理，要处理下一个单词
    if (width === maxWidth) continue;
    cur += w.length;
    tmp.push(w);
  }
  // 处理最后一行
  if (tmp.length) {
    ans.push(tmp.join(" ").padEnd(maxWidth, " "));
  }
  return ans;
};

gameOfLife 生命游戏

输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

var gameOfLife = function (board) {
  // 八个方向的偏移量
  const idx = [0, 1, 0, -1,
    -1, -1, 1, 1];
  const jdx = [1, 0, -1, 0,
    1, -1, 1, -1];

  // 数组副本
  const CopyBoard = board.map(
    // 值是基础类型（Number）
    // 不存在引用问题，直接解构比较方便
    ary => [...ary]
  );

  // 遍历每个细胞
  for (let i = 0;
    i < CopyBoard.length; i++) {
    for (let j = 0;
      j<CopyBoard[i].length;j++){

      // 周边活细胞统计
      let liveAmount = 0;
      // 八个方向都走一遍
      for (let index = 0;
        index < 8; index++) {
        let x = i + idx[index];
        let y = j + jdx[index];

        // 边界规避
        if (x < 0 || y < 0 || x
          >= CopyBoard.length || y
          >= CopyBoard[i].length
        ) continue;

        // 活细胞则计数加1
        liveAmount +=
          CopyBoard[x][y] ? 1 : 0;
      }

      // 该位置细胞死活决策
      if (liveAmount < 2 ||
        liveAmount > 3
      ) {
        board[i][j] = 0;
      } else if (liveAmount <= 3
        && CopyBoard[i][j]
      ) {
        board[i][j] = 1;
      } else if (liveAmount === 3
        && !CopyBoard[i][j]
      ) {
        board[i][j] = 1;
      }
    }
  }
};

generate 杨辉三角

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

输入: numRows = 1
输出: [[1]]

var generate = function (numRows) {
  const ret = [];
  for (let i=0; i < numRows; i++){
    const row =
      new Array(i + 1).fill(1);
    for (let j = 1;
      j < row.length - 1; j++) {
      row[j] = ret[i - 1][j - 1]
             + ret[i - 1][j];
    }
    ret.push(row);
  }
  return ret;
};
// 时间复杂度：O(numRows²)
// 空间复杂度：O(1)

generateParenthesis 括号生成

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

输入：n = 1
输出：["()"]

// 从 n-1 推导出 n 的组合情况
// 只需要遍历 n-1 的所有组合
// 并在所有组合的每个位置
// 填入一对括号 () 并去重即可
var generateParenthesis = function (n) {
  let set = new Set(['()']);
  for (let c = 2; c <= n; c++) {
    let nextSet = new Set();
    for (const s of set) {
      for (
        let j = 0;
        j <= s.length;
        j++
      ) {
        nextSet.add(
          s.slice(0, j)
          + '()'
          + s.slice(j)
        );
      }
    }
    set = nextSet;
  }
  return [...set];
};

getIntersectionNode 相交链表

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
输出：Intersected at '8'

输入：intersectVal = 2, listA = [1,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Intersected at '2'

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：No intersection

// 对于链表 A 的每个节点
// 都去链表 B 中遍历一遍找有没有相同节点
var getIntersectionNode = function (headA, headB) {
  if (!headA || !headB) {
    return null;
  }
  let pA = headA;
  while (pA) {
    let pB = headB;
    while (pB) {
      if (pA === pB) return pA;
      pB = pB.next;
    }
    pA = pA.next;
  }
};
// 时间复杂度：O(M*N)
// M, N 分别为两个链表的长度
// 空间复杂度：O(1)

getSum 两整数之和

输入：a = 1, b = 2
输出：3

输入：a = 2, b = 3
输出：5

var getSum = function (a, b) {
  // 进位左移一位得到新的数
  // 与异或得到的底数继续相加
  // 直到进位为 0 结束
  while (b) {
    sum = a ^ b
    b = (a & b) << 1
    a = sum
  }
  return sum
};

getSkyline 天际线问题

输入：buildings = [[2,9,10],[3,7,15],[5,12,12],[15,20,10],[19,24,8]]
输出：[[2,10],[3,15],[7,12],[12,0],[15,10],[20,8],[24,0]]

输入：buildings = [[0,2,3],[2,5,3]]
输出：[[0,3],[5,0]]

var getSkyline = function (buildings) {
  const arr = [],
        ans = [],
        n = buildings.length;
  // 记录点，用负数标记右点
  for (let [l,r,h] of buildings){
    arr.push([l, h], [r, -h]);
  }
  // 在x轴排序，x相同按y大的排
  arr.sort((a, b) =>
    a[0] - b[0] || b[1] - a[1]
  );
  const m = arr.length,
        heights = [0];
  // 记录前一个最高高度
  // 用于过滤出在x点最高的点
  // 和过滤两点在x处有相同高度的情况
  let preH = 0;
  for (let [l, h] of arr) {
    // 通过二分插入该左点高度
    if (h > 0) {
      heights.splice(
        search(heights, h), 0, h
      );
    } else {
      // 通过二分移除右点高度
      heights.splice(
        search(heights, -h), 1
      );
    }
    // 前高度和当前最高高度不相等
    // 说明出现了关键点
    if (preH !== heights[0]) {
      ans.push([l, heights[0]])
      preH = heights[0];
    }
  }
  return ans;
};

// 二分
function search(arr, tar) {
  let l = 0, r = arr.length - 1;
  while (l < r) {
    // >> 1 相当于除以2向下取整
    const mid = l + (
      (r - l) >> 1
    );
    if(arr[mid]===tar) return mid;
    else if (arr[mid]<tar) r=mid;
    else l = mid + 1;
  }
  return l;
}

groupAnagrams 字母异位词分组

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

输入: strs = [""]
输出: [[""]]

输入: strs = ["a"]
输出: [["a"]]

// Sort 忽略参数
// 按元素 Unicode 位点排序
// 即 Unicode 编码升序排列
var groupAnagrams = function (strs) {
  const h = new Map;
  let k;
  for (
    var i = 0;
    i < strs.length;
    i++
  ) {
    h.has(
      k = strs[i]
        .split('')
        .sort()
        .join('')
    ) ? h.get(k).push(strs[i])
      : h.set(k, [strs[i]])
  }
  return Array.from(h.values())
};

guessNumber 猜数字大小

输入：n = 10, pick = 6
输出：6

输入：n = 1, pick = 1
输出：1

输入：n = 2, pick = 1
输出：1

var guessNumber = function (n) {
  let left = 1;
  let right = n;
  // 循环直至区间左右端点相同
  while (left < right) {
    const mid = Math.floor(
      left + (right - left) / 2
    );
    if (guess(mid) <= 0) {
      // 答案在区间 [left, mid] 中
      right = mid;    
    } else {
      // 答案在区间 [mid+1, right] 中
      left = mid + 1; 
    }
  }
  // 此时有 left == right
  // 区间缩为一个点，即为答案
  return left;
};

hammingDistance 汉明距离

输入：x = 1, y = 4
输出：2

输入：x = 3, y = 1
输出：1

var hammingDistance = function (x, y) {
  x = x.toString(2);
  y = y.toString(2);
  let maxLength = Math.max(
    x.length, y.length);
  x = x.padStart(maxLength, 0);
  y = y.padStart(maxLength, 0);
  let ans = 0;
  for (let i = 0;
    i < maxLength; i++) {
    if (x[i] !== y[i]) ans++;
  }
  return ans;
};

hammingWeight 位1的个数

输入：n = 11
输出：3

输入：n = 128
输出：1

输入：n = 2147483645
输出：30

// 技巧就是把一个整数减去 1
// 再和原整数做与运算
// 会把该整数最右边的 1 变成 0
var hammingWeight = function (n) {
  let index = 0;
  while (n) {
    ++index
    // 去掉最后一位的 1 然后不断的操作
    // 判断消掉多少次
    n = n & (n - 1)
  }
  return index
};

hasCycle 环形链表

输入：head = [3,2,0,-4], pos = 1
输出：true

输入：head = [1,2], pos = 0
输出：true

输入：head = [1], pos = -1
输出：false

var hasCycle = function (head) {
  let p1 = head
  let p2 = head
  while (p1 && p2) {
    p1 = p1.next
    p2 = p2.next?.next
    if (p1 === p2) {
      return true
    }
  }
  return false
};

hasPathSum 路径总和（二叉树）

输入：root = [5,4,8,11,null,13,4,7,2,null,null,null,1], targetSum = 22
输出：true

输入：root = [1,2,3], targetSum = 5
输出：false

输入：root = [], targetSum = 0
输出：false

var hasPathSum = function (root, targetSum) {
  if (!root) return false
  let result = false
  const dfs = (node, sum) => {
    if (!node.left
      && !node.right
      && sum === targetSum
    ) {
      result = true
    }
    node.left && dfs(
      node.left,
      sum + node.left.val
    )
    node.right && dfs(
      node.right,
      sum + node.right.val
    )
  }
  dfs(root, root.val)
  return result
};

hIndex H 指数

输入：citations = [3,0,6,1,5]
输出：3

输入：citations = [1,3,1]
输出：1

var hIndex = function (citations) {
  const n = citations.length;
  const cnt = Array(n + 1).fill(0);
  for (const c of citations) {
    cnt[Math.min(c, n)]++; // 引用次数 > n，等价于引用次数为 n
  }
  let s = 0;
  for (let i = n; ; i--) {
    // i=0 的时候，s>=i 一定成立
    s += cnt[i];
    if (s >= i) {
      // 说明有至少 i 篇论文的引用次数至少为 i
      return i;
    }
  }
};
// 时间复杂度：O(n)，其中 n 为 citations 的长度。
// 空间复杂度：O(n)。

increasingTriplet 递增的三元子序列

输入：nums = [1,2,3,4,5]
输出：true

输入：nums = [5,4,3,2,1]
输出：false

输入：nums = [2,1,5,0,4,6]
输出：true

var increasingTriplet = function (nums) {
  const n = nums.length;
  if (n < 3) {
    return false;
  }
  const leftMin =
    new Array(n).fill(0);
  leftMin[0] = nums[0];
  for (let i = 1; i < n; i++) {
    leftMin[i] = Math.min(
      leftMin[i - 1], nums[i]
    );
  }
  const rightMax =
    new Array(n).fill(0);
  rightMax[n - 1] = nums[n - 1];
  for (let i=n-2; i >= 0; i--) {
    rightMax[i] =
      Math.max(
        rightMax[i + 1], nums[i]
      );
  }
  for (let i=1; i < n - 1; i++) {
    if (nums[i] > leftMin[i - 1]
      && nums[i] < rightMax[i+1]
    ) {
      return true;
    }
  }
  return false;
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

inorderTraversal 二叉树的中序遍历

输入：root = [1,null,2,3]
输出：[1,3,2]

输入：root = []
输出：[]

输入：root = [1]
输出：[1]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

// 递归解法
const inorderTraversal = function (root) {
  const result = []
  const inorder = node => {
    if (!node) return
    inorder(node.left)
    result.push(node.val)
    inorder(node.right)
  }
  inorder(root)
  return result
};

// 非递归解法
const inorderTraversal = function (root) {
  const result = [];
  const stack = [];
  // 能压栈的左子节点都压进来
  while (root) {        
    stack.push(root);
    root = root.left;
  }
  while (stack.length) {
    // 栈顶的节点出栈
    let curNode = stack.pop();
    // 在压入右子树前处理它的数值部分
    result.push(curNode.val);
    // 获取它的右子树
    curNode = curNode.right;
    // 右子树存在，执行 while 循环   
    while (curNode) {
      // 压入当前 root
      stack.push(curNode);
      // 不断压入左子节点
      curNode = curNode.left;
    }
  }
  return result;
};

invertTree 翻转二叉树

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]

输入：root = [2,1,3]
输出：[2,3,1]

输入：root = []
输出：[]

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

isAnagram 有效的字母异位词

输入: s = "anagram", t = "nagaram"
输出: true

输入: s = "rat", t = "car"
输出: false

var isAnagram = function (s, t) {
  const cnt = Array(26).fill(0);
  for (const c of s) {
    cnt[c.charCodeAt(0) - "a".charCodeAt(0)]++;
  }
  for (const c of t) {
    cnt[c.charCodeAt(0) - "a".charCodeAt(0)]--;
  }
  return cnt.every((c) => c === 0);
};

isHappy 快乐数

输入：n = 19
输出：true

输入：n = 2
输出：false

const isHappy = n => {
  let set = new Set(), sum
  n += ''
  while (sum !== 1) {
    sum = 0
    for (let i = 0;
      i < n.length; i++) {
      sum += n[i] * n[i]
    }
    n = sum + ''
   // 利用 set.has() 判断重复
   if (set.has(sum)) return false
    set.add(sum)
  }
  return true
}

isIsomorphic 同构字符串

输入：s = "egg", t = "add"
输出：true

输入：s = "foo", t = "bar"
输出：false

输入：s = "paper", t = "title"
输出：true

var isIsomorphic = function (s, t) {
  for (let i = 0; i < s.length; i++)
    if (s.indexOf(s[i]) !== t.indexOf(t[i])) {
      return false;
    }
  return true;
};

isMatch 正则表达式匹配

输入：s = "aa", p = "a"
输出：false

输入：s = "aa", p = "a*"
输出：true

输入：s = "ab", p = ".*"
输出：true

var isMatch = function (s, p) {
  let getIsMactch = (s, p) => {
  // 如果传入 p 的长度为 0
  // 则 s 长度也为 0 才返回 true
    if (p.length === 0) {
      return !s.length
    }
    // 判断第一个字符是否相等
    let match = false
    if (s.length > 0
      && (s[0] === p[0]
      || p[0] === '.')
    ) {
      match = true
    }
    // p 有模式的
    if (p.length > 1
      && p[1] === "*") {
// 第一种情况：
// s* 匹配 0 个字符
// 第二种情况：
// s* 匹配 1 个字符
// 递归下去用来表示 s* 匹配多个 s*
      return getIsMactch(
        s, p.slice(2)
      ) || (
        match &&
        getIsMactch(
          s.slice(1), p
        )
      )
    } else {
      return (match &&
        getIsMactch(
          s.slice(1),
          p.slice(1)
        )
      )
    }
  }
  return getIsMactch(s, p)
};

isMatch 通配符匹配

输入：s = "aa", p = "a"
输出：false

输入：s = "aa", p = "*"
输出：true

输入：s = "cb", p = "?a"
输出：false

var isMatch = function (s, p) {
  const m = s.length, n = p.length
  // 状态定义：dp[i][j] 表示 s 的
  // 前i个字符和p的前 j 个字符是否匹配
  const dp = new Array(m + 1)
    .fill(false).map(
      () => new Array(n + 1)
        .fill(false)
    )
  // 状态初始化
  // 1. 空字符串和空字符串是匹配的
  dp[0][0] = true
  for (let i = 1; i <= n; i++) {
    // 3. 空字符串和 * 是匹配的
    if(dp[0][i-1] && p[i-1]=='*'){
      dp[0][i] = true
    }
  }
  // 状态转移
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (s[i - 1] == p[j - 1]
          || p[j - 1] == '?') {
        dp[i][j]=dp[i - 1][j - 1]
      } else if (p[j - 1] == '*'){
        dp[i][j] = dp[i][j - 1]
          || dp[i - 1][j]
      }
    }
  }
  return dp[m][n]
};

isPalindrome 回文链表

输入：head = [1,2,2,1]
输出：true

输入：head = [1,2]
输出：false

// 遍历一遍，把值放入数组中
// 然后用双指针判断是否回文
var isPalindrome = function(head) {
  const vals = [];
  // 丢进数组里
  while (head) {
    vals.push(head.val);
    head = head.next;
  }
  // 双指针
  let start = 0,
      end = vals.length - 1;
  while (start < end) {
    // 理应相同，如果不同，不是回文
    if (vals[start] != vals[end]) {
      return false;
    }
    start++;
    // 双指针移动
    end--;
  }
// 循环结束也没有返回 false，说明是回文
  return true;
};

isPalindrome 验证回文串

输入: s = "A man, a plan, a canal: Panama"
输出：true

输入：s = "race a car"
输出：false

输入：s = " "
输出：true

var isPalindrome = function (s) {
  // valid为进行正则匹配后筛选出的数组
  const valid = s.toLowerCase()
    .match(/[a-z0-9]+/g);
  if (!valid) {
    return true;
  }
  // 数据预处理(正则匹配)后得到的字符串
  const str = valid.join("");
  // 将字符串翻转
  const comp = str.split("")
    .reverse().join("");
  return comp === str;
};

validPalindrome 验证回文串 II

输入：s = "aba"
输出：true

输入：s = "abca"
输出：true

输入：s = "abc"
输出：false

function isPali(str, l, r) {
  // 判断str是否回文
  while (l < r) {
    if (str[l] != str[r]) {
      // 指向的字符不一样，不是回文串
      return false;
    }
    l++; // 指针相互逼近
    r--;
  }
  return true; // 始终没有不一样，返回true
}

var validPalindrome = function (str) {
  let l = 0,
    r = str.length - 1; // 头尾指针
  while (l < r) {
    if (str[l] != str[r]) {
      // 指向的字符不一样，还不能死刑
      return isPali(str, l + 1, r)
        || isPali(str, l, r - 1); //转为判断删掉一个字符后，是否回文
    }
    l++;
    r--;
  }
  return true;
};

isSameTree 相同的树（二叉树）

输入：p = [1,2,3], q = [1,2,3]
输出：true

输入：p = [1,2], q = [1,null,2]
输出：false

输入：p = [1,2,1], q = [1,1,2]
输出：false

var isSameTree = function (p, q) {
  if (p === null || q === null) {
    return p === q; // 必须都是 null
  }
  return (
    p.val === q.val &&
    isSameTree(p.left, q.left) &&
    isSameTree(p.right, q.right)
  );
};

// 时间复杂度：O(min(n,m))，其中 n 为 p 的节点个数，m 为 q 的节点个数。
// 空间复杂度：O(min(n,m))

isSubsequence 判断子序列

输入：s = "abc", t = "ahbgdc"
输出：true

输入：s = "axc", t = "ahbgdc"
输出：false

// 双指针
var isSubsequence = function(s, t) {
  if (s.length == 0) return true;
  let index = 0;
  let subIndex = 0;
  while (index < t.length) {
    if (s[subIndex] == t[index]) {
      subIndex++;
      if (subIndex > s.length - 1) {
        return true;
      }
    }
    index++;
  }
  return false;
};

// 时间复杂度：O(n)

isSymmetric 对称二叉树

输入：root = [1,2,2,3,4,4,3]
输出：true

输入：root = [1,2,2,null,3,null,3]
输出：false

var isSymmetric = function (root) {

const check = (left, right) => {
  // 两个子树都为 null 时对称
  if (left == null &&
    right == null) {
    return true;
  }
  // 两个子树都存在时需要：
  // root 值相同
  // 且他们的子树也满足镜像
  if (left && right) {
    return left.val == right.val
      && check(
        left.left, right.right
      )
      && check(
        left.right, right.left
      );
  }
  // 一个子树存在一个不存在
  // 肯定不对称
  return false;
};
// 如果传入的 root 就是 null 则对称
  if (root == null) {
    return true;
  }
// 否则判断它的左右子树是否满足对称
  return check(
    root.left, root.right
  );
};

isValid 有效的括号

输入：s = "()"
输出：true

输入：s = "()[]{}"
输出：true

var isValid = function (s) {
  if (s.length % 2 !== 0) {
    return false
  }
  const arr = s.split('')
  const stack = []

  for (let i = 0, len = arr.length; i < len; i++) {
    if (['(', '[', '{']
      .includes(arr[i])
    ) {
      stack.push(arr[i])
    } else {
const top =
  stack[stack.length - 1]
      if (
top === '(' && arr[i] === ')' ||
top === '[' && arr[i] === ']' ||
top === '{' && arr[i] === '}'
      ) {
        stack.pop()
      } else {
        return false
      }
    }
  }

  if (stack.length > 0) {
    return false
  }

  return true
};

checkValidString 有效的括号字符串

输入：s = "()"
输出：true

输入：s = "(*)"
输出：true

输入：s = "(*))"
输出：true

var checkValidString = function (s) {
  let stack = [];
  for (let i = 0; i < s.length; i++) {
    if (s[i] === "*" || s[i] === "(") {
      stack.push(s[i]);
    } else {
      // 检测到右括号创建临时存储
      let helper = [];
      // 如果是*则全部存起来 优先用左括号进行匹配
      while (stack[stack.length - 1] === "*") {
        helper.push(stack.pop());
      }
      // 当栈内全空的情况下说明没有匹配到左括号
      if (stack.length === 0) {
        // 此时使用*
        if (!helper.length) return false;
        helper.pop();
        // 匹配到了左括号
      } else {
        stack.pop();
      }
      // 将*放回去
      while (helper.length) {
        stack.push(helper.pop());
      }
    }
  }
  // 对剩余元素进行比较(左括号剩余情况)
  let starCount = 0;
  while (stack.length) {
    // 不难发现如果左括号前没有*的话就不能匹配成功
    if (stack.pop() === "*") {
      starCount++;
    } else {
      // 此时说明没有多余的*了
      if (starCount === 0) {
        return false;
      } else {
        starCount--;
      }
    }
  }
  return true;
};

isValidBST 验证二叉搜索树

输入：root = [2,1,3]
输出：true

输入：root = [5,1,4,null,null,3,6]
输出：false

var isValidBST = function (root) {
  let preVal = -Infinity,
    flag = true;
  // 递归的中序遍历
  const inorder = (root) => {
    // 如果已经不是二叉搜索树了
    // 就没有必要再递归下去了
    if (!flag) return;
    // 当前是空节点
    if (root == null) return;
    // 先左 根 右
    inorder(root.left);
    if (root.val <= preVal) {
      // 当前节点的值
      // 小于或等于上一个节点的值
      // 肯定不是二叉搜索树
      flag = false;
      return;
    }
    // 根的时候把当前节点的值
    // 赋值 preVal 方便下次处理
    preVal = root.val;
    inorder(root.right);
  };
  inorder(root);
  return flag;
};

isValidSudoku 有效的数独

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

var isValidSudoku = function (board) {
  // 步骤 1：初始化横、纵以及小九宫格
  const rows = [],
    columns = [],
    boxes = [];
  for (let i = 0; i < 9; i++) {
    rows[i] = [];
    columns[i] = [];
    boxes[i] = [];
  }
  // 对应的 rows 为
  // [[],[],[],[],[],[],[],[],[]]
  // 步骤 2：遍历填充值
  for (let i = 0; i < 9; i++) {
    for (let j = 0; j < 9; j++) {
      // 获取值
      const value = board[i][j];
      // 先判断非 . 元素
      if (value !== '.') {
// 检验横排
if (!rows[i].includes(value)) {
  rows[i].push(value);
} else {
  return false;
}
// 检验竖排
if (!columns[j].includes(value)) {
  columns[j].push(value);
} else {
  return false;
}
        // 检查盒子
        const boxIndex =
          Math.floor(i / 3) * 3 +
          Math.floor(j / 3);
        if (!boxes[boxIndex]
          .includes(value)) {
          boxes[boxIndex]
            .push(value);
        } else {
          return false;
        }
      }
    }
  }
  // 步骤 3：如果没有问题，返回 true
  return true;
};

ladderLength 单词接龙

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
输出：5

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log"]
输出：0

var ladderLength = function(beginWord, endWord, wordList) {
  const wordSet =new Set(wordList);
  const queue = [];
  queue.push([beginWord, 1]);

  while (queue.length) {
    // 当前出列的单词
    const [word, level] =
      queue.shift();
    if (word == endWord) {
      return level;
    }
    // 遍历当前单词的所有字符
    for (let i = 0;
      i < word.length; i++) {
      // 对应 26 个字母
for (let c = 97;
  c <= 122; c++) {
  // 形成新词
  const newWord = word.slice(0, i)
    + String.fromCharCode(c)
    + word.slice(i + 1);
  // 单词表里有这个新词
  if (wordSet.has(newWord)) {
    // 作为下一层的词入列
    queue.push([newWord, level+1]);
    // 避免该词重复入列
    wordSet.delete(newWord);
  }
}
    }
  }
  // bfs 结束，始终没有遇到终点
  return 0;
};

longestCommonPrefix 最长公共前缀

输入：strs = ["flower","flow","flight"]
输出："fl"

输入：strs = ["dog","racecar","car"]
输出：""

var longestCommonPrefix = function (strs) {
  var re = "";
  if (!strs.length) {
    return re;
  }
  for (var j = 0; j < strs[0].length; j++) {
    //第j位
    for (var i = 1; i < strs.length; i++) {
      //第i个
      if (strs[i][j] != strs[0][j]) {
        return re;
      }
    }
    re += strs[0][j];
  }
  return re;
};

largestNumber 最大数

输入：nums = [10,2]
输出："210"

输入：nums = [3,30,34,5,9]
输出："9534330"

// 组成的字符串长度无论如何拼接是固定的
// 思路是将原数组排序
// 前面的位置的数字尽可能大
// 做一个特殊的降序排列
// a + b 与 b + a 比较 (类型隐式转换)
var largestNumber = function (nums) {
  const res = nums.sort(
    (a, b) => (b+''+a) - (a+''+b)
  ).join('')
  return res.startsWith('0')
    ? '0' : res
};
// 时间复杂度：O(nlogn)
// 空间复杂度：O(n)

largestRectangleArea 柱状图中最大的矩形

输入：heights = [2,1,5,6,2,3]
输出：10

输入： heights = [2,4]
输出： 4

// 单调递增栈存放数组下标
// 因为这样可以从栈顶找到
// 左边第一个比自己小的下标
// 这样从当前下标出发到
// 第一个比自己小的柱子的下标
// 就是矩形面积的宽度
// 然后在乘当前柱子的高度就是面积
// 如果当前柱子大于
// 栈顶的下标对应的柱子高度就入栈
// 否则不断出栈
// 计算栈顶的柱子所能形成的矩形面积
// 然后更新最大矩形面积
var largestRectangleArea = function (heights) {
  let maxArea = 0
  const stack = []
  // 前后增加两个哨兵
  // 用来清零单调递增栈里的元素   
  heights = [0, ...heights, 0]
  for (
    let i = 0;
    i < heights.length;
    i++
  ) {
    // 当前元素对应的高度小于
    // 栈顶元素对应的高度时
    while (
      heights[i] <
      heights[
        stack[stack.length - 1]
      ]
    ) {
// 出栈
const stackTopIndex = stack.pop()
// 计算面积 并更新最大面积
maxArea = Math.max(
  maxArea,
  // 高乘宽
  heights[stackTopIndex] * (
    i -
    stack[stack.length - 1] - 1
  )
)
    }
    // 当前下标加入栈
    stack.push(i)
  }
  return maxArea
}

lengthOfLastWord 最后一个单词的长度

输入：s = "Hello World"
输出：5

输入：s = "   fly me   to   the moon  "
输出：4

输入：s = "luffy is still joyboy"
输出：6

var lengthOfLastWord = function (s) {
  let end = s.length - 1;

  while (end >= 0 && s[end] == " ") {
    end--;
  }
  if (end < 0) return 0;
  let start = end;

  while (start >= 0 && s[start] != " ") {
    start--;
  }
  return end - start;
};

lengthOfLIS 最长递增子序列

输入：nums = [10,9,2,5,3,7,101,18]
输出：4

输入：nums = [0,1,0,3,2,3]
输出：4

输入：nums = [7,7,7,7,7,7,7]
输出：1

var lengthOfLIS = function (nums) {
  // 每堆的堆顶
  const top = [];
  // 牌堆数初始化为 0
  let piles = 0;
  for (let i = 0;
    i < nums.length; i++) {
    // 要处理的扑克牌
    let poker = nums[i];
    // 左堆和最右堆进行二分搜索
    // 因为堆顶是有序排的
    // 最终找到该牌要插入的堆
    let left = 0,
        right = piles;
    // 搜索区间是左闭右开
    while (left < right) {
      // >> 1 相当于除以2向下取整
      let mid = left + (
        (right - left) >> 1
      );
      if (top[mid] > poker) {
        right = mid;
    } else if (top[mid] < poker) {
        left = mid + 1;
      } else {
        right = mid;
      }
    }
    //  没找到合适的牌堆，新建一堆
    if (left == piles) piles++;
    // 把这张牌放到堆顶
    top[left] = poker;
  }
  return piles;
};

lengthOfLongestSubstring 无重复字符的最长子串

输入: s = "abcabcbb"
输出: 3

输入: s = "bbbbb"
输出: 1

输入: s = "pwwkew"
输出: 3

var lengthOfLongestSubstring = function (s) {
  let maxLen = 0
  const arr = s.split('')
  for (let i = 0, len = arr.length;
       i < len; i++) {
    let curStr = arr[i]
  for (let j = i + 1; j < len; j++) {
    if (!curStr.includes(arr[j])) {
      curStr += arr[j]
    } else {
      break
    }
  }
    if (curStr.length > maxLen) {
      maxLen = curStr.length
    }
  }
  return maxLen
};

intToRoman 整数转罗马数字

输入：num = 3749
输出： "MMMDCCXLIX"

输入：num = 58
输出："LVIII"

输入：num = 1994
输出："MCMXCIV"

const R = [
  ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"], // 个位
  ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"], // 十位
  ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"], // 百位
  ["", "M", "MM", "MMM"], // 千位
];

var intToRoman = function (num) {
  return (
    R[3][Math.floor(num / 1000)] +
    R[2][Math.floor(num / 100) % 10] +
    R[1][Math.floor(num / 10) % 10] +
    R[0][num % 10]
  );
};
// 时间复杂度：O(1)
// 空间复杂度：O(1)

longestSubstring 至少有 K 个重复字符的最长子串

输入：s = "aaabb", k = 3
输出：3

输入：s = "ababbc", k = 2
输出：5

var longestSubstring = function (s, k) {
  if (k <= 1) { return s.length; }
  else if (s.length < k) {
    return 0;
  }
  const map = {};
  // 计算每种字符出现次数
  for (let i = 0;
    i < s.length; i += 1) {
    map[s[i]] ? map[s[i]] += 1 :
      map[s[i]] = 1;
  }
  // 收集不满足的字符
  const keys = [];
  for (key in map) {
    if (map[key] < k) {
      keys.push(key);
    }
  }
  return keys[0]
    ? Math.max(// 分割求最大
      ...s.split(new RegExp(
        keys.join('|'), 'g')
      ).map(x =>
        longestSubstring(x, k)
      )
    )
    : s.length;
};

leastBricks 砖墙

输入：wall = [[1,2,2,1],[3,1,2],[1,3,2],[2,4],[3,1,2],[1,3,1,1]]
输出：2

输入：wall = [[1],[1],[1]]
输出：3

var leastBricks = function (wall) {
  const cnt = new Map();
  for (const widths of wall) {
    const n = widths.length;
    let sum = 0;
    for (let i=0; i<n-1; i++) {
      sum += widths[i];
      cnt.set(sum,
        (cnt.get(sum) || 0) + 1
      );
    }
  }
  let maxCnt = 0;
  for (
    const [_, c] of cnt.entries()
  ) {
    maxCnt = Math.max(maxCnt, c);
  }
  return wall.length - maxCnt;
};

leastInterval 任务调度器

输入：tasks = ["A","A","A","B","B","B"], n = 2
输出：8

输入：tasks = ["A","C","A","B","D","B"], n = 1
输出：6

输入：tasks = ["A","A","A","B","B","B"], n = 3
输出：10

function leastInterval(tasks, n) {
  let arr = Array(26).fill(0);
  for (let c of tasks) {
    //统计各个字母出现的次数
    arr[c.charCodeAt() -
      "A".charCodeAt()]++;
  }
  let max = 0;
  for (let i = 0; i < 26; i++) {
    //找到最大次数
    max = Math.max(max, arr[i]);
  }
  //计算前n-1行n的间隔的时间大小
  let ret = (max - 1) * (n + 1); 
  for (let i = 0; i < 26; i++) {
//计算和最大次数相同的字母数 累加进ret
    if (arr[i] == max) {
      ret++;
    }
  }
  //在tasks的长度和ret中取较大的一个
  return Math.max(
    ret, tasks.length);
}

letterCombinations 电话号码的字母组合

输入：digits = "23"
输出：["ad","ae","af","bd","be","bf","cd","ce","cf"]

输入：digits = ""
输出：[]

输入：digits = "2"
输出：["a","b","c"]

var letterCombinations = function (digits) {
  const strList = [
    [],
    [],
    ['a', 'b', 'c'],
    ['d', 'e', 'f'],
    ['g', 'h', 'i'],
    ['j', 'k', 'l'],
    ['m', 'n', 'o'],
    ['p', 'q', 'r', 's'],
    ['t', 'u', 'v'],
    ['w', 'x', 'y', 'z']
  ]
  if (digits.length >= 2) {
    let resultArr = []
    // 递归函数
    const handle = (arr) => {
      if (arr.length >= 2) {
        const addArr = []
        arr[0].map(item1 => {
          arr[1].map(item2 => {
            addArr.push(
              item1 + item2
            )
          })
        })
        arr.splice(0, 2, addArr)
        const newArr = arr
        handle(newArr)
      } else {
        resultArr = arr[0]
      }
    }
const strArr = []
const digitsArr = digits.split('')
digitsArr.map(item => {
  const curNum = Number(item)
  strArr.push(strList[curNum])
})
    handle(strArr)
    return resultArr
  } else if (digits.length = 1) {
    return strList[Number(digits)]
  } else {
    return []
  }
};

levelOrder 二叉树的层序遍历

输入：root = [3, 9, 20, null, null, 15, 7]
输出：[[3], [9, 20], [15, 7]]

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

const levelOrder = function (root) {
  const result = [];
  const queue = [];
  if (root) queue.push(root);
  while (queue.length) {
    // 记录当前层级节点数
    const len = queue.length;
    // 存放每一层的节点
    const curArr = [];
  for (let i = 0; i < len; i++) {
    const curNode = queue.shift();
    curArr.push(curNode.val);
    // 存放当前层下一层的节点
    curNode.left &&
      queue.push(curNode.left);
    curNode.right &&
      queue.push(curNode.right);
  }
    // 把每一层的结果放到结果数组
    result.push(curArr);
  }
  return result;
};

levelOrder 从上到下打印二叉树

var levelOrder = function(root) {
  if (!root) return [];
  // 创建队列，并将根节点入队
  const queue = [root];
  const res = [];
  while (queue.length) {
    // 获取根节点，根节点出队
    const n = queue.shift();
    // 访问队头
    res.push(n.val);
    // 队头的子节点依次入队
    n.left && queue.push(n.left);
    n.right &&queue.push(n.right);
  }
  return res;
};

levelOrder 从上到下打印二叉树 II

var levelOrder = function (root) {
  const ret = [];
  if (!root) {
    return ret;
  }
  const q = [];
  q.push(root);
  while (q.length !== 0) {
    const curSize = q.length;
    ret.push([]);
    for (let i = 1;
    i <= curSize; i++) {
const n = q.shift();
ret[ret.length - 1].push(n.val);
if (n.left) q.push(n.left);
if (n.right) q.push(n.right);
    }
  }
  return ret;
};

levelOrder 从上到下打印二叉树 III

var levelOrder = function (root) {
  if (!root) return []
  const queue = [[root, 0]],
        res = []
  while (queue.length) {
    const [node, lev] =
      queue.shift()
    // 初始化当前层
    if (!res[lev]) res[lev] = []
    // 奇数层 逆序 1 3 5 偶数层 正序 0 2 4
    lev & 1 ?
      res[lev].unshift(node.val)
      : res[lev].push(node.val)
node.left &&
  queue.push([node.left, lev+1])
node.right &&
  queue.push([node.right, lev+1])
  }
  return res
};

longestConsecutive 最长连续序列

输入：nums = [100,4,200,1,3,2]
输出：4

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9

输入：nums = [1,0,1,2]
输出：3

// 从小到大排序
// 遍历数组，比较相邻的两项
// 否则，说明连续情况发生中断，将 count 重置为 1
var longestConsecutive = (nums) => {
  if (nums.length === 0) return 0
  nums.sort((a, b) => a - b)
  let max = 1
  let count = 1
  for (
    let i = 0;
    i < nums.length - 1;
    i++
  ) {
    let cur = i, next = i + 1
    // 相同就跳过本次循环
    if (nums[cur] === nums[next]) {
      continue
    }
    // 如果 当前项+1 等于 下一项
    // 说明遇到连续项 count++
    if (
      nums[cur] + 1 === nums[next]
    ) {
      count++
    } else {
      // 否则，说明连续情况发生中断
      // 将 count 重置为 1
      count = 1
    }
    max = Math.max(max, count)
  }
  return max
}

longestIncreasingPath 矩阵中的最长递增路径

输入：matrix = [[9,9,4],[6,6,8],[2,1,1]]
输出：4 

输入：matrix = [[3,4,5],[3,2,6],[2,2,1]]
输出：4 

输入：matrix = [[1]]
输出：1

const dx = [0, 1, 0, -1];
// 0和1、1和0、0和-1、-1和0，四个方向
const dy = [1, 0, -1, 0];
var longestIncreasingPath = function(matrix) {
  // 矩阵中没有元素
  if(matrix.length===0) return 0;
  const m = matrix.length;
  const n = matrix[0].length;
  const memo = new Array(m);
  for (let i = 0; i < m; i++) {
    memo[i] = new Array(n);
  }
  // 路径长度至少为1
  let res = 1;
  for (let i = 0; i < m; i++) {
    // 对坐标(i,j)进行dfs
    for (let j = 0; j < n; j++) {
      res = Math.max(res, dfs(
        matrix, i, j, m, n, memo
      ));
    }
  }
  return res;
};
const dfs = (
  matrix, i, j, m, n, memo
) => {
  if(memo[i][j])return memo[i][j];
  // 以(i,j)为起点的路径，长度保底是1
  let max = 1;
  for (let k = 0; k < 4; k++) {
    const x = i + dx[k];
    // 新的坐标
    const y = j + dy[k];
    if (x >= 0 && x < m && y >= 0
      && y < n &&
      matrix[x][y] > matrix[i][j]
    ) {
      max = Math.max(
        max,
        1 + dfs(
         matrix, x, y, m, n, memo
        )
      );
    }
  }
  return memo[i][j] = max;
};

longestPalindrome 最长回文子串

输入：s = "babad"
输出："bab"

输入：s = "cbbd"
输出："bb"

// 中心扩散法
var longestPalindrome = function (s) {
  if (s.length < 2) {
    return s
  }
  let res = ''
function helper(m, n) {
  while (m >= 0
    && n < s.length
    && s[m] == s[n]
  ) {
    m--
    n++
  }
  // 注意此处 m,n 的值循环完后
  // 是恰好不满足循环条件的时刻
  // 此时 m 到 n 的距离为 n-m+1
  // 但 mn 两个边界不能取
  // 所以应该取 m+1 到 n-1 的区间
  // 长度是 n-m-1
  if (n - m - 1 > res.length) {
// slice 也要取 [m+1,n-1] 这个区间 
    res = s.slice(m + 1, n)
  }
}
  for (let i = 0; i < s.length; i++) {
    // 回文子串长度是奇数
    helper(i, i)
    // 回文子串长度是偶数
    helper(i, i + 1)
  }
  return res
};

longestValidParentheses 最长有效括号

输入：s = "(()"
输出：2

输入：s = ")()())"
输出：4

输入：s = ""
输出：0

var longestValidParentheses = function (s) {
  let maxLen = 0;
  const stack = [];
  stack.push(-1);
  for (
    let i = 0;
    i < s.length;
    i++
  ) {
    const c = s[i];
    if (c == '(') {
      // 左括号的索引，入栈
      stack.push(i);
    } else {
      // 遍历到右括号
      // 栈顶的左括号被匹配，出栈
      stack.pop();
      // 栈非空
      if (stack.length) {
        // 计算有效连续长度
const curMaxLen = 
i - stack[stack.length - 1];
// 挑战最大值
maxLen =
Math.max(maxLen, curMaxLen);
      } else {
        // 栈空了
        // 入栈充当参照
        stack.push(i);
      }
    }
  }
  return maxLen;
};

lowestCommonAncestor 二叉树的最近公共祖先

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出：3

输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出：5

var lowestCommonAncestor = function(root, p, q) {
  // LCA -> 最近公共祖先
  // 遇到 null，返回 null 没有 LCA
  if (root == null) {
    return null;
  }
  // 遇到 p 或 q，直接返回当前节点
  if (root == q || root == p) {
    return root;
  }
  // 非 null 非 q 非 p，则递归左右子树
  const left =
    lowestCommonAncestor(
      root.left, p, q
    );
  const right =
    lowestCommonAncestor(
      root.right, p, q
    );
  // 根据递归的结果，决定谁是 LCA
  if (left && right) {
    return root;
  }
  if (left == null) {
    return right;
  }
  return left;
};

LRUCache LRU 缓存

输入:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, null, -1, 3, 4]

var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.map = new Map();
};

LRUCache.prototype.get = function (key) {
  if (this.map.has(key)) {
    const temp = this.map.get(key)
    this.map.delete(key);
    this.map.set(key, temp);
    return temp
  } else {
    return -1
  }
};

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
  ) {
    this.map.delete(
      this.map.keys().next().value
    );
  }
};

kthSmallest 二叉搜索树中第K小的元素

输入：root = [3,1,4,null,2], k = 1
输出：1

输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

var kthSmallest = function (root, k) {
  const stack = [];
  while (root != null ||
    stack.length) {
    while (root != null) {
      stack.push(root);
      root = root.left;
    }
    root = stack.pop();
    --k;
    if (k === 0) {
      break;
    }
    root = root.right;
  }
  return root.val;
};
// H 是树的高度
// 时间复杂度：O(H+k)
// 空间复杂度：O(H)

kthSmallest 有序矩阵中第 K 小的元素

输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
输出：13

输入：matrix = [[-5]], k = 1
输出：-5

var kthSmallest = function(matrix, k) {
  const count = (arr, tgt) => {
    let res = 0,
      right = arr[0].length;
    for (let i = 0;
      i < arr.length; i++) {
      for (let j = 0;
        j < right; j++) {
        if (arr[i][j] > tgt) {
          right = j;
          break;
        } else {
          res++;
        }
      }
    }
    return res;
  };
  let min = matrix[0][0],
      max = matrix[
        matrix.length - 1
      ][
        matrix[0].length - 1
      ];
  while (min <= max) {
    let mid = Math.floor(
      (min + max) / 2
    );
    let cn = count(matrix, mid);
    if (cn >= k) {
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }
  return min;
};

majorityElement 多数元素

输入：nums = [3,2,3]
输出：3

输入：nums = [2,2,1,1,1,2,2]
输出：2

var majorityElement = function (nums) {
  nums.sort((a, b) => a - b);
  return nums[
    Math.floor(nums.length / 2)
  ];
};

maxArea 盛最多水的容器

输入：[1,8,6,2,5,4,8,3,7]
输出：49 

输入：height = [1,1]
输出：1

var maxArea = function (height) {
  let max = 0;
  // 双指针 i j 循环 height 数组
  for (let i = 0,
       j = height.length - 1;
       i < j;
  ) { 
    // i j 较小的那个先向内移动
    // 如果高的指针先移动
    // 那肯定不如当前的面积大
    const minHeight =
      height[i] < height[j] ?
      height[i++] :
      height[j--];
    // 计算面积
    const area =
      (j - i + 1) * minHeight;
    // 更新最大面积
    max = Math.max(max, area);
  }
  return max;
};

maxCoins 戳气球

输入：nums = [3,1,5,8]
输出：167

输入：nums = [1,5]
输出：10

var maxCoins = function (nums) {
  nums.unshift(1)
  nums.push(1)
  let len = nums.length
  let dp = Array.from(
    { length: len },
    () => new Array(len).fill(0)
  )
  // 默认填充的 1 不能被戳破
  // 则 i 的边界为 len-2-1
  // i < j, 则 i 最大为 len-1
  // 去除默认则未 len-2-1
  for (let i = len - 3;
    i >= 0; i--) {
// i<j,则j最小为 i，去除默认则未 i+1
    for (let j = i + 2;
      j < len; j++) {
      for (let k = i + 1;
        k < j; k++) {
        dp[i][j] = Math.max(
dp[i][j],
dp[i][k] +
nums[i] * nums[k] * nums[j] +
dp[k][j]
        )
      }
    }
  }
  return dp[0][len - 1]
}

maxDepth 括号的最大嵌套深度

输入：s = "(1+(2*3)+((8)/4))+1"
输出：3

输入：s = "(1)+((2))+(((3)))"
输出：3

输入：s = "()(())((()()))"
输出：3

var maxDepth = function (s) {
  var stack = [];
  var maxDep = 0;
  for (var i=0; i<s.length; i++){
    if (s[i] === '(') {
      stack.push(s[i]);
    } else if (s[i] === ')') {
      stack.pop();
    }
    maxDep = Math.max(
      maxDep, stack.length
    );
  }
  return maxDep;
};

maxDepth 二叉树的最大深度

输入：root = [3, 9, 20, null, null, 15, 7]
输出：3

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

// DFS 解法
var maxDepth = function (root) {
  if (!root) return 0
  return Math.max(
    maxDepth(root.left),
    maxDepth(root.right)
  ) + 1
};

// BFS 解法
var maxDepth = function (root) {
  let result = 0;
  const queue = [];
  if (root) queue.push(root);
  while (queue.length) {
    const len = queue.length;
  for (let i = 0; i < len; i++) {
    const curNode = queue.shift();
    curNode.left &&
      queue.push(curNode.left);
    curNode.right &&
      queue.push(curNode.right);
  }
    result += 1;
  }
  return result;
};

maximalRectangle 最大矩形

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：6

输入：matrix = [["0"]]
输出：0

输入：matrix = [["1"]]
输出：1

var maximalRectangle = function (matrix) {
  const len = matrix.length;
  if (len === 0) {
    return 0;
  }
  const n = matrix[0].length;
  const left = new Array(len)
    .fill(0)
    .map(
      () => new Array(n).fill(0)
    );

  for (let i = 0; i < len; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === '1') {
        left[i][j] = (
          j === 0 ?
          0 :
          left[i][j - 1]) + 1;
      }
    }
  }

  let result = 0;
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < n; j++) {
      if (matrix[i][j] === '0') {
        continue;
      }
      let width = left[i][j];
      let area = width;
      for (
        let k = i - 1;
        k >= 0; k--
      ) {
  width = Math.min(
    width, left[k][j]
  );
  area = Math.max(
    area, (i - k + 1) * width
  );
      }
result = Math.max(result, area);
    }
  }
  return result;
};

maximalSquare 最大正方形

输入：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
输出：4

输入：matrix = [["0","1"],["1","0"]]
输出：1

输入：matrix = [["0"]]
输出：0

var maximalSquare = function (matrix) {
  if (!matrix ||
    matrix.length === 0 ||
    matrix[0].length === 0
  ) {
    return 0
  }
  // 1.设一个变量存放最长边
  let maxSide = 0;
  // 长宽
  let row = matrix.length;
  let column = matrix[0].length
  // 2.声明一个数组来存放每个点的最长边
  let dp = []
  for (let i = 0; i < row; i++) {
    dp.push(new Array(column))
  }
  // 3.遍历所有节点
  for (let i = 0;
    i < matrix.length; i++) {
    for (let j = 0;
      j < matrix[i].length; j++) {
      // 如果当前的节点等于 1
      if (matrix[i][j] == '1') {
        // 且该节点的下标是 0 0
        if (i == 0 || j == 0) {
          dp[i][j] = 1
        } else {
          dp[i][j] = Math.min(
            Math.min(
              dp[i - 1][j],
              dp[i][j - 1]
            ),
            dp[i - 1][j - 1]
          ) + 1
        }
      } else {
        dp[i][j] = 0;
      }
      maxSide = Math.max(
        dp[i][j],
        maxSide
      )
    }
  }
  return Math.pow(maxSide, 2)
};

maxPathSum 二叉树中的最大路径和

输入：root = [1,2,3]
输出：6

输入：root = [-10,9,20,null,null,15,7]
输出：42

var maxPathSum = function(root) {
  // 最大路径和
  let maxSum =
  Number.MIN_SAFE_INTEGER;

  const dfs = (root) => {
    // 遍历到 null 节点，收益 0
    if (root == null) {
      return 0;
    }
    // 左子树提供的最大路径和
    const left = dfs(root.left);
    // 右子树提供的最大路径和
    const right = dfs(root.right);
    // 当前子树内部的最大路径和
    const innerMaxSum =
      left + root.val + right;
    // 挑战最大纪录
    maxSum = Math.max(
      maxSum, innerMaxSum
    );
    // 当前子树对外提供的最大和
    const outputMaxSum =
      root.val + Math.max(
        0, left, right
      );

    // 如果对外提供的路径和为负
    // 直接返回0。否则正常返回
    return outputMaxSum < 0 ?
      0 : outputMaxSum;
  };
  dfs(root);
  return maxSum;
};

maxPoints 直线上最多的点数

输入：points = [[1,1],[2,2],[3,3]]
输出：3

输入：points = [[1,1],[3,2],[5,3],[4,1],[2,3],[1,4]]
输出：4

var maxPoints = function (points) {
  const len = points.length;
  if (len === 1) return 1;
  let max = 0;
  for (let i = 0; i < len; i++) {
    let map = new Map();
    const itemI = points[i];
    for (let j = i + 1;
      j < len; j++) {
      const itemJ = points[j];
      let key = null;
if (itemJ[1] - itemI[1] === 0) {
  key = `${itemJ[1]}/0`;
} else {
  key = (itemJ[0] - itemI[0])
      / (itemJ[1] - itemI[1]);
}
      const val = map.has(key) ?
        map.get(key) + 1 : 2
      map.set(key, val);
      max = Math.max(max, val);
    }
  }
  return max;
};

maxProduct 乘积最大子数组

输入: nums = [2,3,-2,4]
输出: 6

输入: nums = [-2,0,-1]
输出: 0

var maxProduct = (nums) => {
  let res = nums[0]
  let prevMin = nums[0]
  let prevMax = nums[0]
  let temp1 = 0, temp2 = 0
  for (let i = 1; i < nums.length; i++) {
// num[i] 是正数，希望乘上前面的最小积
    temp1 = prevMin * nums[i]
// num[i] 是负数，希望乘上前面的最大积
    temp2 = prevMax * nums[i]
    prevMin = Math.min(
      temp1, temp2, nums[i])
    prevMax = Math.max(
      temp1, temp2, nums[i])
    res = Math.max(prevMax, res)
  }
  return res
}
// 时间复杂度 O(n)
// 空间复杂度 O(1)

maxProfit 买卖股票的最佳时机

输入：[7,1,5,3,6,4]
输出：5

输入：prices = [7,6,4,3,1]
输出：0

var maxProfit = function(prices) {
  let max = 0,
      minprice = prices[0]
  for (let i = 1;
    i < prices.length; i++) {
    minprice = Math.min(
      prices[i], minprice
    )
    max = Math.max(
      max, prices[i] - minprice
    )
  }
  return max
}
// 时间复杂度：O(n)
// 空间复杂度：O(1)

maxProfit 买卖股票的最佳时机 II

输入：prices = [7,1,5,3,6,4]
输出：7

输入：prices = [1,2,3,4,5]
输出：4

输入：prices = [7,6,4,3,1]
输出：0

var maxProfit = function (prices) {
  let result = 0;
  let n = prices.length;
  for (let i = 1; i < n; ++i) {
    result += Math.max(
      0, prices[i] - prices[i - 1]
    );
  }
  return result;
};
// 时间复杂度：O(n)
// 空间复杂度：O(1)

maxProfit 最佳买卖股票时机含冷冻期

输入: prices = [1,2,3,0,2]
输出: 3

输入: prices = [1]
输出: 0

var maxProfit = function (prices) {
  // dp[i][0]表示第i天不持有股票
  // dp[i][1]表示第i天持有股票
  const len = prices.length;
  if (len <= 1) return 0;

  if (len == 2 &&
    prices[0] >= prices[1]) {
    return 0;
  }
  else if (len == 2 &&
    prices[0] < prices[1]) {
    return prices[1] - prices[0];
  }
  const dp = [];
  for (let i = 0; i < len; i++) {
    dp.push([]);
    dp[i] = [0, 0]
  }
  // 第一天不持有股票的收益
  dp[0][0] = 0;
  // 第一天持有股票的收益
  //由于第一天只能买入股票因此收益为负数
  dp[0][1] = -prices[0];

  // 第二天不持有股票
  // 或者第一天持有股票并且第二天卖出
  dp[1][0] = Math.max(
    dp[0][0],
    dp[0][1] + prices[1]
  );

  // 第二天持有股票
  // 表示第一天持有股票第二天继续持有
  // 或者第二天买入股票
  dp[1][1] = Math.max(
    dp[0][0] - prices[1],
    dp[0][1]
  );

  for (let i = 2; i < len; ++i) {
    // 第 i 天不持有股票
    // 要么 i-1 不持有并且第i天也不持有
    // 或第i-1天持有成本与第i天股票价格
    dp[i][0] = Math.max(
      dp[i - 1][1] + prices[i],
      dp[i - 1][0]
    );
    dp[i][1] = Math.max(
      dp[i - 2][0] - prices[i],
      dp[i - 1][1]
    );
  }
  // 最后一天不持有股票前提下的最大收益
  return dp[len - 1][0];
};

maxSlidingWindow 滑动窗口最大值

输入：nums = [1,3,-1,-3,5,3,6,7], k = 3
输出：[3,3,5,5,6,7]

输入：nums = [1], k = 1
输出：[1]

var maxSlidingWindow = function (nums, k) {
  const q = [];   // 单递减的双端队列
  const ans = []; // 最后的返回结果
  // 循环 nums
  for (let i = 0; i < nums.length; i++) {
//当进入滑动窗口的元素大于等于队尾元素时 
// 不断从队尾出队
//直到进入滑动窗口的元素小于队尾的元素
// 以保证单调递减的性质
    while (q.length && nums[i] >=
      nums[q[q.length - 1]]
    ) {
      q.pop();
    }
    q.push(i);  // 元素的索引入队
    // 队头元素已经在滑动窗口外了
    // 移除对头元素
    while (q[0] <= i - k) {
      q.shift();
    }
    // 当 i ≥ k-1 时
    // 单调递减队头就是滑动窗口的最大值
    if (i >= k - 1) ans.push(nums[q[0]]);
  }
  return ans;
};
// 时间复杂度 O(n)
// 空间复杂度 O(k)

maxSubArray 最大子数组和

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6

输入：nums = [1]
输出：1

输入：nums = [5,4,-1,7,8]
输出：23

// 动态规划
var maxSubArray = function (nums) {
  let pre = 0;
  let maxAns = nums[0];
  nums.forEach((x) => {
    pre = Math.max(
      pre + x, x
    );
    maxAns = Math.max(
      maxAns, pre
    );
  });
  return maxAns;
};

MedianFinder 数据流的中位数

输入
["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"]
[[], [1], [2], [], [3], []]
输出
[null, null, null, 1.5, null, 2.0]
// 每次取出中位数的时候
// 都先将所有元素进行排序
// 然后再计算中位数
var MedianFinder = function () {
  this.data = [];
};

MedianFinder.prototype.addNum = function (num) {
  this.data.push(num);
};

MedianFinder.prototype.findMedian = function () {
  const length = this.data.length;
  if (!length) {
    return null;
  }
  this.data.sort((a, b) => a - b);

  const mid = Math.floor(
    (length - 1) / 2
  );
  if (length % 2) {
    return this.data[mid];
  }
  return (this.data[mid] +
    this.data[mid + 1]) / 2;
};

merge 合并两个有序数组

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]

var merge = function (nums1, m, nums2, n) {
  for (let i = m, j = 0; i < m + n; i++, j++) {
    nums1[i] = nums2[j];
  }
  nums1.sort((a, b) => a - b);
};

merge 合并区间

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]

var merge = function (intervals) {
  const res = [];
  intervals.sort(
    (a, b) => a[0] - b[0]
  );
  // 初始为第一个区间
  let prev = intervals[0];
  // 尝试合并 prev 和 cur
  // 合并后更新到 prev
  for (
    let i = 1;
    i < intervals.length;
    i++
  ) {
    // 当前的区间
    let cur = intervals[i];
// 合并后的新区间还可能和后面区间重合
// 继续尝试合并新的 cur
// 更新给 prev
    if (prev[1] >= cur[0]) {
      prev[1] = Math.max(
        cur[1], prev[1]
      );
    } else {
      // 直到不重合时
      // 将 prev 区间推入 res 数组
      res.push(prev);
      prev = cur; // 更新 prev
    }
  }

  res.push(prev);
  return res;
};

mergeKLists 合并 K 个升序链表

输入：lists = [[1,4,5],[1,3,4],[2,6]]
输出：[1,1,2,3,4,4,5,6]

输入：lists = []
输出：[]

输入：lists = [[]]
输出：[]

var mergeKLists = function (lists) {
  const len = lists.length
  if (len === 0) return null
  const merge = (l1, l2) => { // 两两合并
    const head = new ListNode()
    let p = head
    while (l1 && l2) {
      if (l1.val <= l2.val) {
        p.next = l1
        l1 = l1.next
      } else {
        p.next = l2
        l2 = l2.next
      }
      p = p.next
    }
    p.next = l1 ? l1 : l2
    return head.next
  }
  let result = lists[0]
  for (let i = 1; i < len; i++) {
    if (lists[i]) {
result = merge(result, lists[i])
    }
  }
  return result
};

mergeTrees 合并二叉树

输入：root1 = [1,3,2,5], root2 = [2,1,3,null,4,null,7]
输出：[3,4,5,5,4,null,7]

输入：root1 = [1], root2 = [1,2]
输出：[2,2]

const mergeTrees = (t1, t2) => {
  if (t1 == null && t2) {
    return t2;
  }
  if (
    (t1 && t2 == null) ||
    (t1 == null && t2 == null)
  ) {
    return t1;
  }
  t1.val += t2.val;
  t1.left = mergeTrees(
    t1.left, t2.left);
  t1.right = mergeTrees(
    t1.right, t2.right);
  return t1;
};

mergeTwoLists 合并两个有序链表

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

输入：l1 = [], l2 = []
输出：[]

输入：l1 = [], l2 = [0]
输出：[0]

var mergeTwoLists = function (list1, list2) {
  const head = new ListNode()
  let p = head
  while (list1 && list2) {
    if (list1.val < list2.val) {
      p.next = list1
      list1 = list1.next
    } else {
      p.next = list2
      list2 = list2.next
    }
    p = p.next
  }
  if (list1) p.next = list1
  if (list2) p.next = list2
  return head.next
};

minDepth 二叉树的最小深度

输入：root = [3, 9, 20, null, null, 15, 7]
输出：2

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

// DFS 解法
var minDepth = function (root) {
  if (!root) return 0;
  if (root.left && root.right) {
    return Math.min(
      minDepth(root.left),
      minDepth(root.right)
    ) + 1;
  }
if (root.left) {
  return minDepth(root.left) + 1;
}
if (root.right) {
  return minDepth(root.right) + 1;
}
  return 1;
};

// BFS 解法
var minDepth = function (root) {
  let result = 0;
  const queue = [];
  if (root) queue.push(root);
while (queue.length) {
  const len = queue.length;
  for (let i = 0; i < len; i++) {
    const curNode = queue.shift();
// 如果是叶子节点，直接返回所在层数
    if (!curNode.left
      && !curNode.right) {
      return result + 1;  
    }
    curNode.left &&
      queue.push(curNode.left);
    curNode.right &&
      queue.push(curNode.right);
  }
  result += 1; // 进入下一层
}
  return result
};

minDistance 编辑距离

输入：word1 = "horse", word2 = "ros"
输出：3

输入：word1 = "intention", word2 = "execution"
输出：5

var minDistance = function (word1, word2) {
  let dp = Array.from(
    Array(word1.length + 1),
    () => Array(
      word2.length + 1
    ).fill(0)
  );

  // 初始化数组
  // word1 前 i 个字符
  // 最少需要 i 次操作
  // 比如 i 次删除变成 word2
  for (
    let i = 1;
    i <= word1.length;
    i++
  ) {
    dp[i][0] = i;
  }

  // 初始化数组
  // word2 前 i 个字符
  // 最少需要 i 次操作
  // 比如 j 次插入变成 word1
  for (
    let j = 1;
    j <= word2.length;
    j++
  ) {
    dp[0][j] = j;
  }

  for (
    let i = 1;
    i <= word1.length;
    i++
  ) {
    // 循环 word1 和 word2
    for (
      let j = 1;
      j <= word2.length;
      j++
    ) {
      if (
        word1[i - 1] ===
        word2[j - 1]
      ) {
// 说明最后一个字符不用操作
        dp[i][j] =
        dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.min(
          // 对应删除
          dp[i - 1][j] + 1,
          // 对应新增
          dp[i][j - 1] + 1,
          // 对应替换操作
          dp[i - 1][j - 1] + 1
        );
      }
    }
  }

  return dp[word1.length][word2.length];
};

minPathSum 最小路径和

输入：grid = [[1,3,1],[1,5,1],[4,2,1]]
输出：7

输入：grid = [[1,2,3],[4,5,6]]
输出：12

// dp[i][j] 从矩阵左上角到（i，j）
// 从上到下 从左到右遍历网格
// 当前最小路径和就是
// 当前的数值加上上面和左边左小的
var minPathSum = function (dp) {
  let row = dp.length
  let col = dp[0].length
  // 初始化第一列
  for (let i = 1; i < row; i++) {
    dp[i][0] += dp[i - 1][0]
  }
  // 初始化第一行
  for (let j = 1; j < col; j++) {
    dp[0][j] += dp[0][j - 1]
  }
  // 取上面和左边最小的
  for (let i = 1; i < row; i++) {
for (let j = 1; j < col; j++) {
  dp[i][j] +=
  Math.min(
    dp[i - 1][j],
    dp[i][j - 1]
  )
}
  }

  return dp[row - 1][col - 1]
};

MinStack 最小栈

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

var MinStack = function () {
  this.stack = [];
  this.minStack = [Infinity];
};

MinStack.prototype.push = function (x) {
  this.stack.push(x);
  this.minStack.push(Math.min(
    this.minStack[
      this.minStack.length - 1
    ], x
  ));
};

MinStack.prototype.pop = function () {
  this.stack.pop();
  this.minStack.pop();
};

MinStack.prototype.top = function () {
  return this.stack[
    this.stack.length - 1
  ];
};

MinStack.prototype.getMin = function () {
  return this.minStack[
    this.minStack.length - 1
  ];
};

minSubArrayLen 长度最小的子数组

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2

输入：target = 4, nums = [1,4,4]
输出：1

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

// 滑动窗口
var minSubArrayLen = function (target, nums) {
  let l = 0;
  let sum = 0;
  let minLen = Infinity;
  for (let r = 0; r < nums.length; r++) {
    // 主旋律是扩张，找可行解
    sum += nums[r];
    while (sum >= target) {
      // 间歇性收缩，优化可行解
      minLen = Math.min(minLen, r - l + 1);
      sum -= nums[l++];
    }
  }
  // 从未找到可行解，返回0
  return minLen === Infinity ? 0 : minLen;
};

minWindow 最小覆盖子串

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

输入：s = "a", t = "a"
输出："a"

输入: s = "a", t = "aa"
输出: ""

var minWindow = function (s, t) {
  let result = "";
  let l = 0;        // 初始左指针
  let r = 0;        // 初始右指针
  // 创建字典表示子串所需的字符及其个数
  const map = new Map();
  for (let i = 0, len = t.length;
       i < len; i++) {
    // 设置字典中所需字符的个数
    const c = t[i];
    map.set(c, map.has(c) ?
            map.get(c) + 1 : 1);
  }
  // 记录还需要匹配的字符数
  let mapType = map.size;
  // 逐个移动右指针
  while (r < s.length) {  
    // 如果是需要匹配的字符
    // 更新字典和还需要的字符数
    const c = s[r];
    if (map.has(c)) {
      map.set(c, map.get(c) - 1);
if (map.get(c) === 0) mapType -= 1;
    }
    // 当需要匹配的字符已经集齐时
// 开始逐个移动左指针尽可能减少子串长度
    while (mapType === 0) {
  // 当新窗口字符长度小于之前时更新结果
  const newRes = s.slice(l, r + 1);
  if (!result ||
    newRes.length < result.length
  ) result = newRes;
  // 如果是需要匹配的字符
  // 更新字典和还需要的字符数
  const c2 = s[l];
  if (map.has(c2)) {
    map.set(c2, map.get(c2) + 1);
if (map.get(c2)===1) mapType += 1;
// 此时左指针不能再移动了，跳出循环
// 去移动右指针，重新找到所需的字符串
  }
      l++;
    }
    r++;
  }
  return result;
};

moveZeroes 移动零

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

输入: nums = [0]
输出: [0]

var moveZeroes = function (nums) {
  let j = 0;
  for (let i = 0;
    i < nums.length; i++) {
    // 遇到非 0 项
    if (nums[i] != 0) {
      // 覆盖到 j 上
      nums[j] = nums[i];
      // j 后移
      j++;
    }
  }
  // 剩下的位置赋为 0
  for (let i = j;
    i < nums.length; i++) {
    nums[i] = 0;
  }
};

myAtoi 字符串转换整数 (atoi)

输入：s = "42"
输出：42

输入：s = " -042"
输出：-42

输入：s = "1337c0d3"
输出：1337

输入：s = "0-1"
输出：0

输入：s = "words and 987"
输出：0

var myAtoi = function (str) {
  const result = str.trim()
    .match(/^[-|+]{0,1}[0-9]+/)
  if (result != null) {
    if (result[0] > (
      Math.pow(2, 31) - 1
    )) {
      return Math.pow(2, 31) - 1
    }
    if (result[0] <
      Math.pow(-2, 31)
    ) {
      return Math.pow(-2, 31)
    }
    return result[0]
  }
  return 0
};

MyCalendar 我的日程安排表 I

输入：
["MyCalendar", "book", "book", "book"]
[[], [10, 20], [15, 25], [20, 30]]
输出：
[null, true, false, true]

var MyCalendar = function () {
  this.booked = [];
};

MyCalendar.prototype.book = function (start, end) {
  for (const arr of this.booked) {
    let l = arr[0], r = arr[1];
    if (l < end && start < r) {
      return false;
    }
  }
  this.booked.push([start, end]);
  return true;
};
// 时间复杂度：O(n^2)
// 空间复杂度：O(n)

MyCalendarThree 我的日程安排表 III

输入：
["MyCalendarThree", "book", "book", "book", "book", "book", "book"]
[[], [10, 20], [50, 60], [10, 40], [5, 15], [5, 10], [25, 55]]
输出：
[null, 1, 1, 2, 3, 3, 3]

var MyCalendarThree = function () {
  this.planMap = {};;
};

MyCalendarThree.prototype.book = function (start, end) {
  this.planMap[start] =
    (this.planMap[start] || 0)+ 1;
  this.planMap[end] =
    (this.planMap[end] || 0) - 1;
  let res = 0;
  let count = 0;
  Object.values(this.planMap)
    .forEach((item) => {
    count += item;
    res = Math.max(count, res);
  });
  return res;
};

MyCircularDeque 设计循环双端队列

输入
["MyCircularDeque", "insertLast", "insertLast", "insertFront", "insertFront", "getRear", "isFull", "deleteLast", "insertFront", "getFront"]
[[3], [1], [2], [3], [4], [], [], [], [4], []]
输出
[null, true, true, true, false, 2, true, true, true, 4]

var MyCircularDeque = function (k) {
  this.capacity = k + 1;
  this.rear = this.front = 0;
  this.elements =
    new Array(k + 1).fill(0);
};

MyCircularDeque.prototype.insertFront = function (value) {
  if (this.isFull()) {
    return false;
  }
  this.front = (
    this.front - 1 + this.capacity
  ) % this.capacity;
  this.elements[this.front] =
    value;
  return true;
};

MyCircularDeque.prototype.insertLast = function (value) {
  if (this.isFull()) {
    return false;
  }
  this.elements[this.rear]=value;
  this.rear = (this.rear + 1)
    % this.capacity;
  return true;
};

MyCircularDeque.prototype.deleteFront = function () {
  if (this.isEmpty()) {
    return false;
  }
  this.front = (this.front + 1)
    % this.capacity;
  return true;
};

MyCircularDeque.prototype.deleteLast = function () {
  if (this.isEmpty()) {
    return false;
  }
  this.rear = (
    this.rear - 1 + this.capacity
  ) % this.capacity;
  return true;
};

MyCircularDeque.prototype.getFront = function () {
  if (this.isEmpty()) {
    return -1;
  }
  return this.elements[this.front];
};

MyCircularDeque.prototype.getRear = function () {
  if (this.isEmpty()) {
    return -1;
  }
  return this.elements[(
    this.rear - 1 + this.capacity
  ) % this.capacity];
};

MyCircularDeque.prototype.isEmpty = function () {
  return this.rear == this.front;
};

MyCircularDeque.prototype.isFull = function () {
  return (this.rear + 1)
    % this.capacity == this.front;
};

myPow Pow(x, n)

输入：x = 2.00000, n = 10
输出：1024.00000

输入：x = 2.10000, n = 3
输出：9.26100

输入：x = 2.00000, n = -2
输出：0.25000

var myPow = function (x, n) {
  // n=0直接返回1
  if (n === 0) return 1
  //n<0时 x的n次方等于1除以x的-n次方分
  if (n < 0) {
    return 1 / myPow(x, -n)
  }
  //n是奇数时 x的n次方 = x*x的n-1次方
  if (n % 2) {
    return x * myPow(x, n - 1)
  }
  //n是偶数，使用分治，一分为二
  // 等于 x*x 的 n/2 次方 
  return myPow(x * x, n / 2)
}

mySqrt x 的平方根

输入：x = 4
输出：2

输入：x = 8
输出：2

var mySqrt = function (x) {
  // 整数x的平方根一定是在1到x的范围内
  let left = 1,
    right = x;
  while (left <= right) {
    // >> 1 相当于除以 2 向下取整
    // 中间值 下面这样写是防止溢出
    let mid = left + (
      (right - left) >> 1
    );
    // 判断 mid 的平方是否小于或等于 x
    // 如果 mid 的平方小于 x
    if (mid <= x / mid) {
      // 判断 mid+1 的平方是否大于 x
      // 如果 mid+1 的平方大于 x
      // 那么 mid 就是 x 的平方根
      if (mid + 1 > x/(mid + 1)) {
        return mid;
      }
      // 如果 mid 的平方小于 x 并且
      // (mid+1) 的平方小于 x
      // 那么 x 的平方根比 mid 大
      // 接下来搜索从 mid+1 到x的范围
      left = mid + 1;
    } else {
      // 如果 mid 的平方大于 x
      // 则 x 的平方根小于 mid
      // 接下来搜索 1 到 mid-1 的范围
      right = mid - 1;
    }
  }
  // 如果输入参数是0
  // left等于1而right等于0
  // 就直接返回0
  return 0;
};

NestedIterator 扁平化嵌套列表迭代器

输入：nestedList = [[1,1],2,[1,1]]
输出：[1,1,2,1,1]

输入：nestedList = [1,[4,[6]]]
输出：[1,4,6]

var NestedIterator = function (nestedList) {
  vals = [];
  const dfs = (nestedList) => {
    for(const nest of nestedList){
if (nest.isInteger()) {
  vals.push(nest.getInteger());
} else {
  dfs(nest.getList());
}
    }
  }
  dfs(nestedList);
};

NestedIterator.prototype.hasNext = function () {
  return vals.length > 0;
};

NestedIterator.prototype.next = function () {
  const val = vals[0];
  vals = vals.slice(1);
  return val;
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

nextPermutation 下一个排列

输入：nums = [1,2,3]
输出：[1,3,2]

输入：nums = [3,2,1]
输出：[1,2,3]

输入：nums = [1,1,5]
输出：[1,5,1]

var nextPermutation = function (nums) {
  // 向左遍历
  // i 从倒数第二开始是为了
  // nums[i+1] 要存在
  let i = nums.length - 2; 
  // 寻找第一个小于右邻居的数
  while (i >= 0
    && nums[i] >= nums[i + 1]
  ) {
    i--;
  }
  // 这个数在数组中存在
  // 从它身后挑一个数和它换
  if (i >= 0) {
    // 从最后一项，向左遍历
    let j = nums.length - 1;
    // 寻找第一个大于 nums[i] 的数
    while (j >= 0
      && nums[j] <= nums[i]
    ) {
      j--;
    }
    // 两数交换，实现变大
    [nums[i], nums[j]]
    = [nums[j], nums[i]];
  }
  // 如果 i = -1，说明是递减排列
  // 如 3 2 1，没有下一排列
  // 直接翻转为最小排列：1 2 3
  let l = i + 1;
  let r = nums.length - 1;
  // i 右边的数进行翻转
  // 使得变大的幅度小一些
  while (l < r) {
    [nums[l], nums[r]]
    = [nums[r], nums[l]];
    l++;
    r--;
  }
}

numDecodings 解码方法

输入：s = "12"
输出：2

输入：s = "226"
输出：3

输入：s = "06"
输出：0

var numDecodings = function (s) {
  const n = s.length;
const f = new Array(n + 1).fill(0);
  f[0] = 1;
  for (let i = 1; i <= n; ++i) {
    if (s[i - 1] !== '0') {
      f[i] += f[i - 1];
    }
    if (
      i > 1 && s[i - 2] != '0'
      && ((s[i - 2] - '0') * 10
        + (s[i - 1] - '0') <= 26)
    ) {
      f[i] += f[i - 2];
    }
  }
  return f[n];
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

numIslands 岛屿数量

输入：grid = [
  ["1","1","1","1","0"],
  ["1","1","0","1","0"],
  ["1","1","0","0","0"],
  ["0","0","0","0","0"]
]
输出：1

输入：grid = [
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
]
输出：3

// 沉没四周的陆地
function turnZero(i, j, grid) {
  // 检查坐标的合法性
  if (i < 0 ||
      i >= grid.length ||
      j < 0 ||
      j >= grid[0].length ||
      grid[i][j] === '0'
  ) {
    return
  }
  // 让四周的陆地变为海水
  grid[i][j] = '0'
  turnZero(i, j + 1, grid)
  turnZero(i, j - 1, grid)
  turnZero(i + 1, j, grid)
  turnZero(i - 1, j, grid)
}

var numIslands = function (grid) {
  let count = 0
  for (let i = 0;
    i < grid.length; i++) {
    // 循环网格
    for (let j = 0;
      j < grid[0].length; j++) {
      // 如果为陆地，count++
      if (grid[i][j] === '1') {
        count++
        turnZero(i, j, grid)
      }
    }
  }
  return count
}

numSquares 完全平方数

输入：n = 12
输出：3

输入：n = 13
输出：2

var numSquares = function (n) {
  // 数组长度为 n+1，值均为 0
  const dp = [...Array(n + 1)]
    .map(_ => 0);
  for (let i = 1; i <= n; i++) {
    // 最坏的情况就是每次 +1
    dp[i] = i;
    for (let j = 1; i - j * j >= 0; j++) {
      // 动态转移方程
      dp[i] = Math.min(
        dp[i],
        dp[i - j * j] + 1
      );
    }
  }
  return dp[n];
};

numTrees 不同的二叉搜索树

输入：n = 3
输出：5

输入：n = 1
输出：1

var numTrees = function (n) {
  const dp = new Array(n + 1)
    .fill(0);
  dp[0] = 1;
  dp[1] = 1;

for (let i = 2; i <= n; i++) {
  for (let j = 1;
    j <= i; j++) {
    dp[i] +=
      dp[j - 1] * dp[i - j];
  }
}

  return dp[n];
};

oddEvenList 奇偶链表

输入: head = [1,2,3,4,5]
输出: [1,3,5,2,4]

输入: head = [2,1,3,5,6,4,7]
输出: [2,3,6,7,1,5,4]

var oddEvenList = function (head) {
  if (head === null) {
    return head;
  }
  let evenHead = head.next;
  let odd = head, even = evenHead;
  while (even !== null &&
    even.next !== null) {
    odd.next = even.next;
    odd = odd.next;
    even.next = odd.next;
    even = even.next;
  }
  odd.next = evenHead;
  return head;
};
// 时间复杂度：O(n)
// 空间复杂度：O(1)

openLock 打开转盘锁

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6

输入: deadends = ["8888"], target = "0009"
输出：1

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1

var openLock = function (deadends, target) {
  const swipeUp = (path, i) => {
    const arr = path.split('')
    let val = arr[i]
    arr[i]=val==='9' ? 0 : ++val
    return arr.join('')
  }
  const swipeDown = (path, i) =>{
    const arr = path.split('')
    let val = arr[i]
    arr[i]=val==='0' ? 9 : --val
    return arr.join('')
  }
  let step = 0, path = '0000',
      dead = new Map(
        deadends.map(
          item => [item, true]
        )
      )
  const queue = [path],
        visited = new Map()
  while (queue.length) {
    const len = queue.length
    // 取出每层
    for (let i=0; i < len; i++){
const curr = queue.shift()
if (curr === target) return step
if (dead.has(curr)) continue
for (let i = 0; i < 4; i++) {
  const up = swipeUp(curr, i)
  const down = swipeDown(curr, i)
  !visited.has(up) &&
    queue.push(up) &&
    visited.set(up, true)
  !visited.has(down) &&
    queue.push(down) &&
    visited.set(down, true)
}
    }
    step++
  }
  return -1
};

orangesRotting 腐烂的橘子

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4

输入：grid = [[2,1,1],[0,1,1],[1,0,1]]
输出：-1

输入：grid = [[0,2]]
输出：0

var orangesRotting = function(grid) {
  const queue = []
  let unrotten = 0 // 完好的个数
  const height = grid.length
  const width = grid[0].length
  for (let i=0; i<height; i++) {
for (let j = 0; j < width; j++) {
  if (grid[i][j] === 2) {
    queue.push([i, j]) // 所有的坏橘子的坐标推入队列
  } else if (grid[i][j] === 1) {
    unrotten++ // 统计好橘子的个数
  }
}
  }
  if (unrotten == 0) return 0 //如果没有好橘子，直接返回0
  let level = 0 // 树的层次，即腐坏所用的时间
  const dx = [0, 1, 0, -1]
  const dy = [1, 0, -1, 0] // 代表4个方向
  while (queue.length) { // queue队列不为空就继续循环
    const levelSize=queue.length // 当前层节点个数
    level++ // 层次+1
for (let i=0; i<levelSize; i++) { // 当前层节点出列
  let cur = queue.shift()
  for (let j = 0; j < 4; j++) {
    let x = cur[0] + dx[j]
    let y = cur[1] + dy[j]
    if (x < 0 || x >= height ||
      y < 0 || y >= width ||
      grid[x][y] !== 1
    ) continue // 腐化好橘子，超出边界或本身就不是好橘子，跳过
    grid[x][y] = 2 // 将好橘子腐化，避免它被重复遍历
    queue.push([x, y]) // 推入队列，下次循环就将它们出列
    unrotten-- // 好橘子个数-1
  }
}
  }
  return unrotten === 0 ?
    level - 1 : -1 // 好橘子如果还存在，返回-1
}

orderlyQueue 有序队列

输入：s = "cba", k = 1
输出："acb"

输入：s = "baaca", k = 3
输出："aaabc"

var orderlyQueue = function (s, k) {
  if (k === 1) {
    let ans = s;
    for (let i = 0; i < s.length - 1; ++i) {
      const n = s.length;
      s =s.substring(1, n) + s[0];
      ans = ans < s ? ans : s;
    }
    return ans;
  }
  return [...s].sort().join('');
};

partition 分割回文串

输入：s = "google"
输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]

输入：s = "aab"
输出：[["a","a","b"],["aa","b"]]

输入：s = "a"
输出：[["a"]]

var partition = function (s) {
  const n = s.length;
  const f = new Array(n).fill(0)
   .map(
    () => new Array(n).fill(true)
   );
  let result = [],
      ans = [];
  for (let i=n - 1; i >= 0; --i){
    for (let j=i+1; j < n; ++j){
      f[i][j] = (s[i] === s[j])
        && f[i + 1][j - 1];
    }
  }
  const dfs = (i) => {
    if (i === n) {
      ret.push(ans.slice());
      return;
    }
    for (let j = i; j < n; ++j) {
      if (f[i][j]) {
        ans.push(s.slice(i, j+1));
        dfs(j + 1);
        ans.pop();
      }
    }
  }
  dfs(0);
  return result;
};
// n 是字符串 s 的长度
// 时间复杂度 O(n * 2^n)
// 空间复杂度 O(n²)

partition 分隔链表

输入：head = [1,4,3,2,5,2], x = 3
输出：[1,2,2,4,3,5]

输入：head = [2,1], x = 2
输出：[1,2]

var partition = function (head, x) {
  let small = new ListNode(0);
  const smallHead = small;
  let large = new ListNode(0);
  const largeHead = large;
  while (head !== null) {
    if (head.val < x) {
      small.next = head;
      small = small.next;
    } else {
      large.next = head;
      large = large.next;
    }
    head = head.next;
  }
  large.next = null;
  small.next = largeHead.next;
  return smallHead.next;
};
// 时间复杂度: O(n)
// 空间复杂度: O(1)

pathSum 路径总和 III

输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3

输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

// DFS 穷举所有的可能
var pathSum = function (root, targetSum) {
  if (root == null) {
    return 0;
  }
let ret = rootSum(root, targetSum);
ret+=pathSum(root.left, targetSum);
ret+=pathSum(root.right, targetSum);
  return ret;
};
const rootSum = (root, targetSum) => {
  let ret = 0;
  if (root == null) {
    return 0;
  }
  const val = root.val;
  if (val === targetSum) {
    ret++;
  }
  ret += rootSum(
    root.left, targetSum - val);
  ret += rootSum(
    root.right, targetSum - val);
  return ret;
}

permutation 有重复字符串的排列组合

输入：S = "qqe"
输出：["eqq","qeq","qqe"]

输入：S = "ab"
输出：["ab", "ba"]

var permutation = function (S) {
  // 排序，方便确定相同字符
  S = S.split('').sort()
  let res = [];
  let isTrue =
   new Array(S.length).fill(true);
  var dfs = function (str) {
    if (str.length == S.length) {
      res.push(str)
    }
for (let i=0; i < S.length; i++){
  if (i > 0 &&
    S[i - 1] == S[i] &&
    !isTrue[i - 1]
  ) continue;//去重
  if (isTrue[i]) {
    isTrue[i] = false;
    dfs(str + S[i])
    isTrue[i] = true;
  }
}
  }
  dfs('');
  return res;
};

permutation 无重复字符串的排列组合

输入：S = "qwe"
输出：["qwe", "qew", "wqe", "weq", "ewq", "eqw"]

输入：S = "ab"
输出：["ab", "ba"]

var permutation = function (S) {
  const res = [];
  backtrack("");

  return res;

  function backtrack(str) {
    // 符合字符串长度则收集
    if (str.length === S.length) {
      res.push(str);
      return;
    }
    for (let i = 0; i < S.length; i++) {
      // 去除重复字符，比如：字符串为'ab'， 去掉'aa'或'bb'这类情况
      if (str.indexOf(S[i]) !== -1) {
        continue;
      }
      // 递归：回溯的通用公式
      backtrack(str + S[i]);
    }
  }
};

permute 全排列

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

输入：nums = [0,1]
输出：[[0,1],[1,0]]

输入：nums = [1]
输出：[[1]]

var permute = function (nums) {
  const res = [];
  const used = {};

  function dfs(path) {
    // 个数选够了
    if (path.length == nums.length) {
// 拷贝一份 path 加入解集 res
      res.push(path.slice());
// 结束当前递归分支
      return;
    }
    // for 枚举出每个可选的选项
    for (const num of nums) {
      // 使用过的，跳过
      if (used[num]) continue;
      // 选择当前的数加入 path
      path.push(num);
      // 记录一下 使用了
      used[num] = true;
      // 基于选了当前的数，递归
      dfs(path);
      // 上一句的递归结束，回溯
      // 将最后选的数 pop 出来
      path.pop();
      // 撤销这个记录
      used[num] = false;
    }
  }
  // 递归的入口，空 path 传进去
  dfs([]);
  return res;
};

permute 全排列 II

输入：nums = [1,1,2]
输出：
[[1,1,2],
 [1,2,1],
 [2,1,1]]

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

var permuteUnique = function (nums) {
  nums.sort((a, b) => a - b);
  const n = nums.length;
  const ans = [];
  const path = Array(n); // 所有排列的长度都是 n
  const onPath = Array(n).fill(false); // onPath[j] 表示 nums[j] 是否已经填入排列
  function dfs(i) {
    // i 表示当前要填排列的第几个数
    if (i === n) {
      // 填完了
      ans.push([...path]);
      return;
    }
    // 枚举 nums[j] 填入 path[i]
    for (let j = 0; j < n; j++) {
      // 如果 nums[j] 已填入排列，continue
      // 如果 nums[j] 和前一个数 nums[j-1] 相等，且 nums[j-1] 没填入排列，continue
      if (onPath[j] ||
(j > 0 && nums[j] === nums[j - 1] && !onPath[j - 1])
      ) {
        continue;
      }
      path[i] = nums[j]; // 填入排列
      onPath[j] = true; // nums[j] 已填入排列（注意标记的是下标，不是值）
      dfs(i + 1); // 填排列的下一个数
      onPath[j] = false; // 恢复现场
      // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
    }
  }
  dfs(0);
  return ans;
};

plusOne 加一

输入：digits = [1,2,3]
输出：[1,2,4]

输入：digits = [4,3,2,1]
输出：[4,3,2,2]

输入：digits = [9]
输出：[1,0]

var plusOne = function (digits) {
  let carry = false;
  digits[digits.length - 1]++;
  for (let i = digits.length - 1;
    i >= 0; i--) {
    if (carry) digits[i]++;
    carry = digits[i] > 9;
    digits[i] %= 10;
  }
  if (carry) digits.unshift(1);
  return digits;
};

preorderTraversal 二叉树的前序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

// 递归解法
const preorderTraversal = (root) => {
  let result = []
  const preorder = (node) => {
    if (!node) return
    // 先根节点
    result.push(node.val)
    // 然后遍历左子树
    preorder(node.left)
    // 再遍历右子树
    preorder(node.right)
  }
  preorder(root)
  return result
};

// 非递归解法
const preorderTraversal = (root) => {
  const result = [];
  const stack = [];

  // 当根节点不为空的时候，将根节点入栈
  if (root) stack.push(root)
  while (stack.length) {
    const curNode = stack.pop()
    // 第一步的时候，先访问的是根节点
    result.push(curNode.val)

    // 我们先打印左子树，然后右子树
    // 所以先加入栈的是右子树，然后左子树
    curNode.right &&
      stack.push(curNode.right)
    curNode.left &&
      stack.push(curNode.left)
  }
  return result
}

productExceptSelf 除自身以外数组的乘积

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

// 初始化数组、先将该元素乘以左边的乘积
//然后再初始化右边的元素 乘以右边的乘积
var productExceptSelf = function (nums) {
  let len = nums.length;
  let ans = Array.from(
    { length: len }
  );
  let R = 1;
  ans[0] = 1;
// ans[i] 等于数组i左侧所有数字的乘积
for (let i = 1; i < len; i++) {
 ans[i] = ans[i - 1] * nums[i - 1];
}
// 乘上 R 即所有右侧元素的乘积
for (let i=len - 1; i >= 0;i--) {
  ans[i] = ans[i] * R;
  R *= nums[i]
}
  return ans;
};

postorderTraversal 二叉树的后序遍历

/**
 * Definition for a binary tree node.
 * function TreeNode(val, left, right) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.left = (left===undefined ? null : left)
 *     this.right = (right===undefined ? null : right)
 * }
 */

// 递归解法
const postorderTraversal = function (root) {
  const result = []
  const postorder = node => {
    if (!node) return
    postorder(node.left)
    postorder(node.right)
    result.push(node.val)
  }
  postorder(root)
  return result
};

// 非递归解法
const postorderTraversal = function (root) {
  const result = [];
  const stack = [];

  // 当根节点不为空的时候，将根节点入栈
  if (root) stack.push(root)
  while (stack.length) {
    const curNode = stack.pop()
    // 中左右 => 右左中
    result.unshift(curNode.val)

    // 先进栈左子树后右子树
    // 出栈的顺序就变更为先右后左
    curNode.left &&
      stack.push(curNode.left)
    curNode.right &&
      stack.push(curNode.right)
  }
  return result
}

RandomizedSet O(1) 时间插入、删除和获取随机元素

输入
["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
[[], [1], [2], [2], [], [1], [2], []]
输出
[null, true, false, true, 2, true, false, 2]

var RandomizedSet = function () {
  this.nums = [];
  this.indices = new Map();
};

RandomizedSet.prototype.insert = function (val) {
  if (this.indices.has(val)) {
    return false;
  }
  let index = this.nums.length;
  this.nums.push(val);
  this.indices.set(val, index);
  return true;
};

RandomizedSet.prototype.remove = function (val) {
  if (!this.indices.has(val)) {
    return false;
  }
  let id = this.indices.get(val);
  this.nums[id] = this.nums[
    this.nums.length - 1
  ];
  this.indices.set(
    this.nums[id], id
  );
  this.nums.pop();
  this.indices.delete(val);
  return true;
};

RandomizedSet.prototype.getRandom = function () {
  const randomIndex = Math.floor(
    Math.random() *
    this.nums.length
  );
  return this.nums[randomIndex];
};
// 时间复杂度：O(1)
// 空间复杂度：O(n)

reconstructQueue 根据身高重建队列

输入：people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
输出：[[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]

输入：people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
输出：[[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]

var reconstructQueue = function (people) {
  if (people.length < 2) {
    return people;
  }
  let res = [];
  // 先根据 h 和 k 排序，主 h 副 k
  // h 从大到小排序，k 从小到大排序
  people.sort((a, b) => {
    if (a[0] === b[0]) {
      return a[1] - b[1];
    }
    return b[0] - a[0];
  });
  for (let i = 0;
    i < people.length; i++) {
    let k = people[i][1];
    if (k < i) {
      res.splice(k, 0, people[i]);
    } else {
      res[i] = people[i];
    }
  }
  return res;
};

removeDuplicates 删除有序数组中的重复项

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]

var removeDuplicates = function (nums) {
  let k = 1;
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] != nums[i - 1]) {
      // nums[i] 不是重复项
      nums[k++] = nums[i]; // 保留 nums[i]
    }
  }
  return k;
};
// 时间复杂度：O(n)，其中 n 是 nums 的长度。
// 空间复杂度：O(1)。

removeDuplicates 删除有序数组中的重复项 II

输入：nums = [1,1,1,2,2,3]
输出：5, nums = [1,1,2,2,3]

输入：nums = [0,0,1,1,1,1,2,3,3]
输出：7, nums = [0,0,1,1,2,3,3]

var removeDuplicates = function (nums) {
  let stackSize = 2; // 栈的大小，前两个元素默认保留
  for (let i = 2; i < nums.length; i++) {
    if (nums[i] !== nums[stackSize - 2]) {
      // 和栈顶下方的元素比较
      nums[stackSize++] = nums[i]; // 入栈
    }
  }
  return Math.min(stackSize, nums.length);
};

// 时间复杂度：O(n)，其中 n 是 nums 的长度。
// 空间复杂度：O(1)。

removeElement 移除元素

输入：nums = [3,2,2,3], val = 3
输出：2, nums = [2,2,_,_]

输入：nums = [0,1,2,2,3,0,4,2], val = 2
输出：5, nums = [0,1,4,0,3,_,_,_]

var removeElement = function (nums, val) {
  let ans = 0;
  for (const num of nums) {
    if (num != val) {
      nums[ans] = num;
      ans++;
    }
  }
  return ans;
};
// 时间复杂度：O(n)
// 空间复杂度：O(1)

removeInvalidParentheses 删除无效的括号

输入：s = "()())()"
输出：["(())()","()()()"]

输入：s = "(a)())()"
输出：["(a())()","(a)()()"]

输入：s = ")("
输出：[""]

var removeInvalidParentheses = function (s) {
  let res = [];
  let queue = [];
  let visited = new Set();  // 去重

  queue.push(s);
  while (true) {
    let size = queue.length;//[s]
    for (let i=0; i < size; i++) {
      s = queue.shift();//出队
if (isVaild(s)) { // 如果是合法字符串
  res.push(s);    // 加入结果数组
} else if (res.length == 0) {
  // 不合法并且res.length == 0
  // 则进入 bfs 下一层 尝试删除字符
 for (let i=0; i < s.length; i++){
    // 是左右括号尝试删除字符，否则跳过
   if (s[i]=='(' || s[i]===')') {
      let nexts =
        s.substring(0, i) +
        s.substring(i + 1);
      // 判断新生成的字符串是否重复
      if (!visited.has(nexts)) {
  // 加入队列 进入下一层 [s1,s2...]
        queue.push(nexts);
        // 加入去重数组
        visited.add(nexts);
      }
    }
  }
}
    }
    // 出现合法字符串的那一层，终止循环
    if (res.length > 0) {
      break;
    }
  }
  return res;
};

function isVaild(s) {
  let count = 0;
  for(let i=0; i < s.length; i++){
    // 左括号 count + 1
    if (s[i] === '(') {
      count++;
    } else if (s[i] === ')') {
      // 右括号 count - 1
      count--;
    }
    // 小于0 说明右括号多
    if (count < 0) {
      return false;
    }
  }
  return count === 0;
}

removeNthFromEnd 删除链表的倒数第 N 个结点

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

输入：head = [1], n = 1
输出：[]

输入：head = [1,2], n = 1
输出：[1]

// 快慢指针
// 需要删除链表中的倒数第 n 个节点
// 需要知道的就是倒数第 n+1 个节点
// 然后删除
// 倒数第 n+1 节点的后继节点即可
var removeNthFromEnd = function (head, n) {
  let fast = head
  let slow = head
  // 快先走 n 步
  while (--n) {
    fast = fast.next
  }
  if (!fast.next) {
    return head.next
  }
  fast = fast.next
  // fast、slow 一起前进
  while (fast && fast.next) {
    fast = fast.next
    slow = slow.next
  }
  slow.next = slow.next.next
  return head
};

repeatedSubstringPattern 重复的子字符串

输入: s = "abab"
输出: true

输入: s = "aba"
输出: false

var repeatedSubstringPattern = function (s) {
  // 1. 设置 s 的长度 length
  const length = s.length;

  // 2. 设置每次累加的长度
  let str = "";

  // 3. 遍历字符串
  for (let i = 0; i < s.length - 1; i++) {
    // 3.1 累加字符串
    str += s[i];
    // 3.2 判断是否为重复的长度
    if (s === str.repeat(
      Math.floor(length / str.length)
    )) {
      return true;
    }
  }

  // 4. 如果不存在，则返回 false
  return false;
};

reverseBits 颠倒二进制位

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)

var reverseBits = function (n) {
  let result = 0; // 存储结果
  // 32位二进制数，因此需要移动32次
  // 每次将 n 的左后一位
  // 移动到 result 的第一位
  for (let i = 0; i < 32; i++) {
    // 每次将结果左移一位
    // 将当前数字填入空位
    // 如果将移动放在 if 语句之后
    // 会导致多移动一位
    result <<= 1;
    // 如果当前 n 的第一个位置为 1
    // 则需要将 1 填入 result
    if (n & 1) {
      // 如果是 1，才需要填入 1
      // 如果是 0，无需填入
      // 当前位置左移后自然是 0
      result += 1;
    }
    // n 向右移动一位，判断下一个位置
    n >>= 1;
  }

  return result >>> 0;
};

reverseKGroup K 个一组翻转链表

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

var reverseKGroup = function (head, k) {
  let cur = head;
  let count = 0;
  // 求k个待反转元素的首节点和尾节点
  while (cur !== null &&
    count !== k) {
    cur = cur.next;
    count++;
  }
  // 足够k个节点，去反转
  if (count === k) {
    // 递归链接后续k个反转的链表头节点
    cur = reverseKGroup(cur, k);
    while (count != 0) {
      count--;
      // 反转链表
      let tmp = head.next;
      head.next = cur;
      cur = head;
      head = tmp;
    }
    head = cur;
  }
  return head;
};

reverseList 反转链表

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

输入：head = []
输出：[]

var reverseList = function (head) {
  let p1 = head
  let p2 = null

  while (p1) {
    const temp = p1.next
    p1.next = p2
    p2 = p1
    p1 = temp
  }

  return p2
};

reverseBetween 反转链表 II

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

输入：head = [5], left = 1, right = 1
输出：[5]

var reverseBetween = function (head, left, right) {
  const dummy = new ListNode(0, head);
  let p0 = dummy;
  for (let i = 0; i < left - 1; i++) {
    p0 = p0.next;
  }

  let pre = null;
  let cur = p0.next;
  for (let i = 0; i < right - left + 1; i++) {
    const nxt = cur.next;
    cur.next = pre; // 每次循环只修改一个 next，方便大家理解
    pre = cur;
    cur = nxt;
  }

  p0.next.next = cur;
  p0.next = pre;
  return dummy.next;
};

// 时间复杂度：O(right)
// 空间复杂度：O(1)

reverseStr 反转字符串 II

输入：s = "abcdefg", k = 2
输出："bacdfeg"

输入：s = "abcd", k = 2
输出："bacd"

var reverseStr = function (s, k) {
  const len = s.length;
  let resArr = s.split("");

  for (let i = 0; i < len; i += 2 * k) {
    let l = i - 1,
      r = i + k > len ? len : i + k;
    while (++l < --r) {
      [resArr[l], resArr[r]] =
        [resArr[r], resArr[l]];
    }
  }
  return resArr.join("");
};

reverseWords 反转字符串中的单词

输入：s = "the sky is blue"
输出："blue is sky the"

输入：s = "  hello world  "
输出："world hello"

输入：s = "a good   example"
输出："example good a"

var reverseWords = function (s) {
  let res = "";
  for (let item of s.split(" ").reverse()) {
    if (item.trim() !== "") {
      res += item.trim();
      res += " ";
    }
  }
  return res.trim();
};

rightSideView 二叉树的右视图

输入：root = [1,2,3,null,5,null,4]
输出：[1,3,4]

输入：root = [1,2,3,4,null,null,null,5]
输出：[1,3,4,5]

输入：root = [1,null,3]
输出：[1,3]

输入：root = []
输出：[]

var rightSideView = function (root) {
  const ans = [];
  function dfs(node, depth) {
    if (node === null) {
      return;
    }
    if (depth === ans.length) {
      // 这个深度首次遇到
      ans.push(node.val);
    }
    // 先递归右子树，保证首次遇到的一定是最右边的节点
    dfs(node.right, depth + 1);
    dfs(node.left, depth + 1);
  }
  dfs(root, 0);
  return ans;
};

rob 打家劫舍

输入：nums = [1,2,3,1]
输出：4

输入：nums = [2,7,9,3,1]
输出：12

var rob = function (nums) {
  const len = nums.length;
  if (len == 0) { return 0; }
  const dp = new Array(len + 1);
  dp[0] = 0;
  dp[1] = nums[0];
  for (let i = 2; i <= len; i++){
    dp[i] = Math.max(
      dp[i - 1],
      dp[i - 2] + nums[i - 1]
    );
  }
  return dp[len];
};

rob 打家劫舍 II

输入：nums = [2,3,2]
输出：3

输入：nums = [1,2,3,1]
输出：4

输入：nums = [1,2,3]
输出：3

var rob1 = function (nums) {
  let f0 = 0,
    f1 = 0;
  for (const x of nums) {
    [f0, f1] = [f1, Math.max(f1, f0 + x)];
  }
  return f1;
};

var rob = function (nums) {
  const n = nums.length;
  return Math.max(
    nums[0] + rob1(nums.slice(2, n - 1)),
    rob1(nums.slice(1))
  );
};

// 时间复杂度：O(n)
// 空间复杂度：O(1)

rob 打家劫舍 III（二叉树）

输入: root = [3,2,3,null,3,null,1]
输出: 7

输入: root = [3,4,5,1,3,null,1]
输出: 9

// 打劫以 root 为根节点的子树的最大收益
const rob = (root) => {
  if (root == null) {
    return 0;
  }
// 打劫包括根节点的收益，保底是root.val
  let robIncludeRoot = root.val;
  if (root.left) {
    robIncludeRoot +=
      rob(root.left.left) +
      rob(root.left.right);
  }
  if (root.right) {
    robIncludeRoot +=
      rob(root.right.left) +
      rob(root.right.right);
  }
  // 打劫不包括根节点的收益
  const robExcludeRoot =
  rob(root.left) + rob(root.right);
  // 二者取其大
  return Math.max(
    robIncludeRoot,
    robExcludeRoot
  );
};

romanToInt 罗马数字转整数

输入: s = "III"
输出: 3

输入: s = "IV"
输出: 4

输入: s = "IX"
输出: 9

输入: s = "LVIII"
输出: 58

输入: s = "MCMXCIV"
输出: 1994

var romanToInt = function (s) {
  const map = {
    I: 1,
    IV: 4,
    V: 5,
    IX: 9,
    X: 10,
    XL: 40,
    L: 50,
    XC: 90,
    C: 100,
    CD: 400,
    D: 500,
    CM: 900,
    M: 1000,
  };
  let ans = 0;
  for (let i = 0; i < s.length; ) {
    if (i + 1 < s.length
        && map[s.substring(i, i + 2)]
    ) {
      ans += map[s.substring(i, i + 2)];
      i += 2;
    } else {
      ans += map[s.substring(i, i + 1)];
      i++;
    }
  }
  return ans;
};

rotate 旋转图像

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

var rotate = function (matrix) {
  const n = matrix.length;
  // 水平翻转
  for (
    let i = 0;
    i < Math.floor(n / 2);
    i++
  ) {
    for (
      let j = 0; j < n; j++
    ) {
      [
        matrix[i][j],
        matrix[n - i - 1][j]
      ] = [
        matrix[n - i - 1][j],
        matrix[i][j]
      ];
    }
  }
  // 主对角线翻转
  for (let i = 0; i < n; i++) {
    for (
      let j = 0; j < i; j++
    ) {
      [
        matrix[i][j],
        matrix[j][i]
      ] = [
        matrix[j][i],
        matrix[i][j]
      ];
    }
  }
};

rotate 轮转数组

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]

var rotate = function (nums, k) {
  const n = nums.length;
  const newArr = new Array(n);
  for (let i = 0; i < n; ++i) {
    newArr[(i + k) % n] = nums[i];
  }
  for (let i = 0; i < n; ++i) {
    nums[i] = newArr[i];
  }
};
// 时间复杂度 O(n)
// 空间复杂度 O(n)

rotateRight 旋转链表

输入：head = [1,2,3,4,5], k = 2
输出：[4,5,1,2,3]

输入：head = [0,1,2], k = 4
输出：[2,0,1]

var rotateRight = function (head, k) {
  if (k === 0 || !head
    || !head.next) {
    return head;
  }
  let n = 1;
  let cur = head;
  while (cur.next) {
    cur = cur.next;
    n++;
  }

  let add = n - k % n;
  if (add === n) {
    return head;
  }

  cur.next = head;
  while (add) {
    cur = cur.next;
    add--;
  }

  const ret = cur.next;
  cur.next = null;
  return ret;
};

search 搜索旋转排序数组

输入：nums = [4,5,6,7,0,1,2], target = 0
输出：4

输入：nums = [4,5,6,7,0,1,2], target = 3
输出：-1

输入：nums = [1], target = 0
输出：-1

// 二分法
var search = function (nums, target) {
  let start = 0;
  let end = nums.length - 1;

while (start <= end) {
  // >> 1 相当于除以2向下取整
let mid = (start + end) >> 1;

  if (nums[mid] === target) {
    return mid;
  }

  // 如果中间数小于最右边数
  // 则右半段是有序的
  if (nums[mid] < nums[end]) {
// 判断 target 是否在 (mid, end] 之间
    if (
      nums[mid] < target
      && target <= nums[end]
    ) {
// 如果在，则中间数右移 start 增大
      start = mid + 1;
    } else {
// 如果不在，则中间数左移 end 减小
      end = mid - 1;
    }
  } else {
    // 如果中间数大于最右边数
    // 则左半段是有序的
    if (
      nums[start] <= target
      && target < nums[mid]
    ) {
      end = mid - 1;
    } else {
      start = mid + 1;
    }
  }
}

  return -1;
};

searchMatrix 搜索二维矩阵 II

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 5
输出：true

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], target = 20
输出：false

// 由于 matrix 每一行元素都是升序排列的
// 因此可以对每一行都使用一次二分查找
// 判断 target 是否在该行中
// 从而判断 target 是否出现
var searchMatrix = function (matrix, target) {
  const search = (nums, target) => {
    let low = 0,
        high = nums.length - 1;
    while (low <= high) {
      const mid = Math.floor(
        (high - low) / 2
      ) + low;
      const num = nums[mid];
      if (num === target) {
        return mid;
      } else if (num > target) {
        high = mid - 1;
      } else {
        low = mid + 1;
      }
    }
    return -1;
  }
  for (const row of matrix) {
    const index = search(
      row, target
    );
    if (index >= 0) {
      return true;
    }
  }
  return false;
};
// 时间复杂度：O(mlog⁡n)
// 空间复杂度：O(1)

searchRange 在排序数组中查找元素的第一个和最后一个位置

输入：nums = [5,7,7,8,8,10], target = 8
输出：[3,4]

输入：nums = [5,7,7,8,8,10], target = 6
输出：[-1,-1]

输入：nums = [], target = 0
输出：[-1,-1]

// 二分查找
// 然后向左和向右找相同的元素
var searchRange = function (nums, target) {
  let left = 0;
  let right = nums.length - 1;
  let mid;
  // 二分查找 target
  while (left <= right) {
    // >> 1 相当于除以2向下取整
    mid = (left + right) >> 1;
    if (nums[mid] === target) {
      break;
    }
    if (nums[mid] > target) {
      right = mid - 1;
    } else {
      left = mid + 1;
    }
  }
  if (left > right) {
    return [-1, -1];
  }
  let i = mid;
  let j = mid;
  // 向左尝试找相同的元素
while (nums[i] === nums[i - 1]) {
  i--;
}
// 向右尝试找相同的元素
while (nums[j] === nums[j + 1]) {
  j++;
}
  return [i, j];
};

serialize 二叉树的序列化与反序列化

输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]

输入：root = []
输出：[]

输入：root = [1]
输出：[1]

输入：root = [1,2]
输出：[1,2]

const serialize = (root) => {
  // 遍历到 null 节点
  if (root == null) {
    return 'X';
  }
// 左子树的序列化结果
const left = serialize(root.left);
// 右子树的序列化结果
const right =serialize(root.right);
  // 按  根,左,右  拼接字符串
  return root.val +
    ',' + left + ',' + right;
};

const deserialize = (data) => {
  // split成数组
  const list = data.split(',');
  // 基于list构建当前子树
  const buildTree = (list) => {
    // 弹出首项，获取它的“数据”
    const rootVal = list.shift();
    // 是X，返回null节点
    if (rootVal == "X") {
      return null;
    }
// 不是X，则创建节点
const root = new TreeNode(rootVal);
    // 递归构建左子树
    root.left = buildTree(list);
    // 递归构建右子树
    root.right = buildTree(list);
    // 返回当前构建好的root
    return root;
  };
  // 构建的入口
  return buildTree(list);
};

setZeroes 矩阵置零

输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

var setZeroes = function (matrix) {
  const m = matrix.length,
        n = matrix[0].length;
  // 表示第一行和第一列有没有 0
  let flagCol0 = false,
      flagRow0 = false;
  // 寻找第一列是否存在 0
  for (let i = 0; i < m; i++) {
    if (matrix[i][0] === 0) {
      flagCol0 = true;
    }
  }
  for (let j = 0; j < n; j++) {
    if (matrix[0][j] === 0) {
      flagRow0 = true;
    }
  }
  // 循环矩阵，如果遇见 0，将和这个网格
  // 相同的第一行和第一列的元素标记成0
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][j] === 0) {
        matrix[i][0] =
          matrix[0][j] = 0;
      }
    }
  }
  // 循环矩阵，如果当前网格对应的第一行
  // 和第一列是 0，则将这个单元格置为0
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      if (matrix[i][0] === 0 ||
          matrix[0][j] === 0) {
        matrix[i][j] = 0;
      }
    }
  }
//如果第一列有 0，则将这第一列全部置为0
  if (flagCol0) {
    for (let i = 0; i < m; i++) {
      matrix[i][0] = 0;
    }
  }
//如果第一行有 0，则将这第一行全部置为0
  if (flagRow0) {
    for (let j = 0; j < n; j++) {
      matrix[0][j] = 0;
    }
  }
};
// 时间复杂度O(mn)，m、n为矩阵的行和列
// 空间复杂度O(1)

shortestAlternatingPaths 颜色交替的最短路径

输入：n = 3, red_edges = [[0,1],[1,2]], blue_edges = []
输出：[0,1,-1]

输入：n = 3, red_edges = [[0,1]], blue_edges = [[2,1]]
输出：[0,1,-1]

var shortestAlternatingPaths = function (n, red_edges, blue_edges) {
  const map = Array.from(
    { length: n }, () => []
  );
  for(const [f,t] of red_edges){
    map[f].push(t);
  }
  for(const [f,t] of blue_edges){
    map[f].push(t | 128);
  }
  const ans=new Array(n).fill(-1);
  const vis = new Set();
  let queue = [0, 128];
  let step = -1;
  while (queue.length) {
    const tmp = [];
    step++;
    for (const f of queue) {
      vis.add(f);
      const idx = f & -129;
      if (ans[idx] === -1) {
        ans[idx] = step;
      }
      for (const t of map[idx]) {
        if (vis.has(t)) continue;
        // 同色
        if (
          (f & 128) === (t & 128)
        ) continue;
        tmp.push(t);
      }
    }
    queue = tmp;
  }
  return ans;
};

shortestPalindrome 最短回文串

输入：s = "aacecaaa"
输出："aaacecaaa"

输入：s = "abcd"
输出："dcbabcd"

// 找到原字符串中最大的重叠部分，然后把剩余部分反转后加到前面
var shortestPalindrome = function(s) {
  const len = s.length;
  // 先把原字符串反转
  const reStr = s.split('').reverse().join(''); 
  
  // 然后比较原字符串和反转字符串的重叠部分
  for (let i = len; i >= 0; i--) {
    // 比较原字符串前i个字符和反转字符串后i个字符
    if (s.substring(0, i) == reStr.substring(len - i)) {
      // 找到最大的重叠部分
      // 把反转字符串中不重叠的部分加到原字符串前面
      return reStr.substring(0, len - i) + s;
    }
  }
};

shortestPathBinaryMatrix 二进制矩阵中的最短路径

输入：grid = [[0,1],[1,0]]
输出：2

输入：grid = [[0,0,0],[1,1,0],[1,1,0]]
输出：4

输入：grid = [[1,0,0],[1,1,0],[1,1,0]]
输出：-1

var shortestPathBinaryMatrix = function(grid) {
  const n = grid.length
  if (grid[0][0] !== 0 ||
    grid[n-1][n-1] !== 0
  ) return -1
  const direction = [
    [1,1], [0,1], [1,0],
    [-1,1], [1,-1], [0,-1],
    [-1,0], [-1,-1]
  ] // 八个方向
  const list = [[0, 0]]
  let count = 1
  while (list.length > 0) {
    const size = list.length // 当前层范围
    for (let i=0; i<size; ++i) {
      const [curR, curC] =
        list.shift() // 取节点
      if (curR === n - 1 &&
        curC === n - 1
      ) return count // 找到最短路径
      for (let j=0; j<8; ++j) {
        const nextR =
          curR + direction[j][0]
        const nextC =
          curC + direction[j][1]
if (nextR<0 || nextR>=n ||
  nextC < 0 || nextC >= n ||
    grid[nextR][nextC] !== 0
  ) continue // 索引不合法 或 值不为0 跳过
        grid[nextR][nextC] = 1
        list.push([nextR, nextC])
      }
    }
    ++count // 层数+1
  }
  return -1
};

simplifyPath 简化路径

输入：path = "/home/"
输出："/home"

输入：path = "/home//foo/"
输出："/home/foo"

输入：path = "/home/user/Documents/../Pictures"
输出："/home/user/Pictures"

输入：path = "/../"
输出："/"

输入：path = "/.../a/../b/c/../d/./"
输出："/.../b/d"

var simplifyPath = function (path) {
  const stack = [];
  for (const s of path.split("/")) {
    if (!s || s === ".") {
      continue;
    }
    if (s !== "..") {
      stack.push(s);
    } else if (stack.length > 0) {
      stack.pop();
    }
  }
  return "/" + stack.join("/");
};

Solution 打乱数组

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

var Solution = function (nums) {
  this.nums = nums;
  this.original = nums.slice();

};

Solution.prototype.reset = function () {
  this.nums =
    this.original.slice();
  return this.nums;
};

Solution.prototype.shuffle = function () {
  const shuffled =
    new Array(
      this.nums.length
    ).fill(0);
  const list = [];
  this.nums.forEach(
    (num) => list.push(num)
  );
  for (let i = 0;
    i < this.nums.length; ++i) {
    const j = Math.random()
      * list.length;
    shuffled[i] =
      list.splice(j, 1);
  }
  this.nums = shuffled.slice();
  return this.nums;
};

solve 被围绕的区域

输入：board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
输出：[["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]

var solve = function (board) {
  const m = board.length;
  // [] 情况的特判
  if (m == 0) return;
  const n = board[0].length;
  const dfs = (i, j) => {
    // 越界了
    if (i < 0 || i == m ||
        j < 0 || j == n) return;
    // 遇到 O，染为 NO    
    if (board[i][j] == 'O') {
      board[i][j] = 'NO';
      // 对四个方向的邻居进行 dfs
      dfs(i + 1, j);
      dfs(i - 1, j);
      dfs(i, j + 1);
      dfs(i, j - 1);
    }
  };
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (i == 0 || i == m - 1 ||
          j == 0 || j == n - 1) {
        // 从最外层的 O，开始 DFS
        if (board[i][j] == 'O') {
          dfs(i, j);
        }
      }
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      // 恢复为 O
      if (board[i][j] === 'NO') {
        board[i][j] = 'O';
      }
      // O 变为 X
     else if (board[i][j]==='O'){
        board[i][j] = 'X';
      }
    }
  }
};
// 时间复杂度 O(m*n)
// 空间复杂度 O(m*n)

sortColors 颜色分类

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]

输入：nums = [2,0,1]
输出：[0,1,2]

// 使用三个指针
var sortColors = function (nums) {
  const length = nums.length - 1;
  // 存放 0 的指针
  let start = 0;
  // 存放 1 的指针 end
  let end = length;
  // 移动指针 cur
  let cur = 0;
  let cval;

  function swap(start, end) {
    const temp = nums[start];
    nums[start] = nums[end];
    nums[end] = temp;
  }
  // 结束条件
  while (cur <= end) {
    cval = nums[cur];
    // 当前数为 0，就往前放
    if (cval === 0) {
      swap(cur, start);
// 放了之后 0 指针自然就 +1;
      start++;
// 但还需要 cur 也加 1
// 因为 cur 已经为 0 了
// 交换后，不可能变大
// 所以 curr 也得往前
      cur++;
    }
    // 这里 start 不能 ++
    // 因为后面交换回来的有可能是 0
    // 所以还得经下一轮比较判断
    // 再决定是否 +1；
    if (cval === 2) {
      swap(cur, end);
      end--;
    }
    // 为 1 就是特殊情况
    // 暂时不动，继续往前查找
    if (cval === 1) {
      cur++
    }
  }
};

sortedArrayToBST 将有序数组转换为二叉搜索树

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]

输入：nums = [1,3]
输出：[3,1]

var sortedArrayToBST = function (nums) {
  // 因为涉及到递归
  // 所以必然会有数组为空的情况
  if (!nums.length) {
    return null;
  }
  // 找到序列中点：
  const headIndex =
    Math.floor(nums.length / 2);
  // 实例化节点头部
  const head =
    new TreeNode(nums[headIndex]);
  let temp = head;
  let left = headIndex - 1;
  let right = headIndex + 1;
  // 因为是有序升序列表，则当前头部索引
  // 的左侧应该都在树的左子树 同理右子树
  if (left >= 0) {
// 左侧有节点，对左侧节点递归 形成左子树
    head.left = sortedArrayToBST(
      nums.slice(0, headIndex)
    );
  }
  if (right < nums.length) {
// 右侧有节点，对右侧节点递归 形成右子树
    head.right = sortedArrayToBST(
      nums.slice(right)
    );
  }
  // 返回节点
  return head;
};

sortList 排序链表

输入：head = [4,2,1,3]
输出：[1,2,3,4]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

输入：head = []
输出：[]

// 先将链表分割成最小的块
// 再放入合并 -> 从最小的块升序排序
var sortList = function (head) {
  // 合并链表
  let mergeList = (left, right) => {
    // 从最小的块开始合并
    let res = new ListNode(0);
    let pre = res;
    // 排序
    while (left && right) {
      if (left.val <= right.val) {
        pre.next = left;
        left = left.next;
      } else {
        pre.next = right;
        right = right.next;
      }
      pre = pre.next;
    }
    // 最大值
    pre.next = left || right;
    // 返回最后的结果
    return res.next;
  }
  // 切分列表
  let mergeSort = (node) => {
    // 若无链表 -> 直接返回
    if (!node || !node.next) {
      return node;
    }

    // 慢指针
    let mid = node;
    // 快指针
    let fast = node.next;

    // 利用 fast 和 fast.next
    // 如果链表长度为奇数
    // 则返回中间节点
    // 如果链表长度为偶数
    // 则有两个中间节点，这里返回第一个
    while (fast && fast.next) {
      mid = mid.next;
      fast = fast.next.next;
    }

    // 分割左右链表
    let rightList = mid.next;
    // 从中间切断
    mid.next = null;
    let left = node;
    let right = rightList;
    // 继续分割到只有一个时
    // -> 传入 mergeList 合并方法
    return mergeList(
      mergeSort(left),
      mergeSort(right)
    );
  }
  // 调用方法
  return mergeSort(head);
};

spiralOrder 螺旋矩阵

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

var spiralOrder = function (matrix) {
if (matrix.length === 0) return []
  const res = []
  let top = 0,
    bottom = matrix.length - 1,
    left = 0,
    right = matrix[0].length - 1
  while (top < bottom
    && left < right) {
    // 上层
    for (let i=left; i<right;i++){
      res.push(matrix[top][i])
    }
    // 右层
    for (let i=top; i<bottom;i++){
      res.push(matrix[i][right])
    }
    // 下层
    for (let i=right; i>left;i--){
      res.push(matrix[bottom][i])
    }
    // 左层
    for (let i=bottom; i>top;i--){
      res.push(matrix[i][left])
    }
    // 四个边界同时收缩，进入内层
    right--
    top++
    bottom--
    left++
  }
  // 剩下一行，从左到右依次添加
  if (top === bottom) {
   for (let i=left; i<=right;i++){
    res.push(matrix[top][i])
   }
  }
  // 剩下一列，从上到下依次添加
  else if (left === right) {
   for (let i=top; i<=bottom;i++){
      res.push(matrix[i][left])
    }
  }
  return res
};

strStr 找出字符串中第一个匹配项的下标

输入：haystack = "sadbutsad", needle = "sad"
输出：0

输入：haystack = "leetcode", needle = "leeto"
输出：-1

var strStr = function (haystack, needle) {
  const n = haystack.length,
        m = needle.length;
  for (let i=0; i + m <= n; i++) {
    let flag = true;
    for (let j = 0; j < m; j++) {
      if (
        haystack[i+j] != needle[j]
      ) {
        flag = false;
        break;
      }
    }
    if (flag) {
      return i;
    }
  }
  return -1;
};

subarraySum 和为 K 的子数组

输入：nums = [1,1,1], k = 2
输出：2

输入：nums = [1,2,3], k = 3
输出：2

var subarraySum = function(nums, k) {
  const map = { 0: 1 };
  let prefixSum = 0;
  let count = 0;
  for (let i = 0;
    i < nums.length; i++) {
    prefixSum += nums[i];
    if (map[prefixSum - k]) {
      count += map[prefixSum - k];
    }
    if (map[prefixSum]) {
      map[prefixSum]++;
    } else {
      map[prefixSum] = 1;
    }
  }
  return count;
};

subsets 子集

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

输入：nums = [0]
输出：[[],[0]]

// 逐个考察数字，每个数都选或不选
// 等到递归结束时，把集合加入解集
var subsets = function (nums) {
  const res = [];

  const dfs = (index, list) => {
    // 指针越界
    if (index == nums.length) {
      // 加入解集
      res.push(list.slice());
      // 结束当前的递归
      return;
    }
    // 选择这个数
    list.push(nums[index]);
    // 基于该选择，继续往下递归
    // 考察下一个数
    dfs(index + 1, list);
    // 上面的递归结束，撤销该选择
    list.pop();
    // 不选这个数，继续往下递归
    // 考察下一个数
    dfs(index + 1, list);
  };

  dfs(0, []);
  return res;
};

sumNumbers 求根节点到叶节点数字之和

输入：root = [1,2,3]
输出：25

输入：root = [4,9,0,5,1]
输出：1026

var sumNumbers = function (root, x = 0) {
  if (root === null) {
    return 0;
  }
  x = x * 10 + root.val;
  if (root.left === null && root.right === null) {
    // root 是叶子节点
    return x;
  }
  return sumNumbers(root.left, x) + sumNumbers(root.right, x);
};

// 时间复杂度：O(n)，其中 n 为二叉树的节点个数。
// 空间复杂度：O(n)。最坏情况下，二叉树退化成一条链，递归需要 O(n) 的栈空间。

threeSum 三数之和

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

输入：nums = [0,1,1]
输出：[]

输入：nums = [0,0,0]
输出：[[0,0,0]]

var threeSum = function (nums) {
  let ans = [];
  const len = nums.length;
  if (nums == null || len < 3) {
    return ans;
  }
  // 排序
  nums.sort((a, b) => a - b);
  for (let i = 0; i < len; i++) {
    // 如果当前数字大于 0
    // 则三数之和一定大于 0
    // 所以结束循环
    if (nums[i] > 0) break;
    // 去重
    if (i > 0
      && nums[i] == nums[i - 1]
    ) continue;
    let L = i + 1;
    let R = len - 1;
    while (L < R) {
      const sum =
        nums[i] +
        nums[L] + 
        nums[R];
      if (sum == 0) {
        ans.push([
          nums[i],
          nums[L],
          nums[R]
        ]);
        // 去重
        while (
          L < R && nums[L]
          == nums[L + 1]
        ) L++;
        // 去重
        while (
          L < R && nums[R]
          == nums[R - 1]
        ) R--;
        L++;
        R--;
      } else if (sum < 0) L++;
      else if (sum > 0) R--;
    }
  }
  return ans;
};

threeSumClosest 最接近的三数之和

输入：nums = [-1,2,1,-4], target = 1
输出：2

输入：nums = [0,0,0], target = 1
输出：0

var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b);
  let res = nums[0] + nums[1]
    + nums[nums.length - 1];

  for (let i = 0;
    i < nums.length - 2; i++) {
    const n1 = nums[i];
    let l = i + 1;
    let r = nums.length - 1;
    while (l < r) {
      const n2 = nums[l];
      const n3 = nums[r];
      const sum = n1 + n2 + n3;
      if (sum > target) {
        r--;
      } else {
        l++;
      }
      if (Math.abs(sum - target)
        < Math.abs(res - target)
      ) {
        res = sum;
      }
    }
  }
  return res;
};

titleToNumber Excel 表列序号

输入: columnTitle = "A"
输出: 1

输入: columnTitle = "AB"
输出: 28

输入: columnTitle = "ZY"
输出: 701

// 进制转换
// 当列名称的长度为 n 时，列名称的
// 每个字母都有 26 种不同的取值
// 因此长度为 n 的不同列名称有 26^n 个
var titleToNumber = function (columnTitle) {
  let number = 0;
  let multiple = 1;
  const len = columnTitle.length;
  for (let i = len-1; i>=0; i--){
    const k =
      columnTitle[i].charCodeAt()
      - 'A'.charCodeAt() + 1;
    number += k * multiple;
    multiple *= 26;
  }
  return number;
};
// n 是 columnTitle 的长度
// 时间复杂度：O(n)
// 空间复杂度：O(1)

topKFrequent 前 K 个高频元素

输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2
输出: ["i", "love"]

输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
输出: ["the", "is", "sunny", "day"]

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

输入: nums = [1], k = 1
输出: [1]

var topKFrequent = function(words, k) {
  if (nums.length === 1) return nums
  const obj = {}
  nums.forEach(item => {
    if (!obj[item]) {
      obj[item] = 1
    } else {
      obj[item]++
    }
  })
  const arr = []
  for (let key in obj) {
    arr.push({
      key,
      val: obj[key]
    })
  }
  arr.sort((a, b) =>
    b['val'] - a['val']
  )
  const result = []
  for (let i = 0; i < k; i++) {
    result.push(arr[i].key)
  }
  return result
};

trailingZeroes 阶乘后的零

输入：n = 3
输出：0

输入：n = 5
输出：1

输入：n = 0
输出：0

var trailingZeroes = function (n) {
  let ans = 0;
  for (let i=5; i <= n; i += 5){
    for (let x = i;
      x % 5 == 0; x /= 5) {
      ++ans;
    }
  }
  return ans;
};
// 时间复杂度：O(n)
// 空间复杂度：O(1)

trap 接雨水

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6

输入：height = [4,2,0,3,2,5]
输出：9

// 双指针
// 维护两个指针 left 和 right
// 以及两个变量 leftMax 和 rightMax

// 指针 left 只会向右移动
// 指针 right 只会向左移动

// 在移动指针的过程中
// 维护 leftMax 和 rightMax 的值
var trap = function (height) {
  let ans = 0;
  let left = 0;
  let right = height.length - 1;
  let leftMax = 0;
  let rightMax = 0;
  while (left < right) {
    leftMax = Math.max(
      leftMax, height[left]
    );
    rightMax = Math.max(
      rightMax, height[right]
    );
    if (
      height[left] < height[right]
    ) {
      ans +=
        leftMax - height[left];
      ++left;
    } else {
      ans +=
        rightMax - height[right];
      --right;
    }
  }
  return ans;
};

Trie 实现 Trie (前缀树)

输入
["Trie", "insert", "search", "search", "startsWith", "insert", "search"]
[[], ["apple"], ["apple"], ["app"], ["app"], ["app"], ["app"]]
输出
[null, null, true, false, true, null, true]

var Trie = function () {
  this.children = {};
};

Trie.prototype.insert = function (word) {
  let nodes = this.children;
  // 循环 word
  for (const ch of word) {
// 当前字符不在子节点中
// 则创建一个子节点到children的响应位置
    if (!nodes[ch]) {
      nodes[ch] = {};
    }
    // 移动指针到下一个字符子节点
    nodes = nodes[ch];
  }
  // 字符是否结束
  nodes.isEnd = true;
};

Trie.prototype.searchPrefix = function (prefix) {
  let nodes = this.children;
  // 循环前缀
  for (const ch of prefix) {
// 当前字符不在子节点中 直接返回 false
    if (!nodes[ch]) {
      return false;
    }
    // 移动指针到下一个字符子节点
    nodes = nodes[ch];
  }
  return nodes; // 返回最后的节点
}

Trie.prototype.search = function (word) {
  const nodes =
    this.searchPrefix(word);
  // 判断 searchPrefix 返回的节点
  // 是不是字符串的结尾的字符
  return nodes !== undefined &&
    nodes.isEnd !== undefined;
};

Trie.prototype.startsWith = function (prefix) {
  return this.searchPrefix(prefix);
};

twoSum 两数之和 II - 输入有序数组

输入：numbers = [2,7,11,15], target = 9
输出：[1,2]

输入：numbers = [2,3,4], target = 6
输出：[1,3]

输入：numbers = [-1,0], target = -1
输出：[1,2]

// 双指针
var twoSum = function (numbers, target) {
  let left = 0,
    right = numbers.length - 1;

  while (left < right)
    if (numbers[left] + numbers[right] > target) {
      right--;
    } else if (numbers[left] + numbers[right] < target) {
      left++;
    } else {
      return [++left, ++right];
    }
};

uniquePaths 不同路径

输入：m = 3, n = 7
输出：28

输入：m = 3, n = 2
输出：3

var uniquePaths = function (m, n) {
  const f = new Array(m)
    .fill(0)
    .map(() => 
      new Array(n).fill(0)
    );
  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];
};

validateStackSequences 验证栈序列

输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true

输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false

var validateStackSequences = function (pushed, popped) {
  const stack = [];
  const n = pushed.length;
  for (let i=0, j=0; i<n; i++) {
    stack.push(pushed[i]);
    while (stack.length &&
      stack[stack.length - 1] ==
      popped[j]
    ) {
      stack.pop();
      j++;
    }
  }
  return stack.length === 0;
};
// 时间复杂度：O(n)
// 空间复杂度：O(n)

wiggleSort 摆动排序 II

输入：nums = [1,5,1,1,6,4]
输出：[1,6,1,5,1,4]

输入：nums = [1,3,2,2,3,1]
输出：[2,3,1,3,1,2]

var wiggleSort = function (nums) {
  const arr = nums.slice();
  arr.sort((a, b) => a - b);
  const n = nums.length;
  const x = Math.floor((n+1) / 2);
  for (let i = 0,
           j = x - 1,
           k = n - 1;
      i < n; i += 2, j--, k--) {
    nums[i] = arr[j];
    if (i + 1 < n) {
      nums[i + 1] = arr[k];
    }
  }
};
// 时间复杂度：O(nlog⁡n)
// 空间复杂度：O(n)

wordBreak 单词拆分

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true

var wordBreak = function (s, wordDict) {
  // dp 数组,表示前 index 为能否被拆分
  let dp = new Array(
    s.length + 1).fill(false);
  // 空子前缀串默认能被拆分
  dp[0] = true;
  for (let i = 1;
    i <= s.length; i++) {
    for (let j = 0;
      j <= i - 1; j++) {
      // 存在一个字串能被拆分
      // 并且剩余的字符串能在单词表中
      // 找到就表示当前单词能被拆分
      if (dp[j] &&
        wordDict.indexOf(
          s.substring(j, i)
        ) !== -1) {
          dp[i] = true;
      }
    }
  }
  return dp[s.length];
};

wordBreak 单词拆分 II

输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
输出:["cats and dog","cat sand dog"]

输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]

输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
输出:[]

var wordBreak = function (s, wordDict) {
  let map = {}
  let dfs = (start) => {
    if (start == s.length) {
      // 本条路径可通，则返回二维路径
      return [[]]
    }
    let paths = []
    for (let i = start + 1;
      i <= s.length; i++) {
let str = s.substring(start, i)
if (wordDict.indexOf(str) == -1){
  continue
}
      let leafPath = []
      if (map[i]) {
        leafPath = map[i]
      } else {
        leafPath = dfs(i)
      }
for (let j = 0;
  j < leafPath.length; j++) {
  let temp = [...leafPath[j]]
  temp.unshift(str)
  paths.push(temp)
}
    }
    map[start] = paths
    return paths
  }
  return dfs(0).map(
    v => v.join(' ')
  )
};

wordPattern 单词规律

输入: pattern = "abba", s = "dog cat cat dog"
输出: true

输入:pattern = "abba", s = "dog cat cat fish"
输出: false

输入: pattern = "aaaa", s = "dog cat cat dog"
输出: false

var wordPattern = function (pattern, s) {
  //把两个字符串都转化为数组
  let res = pattern.split("");
  let ans = s.split(" ");
  //比较长度
  if (res.length != ans.length) {
    return false;
  }
  //遍历数组，进行比较
  for (let i = 0; i < res.length; i++) {
    if (res.indexOf(res[i]) != ans.indexOf(ans[i])) {
      return false;
    }
  }
  return true;
};

zigzagLevelOrder 二叉树的锯齿形层序遍历

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[20,9],[15,7]]

输入：root = [1]
输出：[[1]]

输入：root = []
输出：[]

var zigzagLevelOrder = function (root) {
  if (!root) {
    return [];
  }

  const result = [];
  const queue = [root];

  let isOrderLeft = true;

  while (queue.length) {
    let level = [];
    const size = queue.length;
    for (let i=0; i < size; ++i){
      const node = queue.shift();
      if (isOrderLeft) {
        level.push(node.val);
      } else {
        level.unshift(node.val);
      }
      if (node.left !== null) {
        queue.push(node.left);
      }
      if (node.right !== null) {
        queue.push(node.right);
      }
    }
    result.push(level);
    isOrderLeft = !isOrderLeft;
  }

  return result;
};
// 时间复杂度：O(N) N 为二叉树的节点数
// 空间复杂度：O(N)

手写实现工厂模式

class Benz {
  getName() {
    console.log("奔驰");
  }
}

class Audi {
  getName() {
    console.log("奥迪");
  }
}

class Car {
  constructor(name) {
    switch (name) {
      case "benz":
        return new Benz();
      case "audi":
        return new Audi();
      default:
        throw TypeError("error name");
    }
  }
}

const benz = new Car("benz");
benz.getName();  // 奔驰

手写实现单例模式

class Benz {
  getName() {
    console.log("奔驰");
  }
}

const Singleton = (function () {
  let instance = null;

  return {
    getInstance: function () {
      if (!instance) {
        instance = new Benz();
      }
      return instance;
    },
  };
})();

const benz1 = Singleton.getInstance()
const benz2 = Singleton.getInstance()
console.log(benz1 === benz2)  // true

手写实现适配器模式

class OldBenz {
  getName() {
    return '奔驰';
  }
}

class NewBenz {
  constructor() {
    this.adapter = new OldBenz();
  }
  getName() {
    const name = this.adapter.getName();
    return name;
  }
}

const benz = new NewBenz();
console.log(benz.getName());  // 奔驰

手写实现装饰器模式

function decorator(car) {
  car.color = 'black'
  return car
}

@decorator
class Benz {
  getName() {
    console.log("奔驰")
  }
}

console.log(Benz.color)

手写实现代理模式

const myCar = {
  name: 'Benz',
  price: 30
}

const carStore = new Proxy(myCar, {
  get(target, key) {
    if (key === 'price') {
      return target[key] + 5
    } else {
      return target[key]
    }
  }
})

console.log(carStore.price, carStore.name) // 35 'Benz'

手写实现观察者模式

class Subject {
  constructor() {
    this.observers = [];
  }
  attach(observer) {
    this.observers.push(observer);
  }
  notify() {
    this.observers.forEach((o) => o.update());
  }
}

class Observer {
  update() {
    console.log('通知：被观察者已更新');
  }
}

// 创建被观察者
const subject = new Subject();
// 创建多个观察者
const o1 = new Observer();
const o2 = new Observer();
// 各个观察者订阅 subject 的通知
subject.attach(o1);
subject.attach(o2);

// 发出广播，执行所有观察者的 update 方法
subject.notify(); // 通知：被观察者已更新 × 2

手写实现迭代器模式

// 定义迭代器生成函数，入参是任意集合
function iteratorGenerator(items) {
  let index = 0
  return {
    next: function () {
      return {
        done: index >= items.length,
        value: index >= items.length
          ? undefined
          : items[index++],
      }
    }
  }
}

const arr = ['a', 'b', 'c'];
const iterator =
  iteratorGenerator(arr);

iterator.next() // { done: false, value: 'a' }
iterator.next() // { done: false, value: 'b' }
iterator.next() // { done: false, value: 'c' }

手写模拟实现 instanceof

function myInstanceof(
  left, right) {
  let proto =
    Object.getPrototypeOf(left)

  while (true) {
    if (proto === null) {
      return false;
    }
    if (proto===right.prototype){
      return true;
    }
    proto =
    Object.getPrototypeOf(proto);
  }
}

手写模拟实现 call 函数

Function.prototype.myCall =
  function (context, ...args) {
  if (typeof this!=='function') {
    throw new TypeError('Error');
  }
  context = context || window;
  context.fn = this;
  const result =
    context.fn(...args);
  delete context.fn;
  return result;
}

手写模拟实现 apply 函数

Function.prototype.myApply =
  function (context, arr) {
  if (typeof this!=='function'){
    throw new TypeError('Error');
  }
  context = context || window;
  context.fn = this;
  let result;
  if (!arr) {
    result = context.fn();
  } else {
    result = context.fn(...arr);
  }
  delete context.fn;
  return result;
}

手写模拟实现 bind 函数

Function.prototype.myBind =
  function (context, ...args) {
  if (typeof this!=='function') {
    throw new TypeError('Error');
  }
  const fn = this;
  return function result(
    ...innerArgs
  ) {
    return fn.apply(
      this instanceof result ?
        this : context,
      args.concat(...innerArgs)
    );
  }
}

手写模拟实现 new 函数

function _new(obj, ...rest) {
  const newObj =
    Object.create(obj.prototype);
  const result =
    obj.apply(newObj, rest);
  return
    result instanceof Object ?
    result : newObj;
}

手写模拟实现 Object.create() 函数

function _create(obj, props) {
  function Fn() { }
  Fn.prototype = obj;
  const fn = new Fn();
  if (props) {
    Object.defineProperties(
      fn, props)
  }
  return fn
}

手写模拟实现 Object.is() 函数

function _is(x, y) {
  if (x === y) {
    return x !== 0 ||
      1 / x === 1 / y;
  }
  return x !== x && y !== y;
};

手写模拟实现数组的 flat 方法

function myFlat(arr, depth = 1) {
  if (!Array.isArray(arr) ||
    depth <= 0) {
    return arr;
  }
  let result = [];
  arr.forEach(item => {
    result = result.concat(
      myFlat(item, depth - 1)
    );
  });
  return result;
}

手写模拟实现数组的 filter 方法

Array.prototype.myFilter =
  function (callback, thisArg) {
  if (typeof callback !==
    'function') {
    throw new TypeError(
      'callback type error');
  }
  const result = [];
  this.forEach((item, index) => {
    if (callback.call(
      thisArg, item, index, this
    )) {
      result.push(item);
    }
  });
  return result;
}

手写模拟实现数组的 map 方法

Array.prototype.myMap =
  function (callback, context) {
  if (typeof callback !==
    'function') {
    throw new TypeError(
      'callback type error');
  }
  const result = [];
  this.forEach((item, index) => {
    result.push(callback.call(
      context, item, index, this
    ));
  });
  return result;
};

手写模拟实现数组的 reduce 方法

Array.prototype.myReduce =
  // args 是初始值
  function (callback, ...args) {
    let start = 0;
  let result;
  if (args.length) {
    // 有参数的话
    // result 等于参数第 0 项
    result = args[0];
  } else {
    // 没参数的话
    // 默认从数组 0 项开始
    result = this[0];
    start = 1;
  }
  for (let i = start;
    i < this.length; i++) {
    result = callback(
      result, this[i], i, this
    );
  }
  return result;
};

手写模拟实现 Promise

function MyPromise(fn) {
  this.state = "pending";
  this.value = null;
  this.resolveFns = [];
  this.rejectFns = [];

  function resolve(value) {
    if (
      value instanceof MyPromise
    ) {
      return value.then(
        resolve, reject
      );
    }
    setTimeout(() => {
      if (
        this.state === "pending"
      ) {
        this.state = "resolved";
        this.value = value;
        this.resolveFns.forEach(
          callback => {
          callback(value);
        });
      }
    });
  }

  function reject(value) {
    setTimeout(() => {
      if (
        this.state === "pending"
      ) {
        this.state = "rejected";
        this.value = value;
        this.rejectFns.forEach(
          callback => {
          callback(value);
        });
      }
    });
  }

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

MyPromise.prototype.then =
function (onResolved,onRejected){
  if (this.state === "pending") {
    this.resolveFns.push(
      onResolved);
    this.rejectFns.push(
      onRejected);
  }
  if (this.state === "resolved"){
    onResolved(this.value);
  }
  if (this.state === "rejected"){
    onRejected(this.value);
  }
};

手写模拟实现 Promise.all

function promiseAll(promises) {
  // 用 Promise 将参数包一层
  // 使其变成一个 promise 对象
  return new Promise(
    (resolve, reject) => {
   if (!Array.isArray(promises)){
      throw new TypeError(
        `argument must be a array`
      )
    }
    let resolvedCounter = 0;
    const promiseNum
      = promises.length;
    const resolvedResult = [];
    // 参数所有回调成功才是成功
    // 返回值数组与参数顺序一致
    for (let i = 0;
      i < promiseNum; i++) {
     Promise.resolve(promises[i])
        .then(value => {
        resolvedCounter++;
        resolvedResult[i]= value;
        if (resolvedCounter
          == promiseNum) {
          return resolve(
            resolvedResult)
        }
      }, error => {
        // 参数数组其中一个失败
        // 则触发失败状态
        return reject(error)
      })
    }
  })
}

const p1 = new Promise(
  (resolve, reject) => {
    setTimeout(() => {
      resolve(1)
    }, 1000)
  })
const p2 = new Promise(
  (resolve, reject) => {
    setTimeout(() => {
      resolve(2)
    }, 2000)
  })
const p3 = new Promise(
  (resolve, reject) => {
    setTimeout(() => {
      resolve(3)
    }, 3000)
  })

promiseAll([p3, p1, p2])
  .then(res => {
    console.log(res) // [3, 1, 2]
  })

手写模拟实现 Promise.race

// 该方法的参数是 Promise 实例数组
// 然后其 then 注册的回调方法
//  是数组中的某一个 Promise 的状态
//  变为 fulfilled 时就执行
// 因为 Promise 的状态只能改变一次
// 那么只需把 Promise.race 中产生的
//  Promise 对象的 resolve 方法
//  注入到数组中的每个 Promise 实例
//  的回调函数中即可.
Promise.race = function (args) {
  return new Promise(
    (resolve, reject) => {
    for (let i = 0,
             len = args.length;
        i < len; i++) {
     args[i].then(resolve,reject)
    }
  })
}

手写模拟实现深拷贝

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

  let result;
  if (obj instanceof Array) {
    result = [];
  } else {
    result = {};
  }
  for (let key in obj) {
    if (obj.hasOwnProperty(key)){
      result[key] =
        deepCopy(obj[key]);
    }
  }
  return result;
}

手写 clearfix 清除浮动（CSS）

.clearfix:after {
  content: "";
  display: block;
  clear: both;
}

.clearfix {
  zoom: 1;  // 兼容 IE
}

手写实现平行四边形（CSS）

div {
  transform: skewX(45deg);
}

手写实现等边三角形（CSS）

div {
  width: 0;
  height: 0;
  border: 100px solid transparent;
  border-bottom-color: black;
}

手写实现下拉尖角（CSS）

// 向上的实心尖角标
.angle {
  width: 0;
  height: 0;
  border-left: 10px solid transparent;
  border-right: 10px solid transparent;
  border-bottom: 10px solid #999;
}

// 向右的实心尖角标
.angle {
  width: 0;
  height: 0;
  border-top: 10px solid transparent;
  border-bottom: 10px solid transparent;
  border-left: 10px solid #999;
}

// 向下的实心尖角标
.angle {
  width: 0;
  height: 0;
  border-left: 10px solid transparent;
  border-right: 10px solid transparent;
  border-top: 10px solid #999;
}

// 向左的实心尖角标
.angle {
  width: 0;
  height: 0;
  border-top: 10px solid transparent;
  border-bottom: 10px solid transparent;
  border-right: 10px solid #999;
}

手写类型判断函数（通用）

function getType(value) {
  // 判断数据是 null 的情况
  if (value === null) {
    return value + "";
  }
  // 判断数据是引用类型的情况
  if (typeof value === "object") {
    const valueClass =
      Object.prototype
        .toString.call(value);
    const type = valueClass
        .split(" ")[1].split("");
    type.pop();
    return type.join("")
      .toLowerCase();
  } else {
    // 判断数据是基本数据类型的情况
    // 和函数的情况
    return typeof value;
  }
}

手写 setTimeout 模拟实现 setInterval

function mySetInterval(fn,timeout){
  // 控制器，控制定时器是否继续执行
  var timer = {
    flag: true
  };
  // 设置递归函数，模拟定时器执行。
  function interval() {
    if (timer.flag) {
      fn();
      setTimeout(interval,timeout);
    }
  }
  // 启动定时器
  setTimeout(interval, timeout);
  // 返回控制器
  return timer;
}

手写解析 URL 参数为对象（通用）

const url = `http://www.abc.com/?
city=gz&a=123&b=456`

const parse = (url) => {
  const param = url.split('?')[1];
  const arr = param.split('&');
  const obj = {};
  arr.forEach(item => {
    const [key, val] =
      item.split('=');
    obj[key] = val;
  })
  return obj
}

console.log(parse(obj));

const parse2 = (url) => {
  const obj = {};
  url.replace(
    /[\?\&]([^=]+)=([^&]+)/g,
    (str, key, val) => {
    obj[key] = val;
  })
  return obj;
}

手写实现深拷贝函数（通用）

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

  let result;
  if (obj instanceof Array) {
    result = [];
  } else {
    result = {};
  }
  for (let key in obj) {
    if (obj.hasOwnProperty(key)){
      result[key] =
        deepCopy(obj[key]);
    }
  }
  return result;
}

手写实现函数柯里化（通用）

function curry(fn, ...args) {
  if (args.length >= fn.length) {
    return fn(...args)
  }
  return (...args2) =>
    curry(fn, ...args, ...args2);
}

const add = (x, y) => {
  console.log(x + y)
}
const curriedAdd = curry(add)
curriedAdd(1)(2)  // 3
curriedAdd(1, 2)  // 3

手写封装 React 受控钩子（通用）

import { useState } from 'react';

export default
  function useDefault(
    value, defaultValue, onChange
  ) {
  const [
    internalValue,
    setInternalValue
  ] = useState(defaultValue);

  const defaultFn = () => {};

  if (typeof value!=='undefined'){
    return [value, onChange ||
      defaultFn];
  }

  return [internalValue,
    (newValue, ...args) => {
    setInternalValue(newValue);
    if (typeof onChange ===
      'function') {
      onChange(newValue, ...args);
    }
  }];
}

手写实现防抖（通用）

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

  return function () {
    if (timer) {
      clearTimeout(timer);
      timer = null;
    }
    timer = setTimeout(() => {
      fn.apply(this, arguments)
    }, wait);
  }
}

手写实现节流（通用）

// 时间戳实现
function throttled(fn, delay = 500) {
  let oldTime = Date.now()
  return function () {
    const newTime = Date.now()
    if(newTime-oldTime >= delay){
      fn.apply(null, arguments)
      oldTime = Date.now()
    }
  }
}

// 定时器实现
function throttled(fn, delay = 500) {
  let timer = null
  return function () {
    if (!timer) {
      timer = setTimeout(() => {
        fn.apply(this, arguments)
        timer = null
      }, delay);
    }
  }
}

手写任务调度器类，控制最大并发数（通用）

class TaskScheduler {
  constructor(n) {
    this.max = n;
    this.running = 0;
    this.queue = [];
  }

  async add(task) {
    if (this.running >= this.max) {
      await new Promise(resolve => this.queue.push(resolve));
    }
    this.running++;
    try {
      return await task();
    } finally {
      this.running--;
      if (this.queue.length) this.queue.shift()();
    }
  }
}

// 示例用法
const scheduler = new TaskScheduler(2);

const tasks = [
  () => new Promise(res => setTimeout(() => console.log(1), 1000)),
  () => new Promise(res => setTimeout(() => console.log(2), 800)),
  () => new Promise(res => setTimeout(() => console.log(3), 500)),
  () => new Promise(res => setTimeout(() => console.log(4), 1200)),
];

tasks.forEach((item) => scheduler.add(item));

手写 MySQL 增删改查语句（通用）

-- 插入数据
INSERT INTO users (
  username, PASSWORD
) VALUES ('aaa', 123456);

-- 删除数据
DELETE FROM users
WHERE username = 'aaa';

-- 修改数据
UPDATE users
SET username = 'bbb'
WHERE username = 'aaa';

-- 查询数据
SELECT username FROM users;

手写排序-冒泡排序

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

const arr = [6, 5, 3, 4, 2, 1];
console.log(bubbleSort(arr)); // [1, 2, 3, 4, 5, 6]

时间复杂度‌：O(n) ~ O(n²)
‌空间复杂度‌：O(1)

手写排序-选择排序

function selectionSort(arr) {
  for (let i = 0, len =arr.length;
    i < len; i++) {
    let minIndex = i;
    for (let j = i + 1;
      j < len; j++) {
      if (arr[j] <arr[minIndex]){
        minIndex = j;
      }
    }
    const temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
  return arr;
}

const arr = [6, 5, 3, 4, 2, 1];
console.log(selectionSort(arr)); // [1, 2, 3, 4, 5, 6]

‌时间复杂度‌：O(n²)
‌空间复杂度‌：O(1)

手写排序-插入排序

function insertionSort(arr) {
  for (let i = 1, len =arr.length;
    i < len; i++) {
    const insert = arr[i];
    for (var j = i - 1;
      j >= 0; j--) {
      if (insert < arr[j]) {
        const tmp = arr[j];
        arr[j + 1] = tmp;
      } else {
        break;
      }
    }
    arr[j + 1] = insert;
  }
  return arr;
}

const arr = [6, 5, 3, 4, 2, 1];
console.log(insertionSort(arr)); // [1, 2, 3, 4, 5, 6]

‌时间复杂度‌：O(n) ~ O(n²)
‌空间复杂度‌：O(1)

手写排序-归并排序

const mergeSort = arr => {
  if (arr.length <= 1) {
    return arr;
  }
  const mid = Math.floor(
    arr.length / 2
  );
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);
  // 合并成一个有序数组
  const merge = (left, right) =>{
    const result = [];
    // 将左右子数组较小的元素放入 result，直到有一个子数组遍历完毕
    while (
      left.length && right.length
    ) {
      if (left[0] < right[0]) {
        result.push(left.shift());
      } else {
        result.push(right.shift());
      }
    }
    // 此时将另一个子数组剩余的元素放入 result
    return result.concat(left)
      .concat(right);
  }

  return merge(
    mergeSort(left),
    mergeSort(right)
  );
}

const arr = [6, 5, 3, 4, 2, 1];
console.log(mergeSort(arr)); // [1, 2, 3, 4, 5, 6]

时间复杂度‌：O(𝑛㏒𝑛)
‌空间复杂度‌：O(n)

手写排序-快速排序

const quickSort = (arr) => {
  const len = arr.length;
  if (len < 2) {
    return arr;
  } else {
    const flag = arr[0];
    const left = [];
    const right = [];
    for (let i = 1;
      i < len; i++) {
      const temp = arr[i];
      if (temp < flag) {
        left.push(temp);
      } else {
        right.push(temp);
      }
    }
    return quickSort(left)
      .concat(
        flag, quickSort(right)
      );
  }
};

const arr = [6, 5, 3, 4, 2, 1];
console.log(quickSort(arr)); // [1, 2, 3, 4, 5, 6]

时间复杂度‌：O(𝑛㏒𝑛) ~ O(n²)
‌空间复杂度‌：O(㏒𝑛)

手写实现数组随机排序

const shuffle = (arr) =>
  arr.sort(
    () => Math.random() - 0.5
  )

手写实现数组元素求和（通用）

const sum = (arr) =>
  arr.reduce((total, item) =>
    total += item
  )

手写模拟实现数组扁平化（通用）

const flatten = (arr) => {
  while (arr.some(item =>
    Array.isArray(item))
  ) {
    arr = [].concat(...arr)
  }
  return arr
}

手写实现数组去重（通用）

const unique = (arr) => {
  for (let i = 0, len =arr.length;
    i < len; i++) {
    for (let j = i + 1;
      j < len; j++) {
      if (arr[i] === arr[j]) {
        arr.splice(j, 1);
        len--;
        j--;
      }
    }
  }
  return arr;
}

// ES6 Set
const unique = (arr) =>
  [...new Set(arr)]

// 对象的方式
const unique = (arr) => {
  const result = [];
  const obj = {}; // 用来去重的对象
  for (let i = 0;
    i < arr.length; i++) {
    if (!obj[arr[i]]) {
      result.push(arr[i]);
      obj[arr[i]] = 'x';
    }
  }
  return result;
}

手写实现二分搜索算法（通用）

const binarySearch = (arr,num)=>{
  arr.sort((a, b) => a - b)
  let left = 0
  let right = arr.length - 1
  while (left < right) {
    const mid = Math.floor(
      (left + right) / 2
    )
    if (arr[mid] < num) {
      left = mid + 1
    } else if (arr[mid] > num) {
      right = mid - 1
    } else {
      return mid
    }
  }
  return -1
}

const arr = [6, 5, 3, 4, 2, 1];
binarySearch(arr, 3)  // 2

手写循环打印红绿黄问题（通用）

递归实现

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

const task = (
  timer, light, callback
) => {
  setTimeout(() => {
    if (light === 'red') {
      red()
    } else if (light==='green') {
      green()
    } else if (light==='yellow') {
      yellow()
    }
    callback()
  }, timer)
}

const step = () => {
  task(3000, 'red', () => {
    task(2000, 'green', () => {
      task(1000, 'yellow', step)
    })
  })
}
step()

Promise 实现

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

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

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

const task = (timer, light) =>
new Promise((resolve, reject) => {
  setTimeout(() => {
    if (light === 'red') {
      red()
    } else if (light==='green') {
      green()
    } else if (light==='yellow') {
      yellow()
    }
    resolve()
  }, timer)
})

const step = () => {
  task(3000, 'red')
    .then(() => task(
      2000, 'green')
    )
    .then(() => task(
      1000, 'yellow')
    )
    .then(step)
}
step()

async/await 实现

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

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

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

const task = (timer, light) =>
  new Promise((
    resolve, reject
  ) => {
    setTimeout(() => {
      if (light === 'red') {
        red()
      }else if(light==='green') {
        green()
      }else if(light==='yellow') {
        yellow()
      }
      resolve()
    }, timer)
  })

const taskRunner = async () => {
  await task(3000, 'red')
  await task(2000, 'green')
  await task(1000, 'yellow')
  taskRunner()
}
taskRunner()

手写 DFS 和 BFS（二叉树）（通用）

const dfs = root => {
  console.log(root.val)
  root.children.forEach(dfs)
}
dfs(tree)

const bfs = root => {
  const queue = []
  if (root) queue.push(root)
  while (queue.length) {
    const curNode = queue.shift()
    console.log(curNode.val)
curNode.children.forEach(child=> {
  queue.push(child)
})
  }
}
bfs(tree)

手写前中后层序遍历（二叉树）（通用）

// 前序遍历
const preorderTraversal = (root) => {
  let result = []
  const preorder = (node) => {
    if (!node) return
    // 先根节点
    result.push(node.val)
    // 然后遍历左子树
    preorder(node.left)
    // 再遍历右子树
    preorder(node.right)
  }
  preorder(root)
  return result
};

// 中序遍历
const inorderTraversal = function (root) {
  const result = []
  const inorder = node => {
    if (!node) return
    inorder(node.left)
    result.push(node.val)
    inorder(node.right)
  }
  inorder(root)
  return result
};

// 后序遍历
const postorderTraversal = function (root) {
  const result = []
  const postorder = node => {
    if (!node) return
    postorder(node.left)
    postorder(node.right)
    result.push(node.val)
  }
  postorder(root)
  return result
};

// 层序遍历
const levelOrder = function (root) {
  const result = [];
  const queue = [];
  if (root) queue.push(root);
  while (queue.length) {
    // 记录当前层级节点数
    const len = queue.length;
    // 存放每一层的节点
    const curArr = [];
  for (let i = 0; i < len; i++) {
    const curNode = queue.shift();
    curArr.push(curNode.val);
    // 存放当前层下一层的节点
    curNode.left &&
      queue.push(curNode.left);
    curNode.right &&
      queue.push(curNode.right);
  }
    // 把每一层的结果放到结果数组
    result.push(curArr);
  }
  return result;
};

手写正则表达式系列（通用）

// 手机号
const reg1 = /^1[44578]\d{9}$/g;
const str1 = '15928229999'
console.log(reg1.test(str1));


// 邮箱
const reg4 = /
  ^([A-za-z0-9_\-\.]+)
  +@([A-za-z0-9_\-\.]+)
  \.([A-Za-z]{2, 6})$/g;
const str4 = 'a11bc@didi.com'
console.log(reg4.test(str4));


// qq号
const reg2 = /^[1-9][0-9]{4,9}$/g;
const str2 = '159222'
console.log(reg2.test(str2));


// 去除字符串空格
var str = ' as '
// 去除所有空格
str = str.replace(/\s*/g,"");
// 去除两头空格
str =str.replace(/^\s*|\s*$/g,"");
// 去除左边空
str = str.replace(/^\s*/,"");
// 去除右边空格
str = str.replace(/(\s*$)/g,"");


// 驼峰 转 -
// helloWorld => hello-world
str.replace(
  /([a-z])([A-Z])/g, '$1-$2'
).toLowerCase();


// - 转驼峰
// hello-world => helloWorld
str.replace(
  /-([a-z])/g,
  (match, group1) => {
  return group1.toUpperCase();
});


// 颜色
const reg3 = /
  #?([0-9a-fA-F]{6}|
    [0-9a-fA-F]{3}
  )/g;
const str3 = '#abc'
console.log(reg3.test(str3));

数据分类处理（信息社会，有海量...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const I = [];
let R = [];

rl.on("line", function (line) {
  if (I.length === 0) {
    I.push(...line.split(" "));
  } else {
    R.push(...line.split(" "));
    const ILen = +I.shift();
    R.shift();
    // 对R先进行排序
    R.sort((a, b) => a - b);
    // 对R去重
    const newArrFn = (arr) => {
      // 利用includes 检查新数组是否
      // 包含原数组的每一项
      // 如果不包含，就push进去
      let newArr = [];
      for (let i = 0;
        i < arr.length; i++) {
        newArr.includes(arr[i]) ?
          newArr :
          newArr.push(arr[i]);
      }
      return newArr;
    };
    R = newArrFn(R);
    // console.log(R);
    const RLen = R.length;
    let output = [];
    let r = 0;
    // R依次中取出R<i>，对I进行处理
    while (r < RLen) {
      const curR = R[r];
      let i = 0;
      let iContainR = 0;
      let iIndexV = [];
      while (i < ILen) {
        const curI = I[i];
        if (curI.includes(curR)){
          iContainR++;
          iIndexV.push(i, curI);
        }
        i++;
      }
      if (iContainR > 0) {
        output.push(curR);
        output.push(iContainR);
        output.push(...iIndexV);
      }
      r++;
    }
    let length = output.length;
    output.unshift(length);
    console.log(output.join(" "));
  }
});

查找组成一个偶数最接近的两个素数（任意一个偶数（大于2...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  let sum = line;
  let a = sum / 2;
  let arr = [];
  let res = 0;
  for (let i = 2; i <= a; i++) {
    let num1 = i;
    let num2 = sum - i;
    let x = 0;
    let y = 0;
    for (let j=num1; j>0; j--) {
      if (num1 % j == 0) {
        x++;
      }
    }
    for (let k=num2; k>0; k--) {
      if (num2 % k == 0) {
        y++;
      }
    }
    if (x == 2 && y == 2) {
      let reduce = num2 - num1;
      if (reduce<res || res==0) {
        res = reduce;
        arr = [];
        arr.push(num1);
        arr.push(num2);
      }
    }
  }
  console.log(arr[0]);
  console.log(arr[1]);
});

素数伴侣（若两个正整数的和为素数...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let arr = [];
rl.on("line", function (line) {
  arr.push(line);
});
rl.on("close", function () {
  let input = arr[1].split(" ");
  let odds = []; // 奇数
  let evens = []; //偶数
  let count = 0;

  let v = new Array(100); //标记访问
  let match = new Array(100); //标记与偶数链接的奇数

  //判断是否为质数
  function isPrime(num) {
    if (num < 2) {
      return false;
    }
    for (let i = 2;
      i * i <= num; i++) {
      if (num % i == 0) {
        return false;
      }
    }
    return true;
  }
  //判断是否匹配
  function isMatch(odd) {
    let evenLength = evens.length;
    for (let i = 0;
      i < evenLength; i++) {
      let sum = Number(odd) +
        Number(evens[i]);
      if (isPrime(sum) && !v[i]){
        //有边，未访问，标记

        v[i] = true;

        //偶数未有匹配的奇数 或者右边有匹配
        if (!match[i] ||
          isMatch(match[i])
        ) {
          match[i] = odd;
          return true;
        }
      }
    }
    return false;
  }
  //执行
  function init() {
    //1.分奇数偶数
    //标记偶数是否匹配的对象
    input.forEach((c) => {
      if (c % 2 == 0) {
        evens.push(c);
      } else {
        odds.push(c);
      }
    });
    // 2.遍历奇数
    let oddLength = odds.length; //zuo
    for (let i = 0;
      i < oddLength; i++) {
      v = new Array(evens.length);
      let falg = isMatch(odds[i]);
      if (falg) {
        count++;
      }
    }
    console.log(count);
  }
  init();
});

求最小公倍数（正整数A和正整数B...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  let [a, b] = line.split(" ");
  function gcd(a, b) {
    if (a % b == 0) return b;
    return gcd(b, a % b);
  }

  console.log((a*b) / gcd(a, b));
});

称砝码（现有n种砝码，重量...）牛客HJ

const readline =
  require("readline");
const lr =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let total = 0,
  mArr = [],
  xArr = [];
let map = new Map();
lr.on("line", (line) => {
  total++;
  if (total === 2) {
    mArr = line.split(" ")
      .map(Number);
  } else if (total === 3) {
    xArr = line.split(" ")
      .map(Number);
  }
});

lr.on("close", () => {
  let fama = [];
  mArr.forEach((item, index) => {
    for (let i = 0;
      i < xArr[index]; i++) {
      fama.push(item);
    }
  });
  let set = new Set();
  set.add(0);
  fama.forEach((item) => {
    let temp = Array.from(set);
    for (let i = 0;
      i < temp.length; i++) {
      set.add(temp[i] + item);
    }
  });
  console.log(set.size);
});

成绩排序（给定一些同学的信息...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let result = [];
rl.on("line", function (line) {
  const tokens = line.split(" ");
  result.push(tokens);
});

rl.on("close", () => {
  result.shift();
  let sort = result.shift()[0];
  let sortArr =
    Boolean(Number(sort))
    ? result.sort(
      (x, y) => x[1] - y[1])
    : result.sort(
      (x, y) => y[1] - x[1]);
  sortArr.forEach((item) => {
    let [key, value] = item;
    console.log(key, value);
  });
});

查找兄弟单词（定义一个单词的“兄弟...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  const inputs = line.split(" ");
  const count = inputs[0];
  let brothers = inputs
    .slice(1, inputs.length - 2)
    .filter((v) => {
      return isBrotherHood(v,
      inputs[inputs.length - 2]);
    })
    .sort((m, n) => {
      return m > n ? 1 : -1;
    });
  console.log(brothers.length);
  if (brothers[+inputs[
    inputs.length - 1] - 1])
    console.log(brothers[
      +inputs[inputs.length - 1]
      - 1
    ]);
});

function isBrotherHood(str,goal){
  return (
    str
      .split("")
      .sort((m, n) => {
        return m > n ? 1 : -1;
      })
      .join("") ===
      goal
        .split("")
        .sort((m, n) => {
          return m > n ? 1 : -1;
        })
        .join("") && str !== goal
  );
}

字符串排序（给定 n 个字符串，请...）牛客HJ

const rl = require("readline")
  .createInterface(
    { input: process.stdin }
  );
var iter =
  rl[Symbol.asyncIterator]();
const readline =
  async () => (
    await iter.next()
  ).value;

void (async function () {
  // Write your code here
  let tokens = [];
  while ((
    line = await readline()
  )) {
    tokens.push(line);
  }
  let arr = tokens.slice(
    1, tokens.length
  );
  arr.sort();
  arr.forEach((item) => {
    console.log(item);
  });
})();

合并表记录（数据表记录包含表索引...）牛客HJ

const rl = require("readline")
  .createInterface(
    { input: process.stdin }
  );
var iter = rl[
  Symbol.asyncIterator
]();
const readline = async () => (
  await iter.next()
).value;

void (async function () {
  // Write your code here
  let arr = [];
  while (
    (line = await readline())
  ) {
    let newstr = line.split(" ");
    if (newstr[1]) {
      let num =
        parseInt(newstr[0]);
      let num1 =
        parseInt(newstr[1]);
      if (arr[num]) {
        arr[num] += num1;
      } else {
        arr[num] = num1;
      }
    }
  }
  arr.forEach((item, index) => {
    console.log(index, item);
  });
})();

字符逆序（将一个字符串str的...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  console.log(
    line.split("")
      .reverse().join("")
  );
});

输入整型数组和排序标识，对其元素按照升序或降序进行排序牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
let [count,collection] = [0, []];
rl.on("line", function (line) {
  if (count === 0) {
    count = +line;
    return;
  }
  if (line.includes(" ") &&
    !collection.length) {
    collection = line.split(" ")
      .map(Number);
    return;
  }
  if (collection.length > 0) {
    collection = collection.sort(
      (m, n) => {
      return +line === 1 ?
        n - m : m - n;
    });
    console.log(collection.slice(
      0, count
    ).join(" "));
  }
});

整数与IP地址间的转换（原理：ip地址的每段可以...）牛客HJ

const readline =
  require("readline");
const r =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

r.on("line", (ip) => {
  let ipArr = ip.split(".");
  if (ipArr.length > 1) {
    let res = 0;
    for (let i = 0;
      i < ipArr.length; i++) {
      res += ipArr[i] *
        Math.pow(2, (3 - i) * 8);
    }
    console.log(res);
  } else {
    let res = [];
    for (let i = 1; i <= 4; i++){
      let remain = Math.floor(
        ip % Math.pow(2, 8)
      );
      ip = ip >>> 8;
      res = `${remain}.${res}`;
    }
    console.log(res.slice(0, -1));
  }
});

删除字符串中出现次数最少的字符（实现删除字符串中出现...）牛客HJ

const readline =
  require("readline");
const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", (line) => {
  let str = line;
  let result = line.split("")
    .reduce((temp, data) => {
    temp[data] = temp[data] ?
      temp[data] + 1 : 1;
    return temp; // 统计字母出现次数
  }, {});
  let min = 21;

  for (let index in result) {
    min = Math.min(
      min, result[index]
    );
  }
  for (let index in result) {
    if (min === result[index]) {
      let reg = new RegExp(
        index, "g"
      );
      str = str.replace(reg, "");
    }
  }
  console.log(str);
});

密码验证合格程序（密码要求...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  console.log(
    isQualify(line) ? "OK" : "NG"
  );
});

function isQualify(str) {
  let [correct, count] = [0, 0];
  if (str.length < 9 ||
    str.includes("\n") ||
    str.includes(" ")
  ) return false;
  if (/[a-z]/.test(str)) {
    correct++;
  }
  if (/[A-Z]/.test(str)) {
    correct++;
  }
  if(/[0-9]/.test(str)) correct++;
  if(
  /[^\u4e00-\u9fa5a-zA-Z\d,\.，。]
    +/.test(str)
  ) correct++;
  if (correct < 3) return false;

  const obj = {};
  for (let i = 0;
    i < str.length; i++) {
    let substring =
      str.substring(i, i + 3);
    if (
      substring.length < 3
    ) continue;
    obj[substring] = null;
    count++;
  }
  return Object.keys(obj).length
    === count;
}

坐标移动（开发一个坐标计算工具...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  //计算x
  let x = eval(
    (line.split(";").filter(
      (v) =>
        /^(a|d)\d+$/i.test(v)
    ) || [])
      .join("")
      .replace(/a/gi, "-")
      .replace(/d/gi, "+") || "0"
  );

  //计算y
  let y = eval(
    (line.split(";").filter(
      (v) =>
        /^(w|s)\d+$/i.test(v)
    ) || [])
      .join("")
      .replace(/s/gi, "-")
      .replace(/w/gi, "+") || "0"
  );

  console.log(`${x},${y}`);
});

跳台阶（一只青蛙一次可以跳上1级台阶...）牛客HJ

function jumpFloor(number) {
  var n1 = 1;
  var n2 = 2;
  while (--number) {
    n2 = n1 + n2;
    n1 = n2 - n1;
  }
  return n1;
}
module.exports = {
  jumpFloor: jumpFloor,
};

字符个数统计（编写一个函数，计算...）牛客HJ

const readline =
  require("readline");

const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
rl.on("line", function (line) {
  let str = [];
  let str1 = [...new Set(line)];
  console.log(str1.length);
});

明明的随机数（明明生成了N个1到...）牛客HJ

const readline =
  require("readline");
const rl =
  readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});
const inputData = [];
rl.on("line", (line) => {
  inputData.push(line);
});
rl.on("close", () => {
  const arr = inputData.splice(1);
  const newArr= [...new Set(arr)];
  newArr.sort((a, b) => a - b);
  newArr.forEach((item) => {
    console.log(Number(item));
  });
});

进制转换（写出一个程序，接受...）牛客HJ

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const hexToDec = {
  a: 10,
  b: 11,
  c: 12,
  d: 13,
  e: 14,
  f: 15,
  g: 16,
};

rl.on("line", function (line) {
  let decValue = 0;
  let hexValue = line.replace(
    /0x/g, "").toLowerCase();
  while (hexValue.length > 0) {
    let decNumber = hexToDec[
      hexValue.substring(0, 1)
    ];
    decValue +=
      (decNumber ? decNumber :
        hexValue.substring(0, 1)
      ) * Math.pow(
        16, hexValue.length - 1
      );
    hexValue =
      hexValue.substring(1);
  }
  console.log(decValue);
});