10w字！前端知识体系+大厂面试总结（算法篇）开发者社区

10w字！前端知识体系+大厂面试总结（算法篇）

// 该算法用的是动态规划的思想，时间复杂度为n²，并不是最优算法，最优算法应该是二分查找，最优时间复杂度为nlogn
function lengthOfLIS(nums) {
  if (!nums.length) return 0;
  // 创建一个和原数组等长的数组dp，用来存储每一项的最长递增子序列，比如[1,2,2] 表示第二项和第三项的最长递增子序列都为2
  // 该数组每一项初始值都为1，记录当前项的最长递增子序列，后面的项会在当前项的最长递增子序列个数进行累加
  let dp = new Array(nums.length).fill(1);
  // 双层for循环，每一项都和之前的所有项一一进行比较，计算出该项的最长递增子序列个数，存储到dp中
  for (let i = 0; i < nums.length; i++) {
    // 当前项依次和之前的每一项进行比较，累加出当前项的最长递增子序列
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        // 比较当前项已有的最大值和之前项最大值，比如当比较到第三项[1,2,2]时，如第三项比第二项大，所以第三项的计算结果为[1,2,3]
        dp[i] = Math.max(dp[i], dp[j] + 1);
  // 取出一组最长递增子序列的具体值（注意：最长递增子序列有可能有多组值，这里是只取出其中一组值）
  // 找到dp中的最大值，该值就是nums的最长递增子序列的个数
  let max = Math.max(...dp);
  let result = [];
  for (let i = max; i >= 1; i--) {
    // 倒序遍历，根据长度获取对应的值
    findArrNode(dp, i, result, nums);
  return result;
function findArrNode(dp, value, result, arr) {
  // 找到符合条件最后一项的下标，这样才能保证数组的顺序是正确的
  let index = dp.lastIndexOf(value);
  // 存储对应的值
  result.unshift(arr[index]);
  // 对dp进行截取，保证只取最大项之前的数据
  dp.length = index + 1;
// 测试
console.log(lengthOfLIS([9, 1, 7, 10, 4, 8, 5, 2])); // [1, 4, 5]
console.log(lengthOfLIS([1, 4, 3, 5, 2, 6, 0])); // [1, 3, 5, 6]

/**
 * 贪心算法求解
 * @param {array} list - 股票每天的价格列表
 * @param {number} fee - 手续费
function buyStock(list, fee) {
  // min为当前的最小值，即买入点
  let min = list[0],
    sum = 0;
  for (let i = 1; i < list.length; i++) {
    // 从1开始，依次判断
    if (list[i] < min) {
      // 寻找数组的最小值
      min = list[i];
    } else {
      // 计算如果当天卖出是否赚钱
      let temp = list[i] - min - fee;
      if (temp > 0) {
        // 赚钱 存数据
        sum += temp;
        // 关键代码：重新计算min，分两种情况，如果后面继续涨，则默认继续持有；若后面跌，则以后面的价格重新买入
        min = list[i] - fee;
  return sum;
console.log(buyStock([1, 12, 13, 9, 15, 8, 6, 16], 2)); // 22

/**
 * 贪心算法求解交易明细
 * @param {array} list - 股票每天的价格列表
 * @param {number} fee - 手续费
function buyStock(list, fee) {
  // 增加result对象，把每笔赚钱的交易都记录下来
  let result = {};
  let min = list[0],
    // 增加minIndex 用来记录每次买入值（最小值）的变化
    minIndex = 0,
    sum = 0;
  for (let i = 1; i < list.length; i++) {
    if (list[i] < min) {
      minIndex = i;
      min = list[i];
    } else {
      let temp = list[i] - min - fee;
      if (temp > 0) {
        sum += temp;
        min = list[i] - fee;
        // 赚钱 存数据
        // 当minIndex不变时，用新的记录替换调老的记录
        result[minIndex] = [list[minIndex], list[i]];
  let arr = [];
  // 遍历result对象，取出所存储的交易明细
  Object.keys(result).forEach(key => {
    arr.push(result[key]);
  return {
console.log(buyStock([1, 12, 13, 9, 15, 8, 6, 16], 2));
// 打印结果： {sum: 22, arr: [[1, 13], [9, 15], [6, 16]]}

function findCoins(coins, amount) {
  if (coins.length === 0) return -1;
  // 用于保存每个目标总额对应的最小硬币个数
  const f = [];
  // 提前定义已知情况
  f[0] = 0;
  // 遍历 [1, amount] 这个区间的硬币总额
  for (let i = 1; i <= amount; i++) {
    // 求的是最小值，因此我们预设为无穷大，确保它一定会被更小的数更新
    f[i] = Infinity;
    // 循环遍历每个可用硬币的面额
    for (let j = 0; j < coins.length; j++) {
      // 若硬币面额小于目标总额，则问题成立
      if (i - coins[j] >= 0) {
        // 状态转移方程
        f[i] = Math.min(f[i], f[i - coins[j]] + 1);
  // 若目标总额对应的解为无穷大，则意味着没有一个符合条件的硬币总数来更新它，本题无解，返回-1
  if (f[amount] === Infinity) {
    return -1;
  // 若有解，直接返回解的内容
  return f[amount];
console.log(findCoins([1, 2, 5], 11)); // 3

function printMinNumber(arr) {
  if (!arr || arr.length == 0) return null;
  // sort底层是快排
  return arr.sort(compare).join("");
// 找到ab 和 ba 这两种组合的最小值
function compare(a, b) {
  let front = `${a}${b}`;
  let after = `${b}${a}`;
  return front - after;
let arr = [3, 45, 12];
console.log(printMinNumber(arr)); // 12345

function exchangeOddEven(arr) {
  let start = 0;
  let end = arr.length - 1;
  // 当start > end时，完成交换
  while (start < end) {
    // 找到第一个偶数
    while (arr[start] % 2 === 1) {
      start++;
    // 找到第一个奇数
    while (arr[end] % 2 === 0) {
      end--;
    // 重点：始终要加上 start < end的限制，否则会出现中间两个数的位置交换错误
    if (start < end) {
      // 奇数和偶数交换位置
      [arr[start], arr[end]] = [arr[end], arr[start]];
  return arr;
let test = [2, 4, 5, 3, 1];
console.log(exchangeOddEven(test)); // [1, 3, 5, 4, 2]

// 时间复杂度O(n)、 空间复杂度O(n)
function twoNumAdd(arr, target) {
  if (Array.isArray(arr)) {
    // 使用map将遍历过的数字存起来
    let map = {};
    for (let i = 0; i < arr.length; i++) {
      // 从map中查找是否有key 等于 target-nums[i]，如果取到了，则条件成立，返回结果
      if (map[target - arr[i]] !== undefined) {
        return [target - arr[i], arr[i]];
      } else {
        // 条件不成立，则将已遍历的值存起来
        map[arr[i]] = i;
  return [];
console.log(twoNumAdd([8, 2, 6, 5, 4, 1, 3], 7)); // [2, 5]

function findThree(arr, target) {
  arr.sort();
  let result = [];
  for (let i = 0; i < arr.length; i++) {
    // 跳过重复的arr[i]值, 比如[2, 1, 1],跳过第二个1
    if (i && arr[i] === arr[i - 1]) continue;
    let left = i + 1;
    let right = arr.length - 1;
    while (left < right) {
      let sum = arr[i] + arr[left] + arr[right];
      if (sum > target) {
        right--;
      } else if (sum < target) {
        left++;
      } else {
        // arr[left++], 先取arr[left]，然后left++, 两步合成一步；arr[right--]同样的逻辑
        result.push([arr[i], arr[left++], arr[right--]]);
        while (arr[left] === arr[left - 1]) {
          // 跳过重复的arr[left]值,
          left++;
        while (arr[right] === arr[right + 1]) {
          // 跳过重复的arr[right]值
          right--;
  return result;
console.log(findThree([5, 2, 1, 1, 3, 4, 6], 8)); //  [1, 1, 6] [1, 2, 5] [1, 3, 4]

function findFour(arr, target) {
  if (arr.length < 4) return [];
  let result = [];
  arr.sort();
  // 最外层控制循环次数，循环次数为arr.length - 3
  for (let i = 0; i < arr.length - 3; i++) {
    // 跳过数组中，重复的起始值
    if (i && arr[i] === arr[i - 1]) continue;
    // 因为数组已进行排序，所有一旦超过目标值，那么以后的值也都比目标值大，所以可以直接结束这一轮循环
    if (arr[i] + arr[i + 1] + arr[i + 2] + arr[i + 3] > target) break;
    for (let j = i + 1; j < arr.length - 2; j++) {
      // 注意范围，第二个值的最小值是倒数第3位（以下的代码和三个数求和的逻辑一致）
      // 跳过数组中，第二个值重复的
      if (j > i + 1 && arr[j] === arr[j - 1]) continue;
      // 第三个数的下标
      let left = j + 1;
      let right = arr.length - 1;
      while (left < right) {
        let sum = arr[i] + arr[j] + arr[left] + arr[right];
        if (sum > target) {
          right--;
        } else if (sum < target) {
          left++;
        } else {
          // 坑点，注意添加后，left++， right--, 确保循环继续执行
          result.push([arr[i], arr[j], arr[left++], arr[right--]]);
          while (arr[left] === arr[left - 1]) {
            // 跳过重复的值
            left++;
          while (arr[right] === arr[right + 1]) {
            // 跳过重复的值
            right--;
  return result;
console.log(findFour([2, 1, 5, 4, 3, 6, 0, 7], 10)); // [0, 1, 2, 7]   [0, 1, 3, 6] [0, 1, 4, 5] [0, 2, 3, 5] [1, 2, 3, 4]

function FindContinuousSequence(sum) {
  let result = [];
  // 记录当前的结果
  let child = [1, 2];
  let small = 1; // 初始值1
  let big = 2; //
  let currentSum = 3; // 当前数字之和
  while (big < sum) {
    // big等于sum时，child中只剩一个数，不满足连续正数序列的要求，结束循环
    while (currentSum < sum && big < sum) {
      child.push(++big);
      // currentSum为当前child的和
      currentSum += big;
    while (currentSum > sum && small < big) {
      child.shift();
      // 因为删除了最小值，所以small也要响应变化，增加1
      currentSum -= small++;
    if (currentSum === sum && child.length > 1) {
      // child.length大于1，剔除一个数等于sum的情况
      // child.slice返回一个新的数组
      result.push(child.slice());
      child.push(++big);
      currentSum += big;
  return result;
console.log(FindContinuousSequence(15)); // [1, 2, 3, 4, 5] [4, 5, 6] [7, 8]

function printMatrix(arr) {
  // map函数用来完成当前矩阵最外一圈的遍历
  // @param1{Array}二维数组 arr 表示当前矩阵
  // @param2{Array}一维数组 result 用来保存遍历结果
  let map = (arr, result) => {
    // 矩阵的高度即行数
    let n = arr.length;
    // 遍历矩阵的每一行
    for (let i = 0; i < n; i++) {
      // 若第一行 按顺序插入
      if (i === 0) {
        result = result.concat(arr[i]);
      } else if (i === n - 1) {
        // 若最后一行 倒序插入
        result = result.concat(arr[i].reverse());
      } else {
        // 若中间行 插入该行最后一个元素 并将该元素从矩阵中删除
        result.push(arr[i].pop());
    // 将已经遍历的第一行和最后一行从矩阵中删除
    arr.pop();
    arr.shift();
    // 遍历插入最左侧一列 此时删除首位两行后矩阵高度已变为n-2
    for (let j = n - 3; j >= 0; j--) {
      // 避免arr[j]长度为空时插入undefined
      if (arr[j].length) {
        result.push(arr[j].shift());
    // 截止条件 矩阵有元素就继续递归
    if (arr.length) {
      // 把已将遍历元素删除的矩阵进行递归
      return map(arr, result);
    } else {
      return result;
  // 将初始矩阵传入, 保存结果的数组初始为空
  return map(arr, []);
let matrix = [
  [1, 2, 3],
  [4, 5, 6],
  [7, 8, 9]
console.log(printMatrix(matrix)); // [1, 2, 3, 6, 9, 8, 7, 4, 5]

function fib(n) {
  // 使用dp数组，将之前计算的结果存起来，防止栈溢出
  let dp = [];
  dp[0] = 1n; //  bigint  可以用来表示超过2^53-1的大整数
  dp[1] = 1n;
  for (let i = 2; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2]; // 注意：arr[i]
  return dp[n];
console.log(fib(1000));

// 二叉树节点
class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
// 构建二叉树
class Tree {
  constructor() {
    this.root = null;
  insert(data) {
    var node = new Node(data, null, null);
    // 创建根节点
    if (!this.root) {
      this.root = node;
      return;
    var current = this.root;
    var parent = null;
    while (current) {
      parent = current;
      // 值比父节点小，放到父节点的左子树上
      if (data < parent.data) {
        current = current.left;
        // 找到最左侧的节点，将新的节点设置为该节点的左子树节点
        if (!current) {
          parent.left = node;
          return;
      } else {
        // 值比父节点大，放到父节点的右子树上
        current = current.right;
        if (!current) {
          parent.right = node;
          return;
  // 定义前序遍历的方法
  static preOrder(node, arr = []) {
    if (node) {
      arr.push(node.data);
      this.preOrder(node.left, arr);
      this.preOrder(node.right, arr);
    return arr;
  // 定义中序遍历的方法
  static middleOrder(node, arr = []) {
    if (node) {
      this.middleOrder(node.left, arr);
      arr.push(node.data);
      this.middleOrder(node.right, arr);
    return arr;
  // 定义后序遍历的方法
  static laterOrder(node, arr = []) {
    if (node) {
      this.laterOrder(node.left, arr);
      this.laterOrder(node.right, arr);
      arr.push(node.data);
    return arr;
  // 获取二叉树的最大层级
  static getDeep(node, deep = 0) {
    if (!node) {
      return deep;
    deep++;
    // 获取左子树的层级
    let left = this.getDeep(node.left, deep);
    // 获取右子树的层级
    let right = this.getDeep(node.right, deep);
    // 取层级最大的值
    return Math.max(left, right);
// 创建二叉树，依次插入新节点
var t = new Tree();
t.insert(5);
t.insert(3);
t.insert(6);
t.insert(2);
t.insert(4);
t.insert(7);
t.insert(8);
t.insert(1);
t.insert(9);
// 打印二叉树
console.log(t);
// 前序遍历  [5, 3, 2, 1, 4, 6, 7, 8, 9]
console.log(Tree.preOrder(t.root));
// 中序遍历 [1, 2, 3, 4, 5, 6, 7, 8, 9]
console.log(Tree.middleOrder(t.root));
// 后序遍历 [1, 2, 4, 3, 9, 8, 7, 6, 5]
console.log(Tree.laterOrder(t.root));
// 获取二叉树的最大层级：5
console.log(Tree.getDeep(t.root));

function middleTraverse(root) {
  const result = [];
  // stack 用来存储回溯算法中的节点
  const stack = [];
  let current = root;
  while (current || stack.length > 0) {
    // 找到最左侧的节点
    while (current) {
      // 依次将左子树节点存到栈中
      stack.push(current);
      current = current.left;
    // 节点出栈
    current = stack.pop();
    // 存储该节点的值
    result.push(current.data);
    // 获取该节点的右子树节点
    current = current.right;
  return result;
// t 为上文创建的二叉树
console.log(middleTraverse(t.root));
// 打印结果： [1, 2, 3, 4, 5, 6, 7, 8, 9]

// 重建二叉树
function reConstruction(pre, mid) {
  if (pre.length === 0) {
    return null;
  // 前序遍历长度为1时，该节点为叶子节点
  if (pre.length === 1) {
    return new Node(pre[0]);
  // 前序遍历的第一个值为根节点
  const value = pre[0];
  // 找到根节点在中序遍历的位置
  const index = mid.indexOf(value);
  // 将中序遍历 分为左子树中序遍历 和 右子数中序遍历
  const midLeft = mid.slice(0, index);
  const midRight = mid.slice(index + 1);
  // 左子树前序遍历的长度为index
  // 将前序遍历 分为左子树前序遍历 和 右子树前序遍历
  const preLeft = pre.slice(1, index + 1);
  const preRight = pre.slice(index + 1);
  // 创建根节点
  const node = new Node(value);
  // 利用左子树中序遍历 + 左子树前序遍历，递归创建左子树节点
  node.left = reConstruction(preLeft, midLeft);
  // 递归创建右子树节点
  node.right = reConstruction(preRight, midRight);
  return node;
class Node {
  constructor(data, left = null, right = null) {
    this.data = data;
    this.left = left;
    this.right = right;
reConstruction([1, 2, 4, 7, 3, 5, 6, 8], [4, 7, 2, 1, 5, 3, 8, 6]);

// 查找一个节点
function findNode(data, node) {
  if (node) {
    if (data === node.data) {
      return node;
    } else if (data < node.data) {
      return this.findNode(data, node.left);
    } else {
      return this.findNode(data, node.right);
  } else {
    return null;
// 查找值为6的节点
// t 为上文创建的二叉树
console.log(findNode(6, t.root));

// 最大值：最右侧的节点
function getMax(root) {
  let max = null;
  let current = root;
  while (current !== null) {
    max = current.data;
    current = current.right;
  return max;
// 最小值：最左侧的节点
function getMix(root) {
  let mix = null;
  let current = root;
  while (current !== null) {
    mix = current.data;
    current = current.left;
  return mix;
console.log(getMax(t.root), "max"); // 9
console.log(getMix(t.root), "min"); // 1

// 判断一个整数数组，是否为某二叉查找树的前序遍历的结果
function preOrderOfBST(list) {
  if (list && list.length > 0) {
    // 前序遍历，第一个值为根节点
    var root = list[0];
    // 找到数组中，第一个比根节点大的节点，即为右子树的节点
    for (var i = 0; i < list.length; i++) {
      if (list[i] > root) {
        break;
    // 遍历右子树的节点，要求所有右子树的节点都比根节点大
    for (let j = i; j < list.length; j++) {
      if (list[j] < root) {
        return false;
    var left = true;
    // 同理，递归判断左子树是否符合二叉搜索树的规则
    if (i > 1) {
      left = preOrderOfBST(list.slice(1, i + 1));
    var right = true;
    // 递归判断右子树是否符合二叉搜索树的规则
    if (i < list.length) {
      right = preOrderOfBST(list.slice(i, list.length));
    // 左、右子树 都符合要求，则是一个二叉搜索树
    return left && right;
console.log(preOrderOfBST([5, 3, 2, 1, 4, 6, 7, 8, 9])); // true

// 判断一个整数数组，是否为某二叉搜索树的后序遍历的结果
function laterOrderOfBST(list) {
  if (list && list.length > 0) {
    // 后续遍历，最后一个节点为根节点
    var root = list[list.length - 1];
    for (var i = 0; i < list.length - 1; i++) {
      if (list[i] > root) {
        break;
    for (let j = i; j < list.length - 1; j++) {
      if (list[j] < root) {
        return false;
    var left = true;
    // 判断左子树
    if (i > 0) {
      left = laterOrderOfBST(list.slice(0, i));
    var right = true;
    // 判断右子树
    if (i < list.length - 1) {
      right = laterOrderOfBST(list.slice(i, list.length - 1));
    return left && right;
console.log(laterOrderOfBST([1, 2, 4, 3, 9, 8, 7, 6, 5])); // true

/**
 * 找到和为某一值的路径
 * @param {object} node - 二叉树
 * @param {number} num - 和（目标值）
 * @param {array} stack - 栈
 * @param {number} sum - 当前路径的和
 * @param {array} result - 存储所有的结果
function findPath(node, num, stack = [], sum = 0, result = []) {
  stack.push(node.data);
  sum += node.data;
  // 找到所有的节点路径(包含叶子节点和子节点的所有情况之和)
  if (sum === num) {
    // if (!node.left && !node.right && sum === num) {  // 找到所有的叶子节点路径
    result.push(stack.slice());
  if (node.left) {
    findPath(node.left, num, stack, sum, result);
  if (node.right) {
    findPath(node.right, num, stack, sum, result);
  // 回溯算法：不符合要求，退回来，换一条路再试
  // 叶子节点直接pop；子节点中的所有的节点递归完成后再pop
  stack.pop();
  return result;
// t 为上文创建的二叉树
console.log(findPath(t.root, 11)); // [5, 3, 2, 1], [5, 6]

function heapSort(list, m) {
  if (m > list.length) {
    return [];
  createHeap(list, m);
  for (let i = m; i < list.length; i++) {
    if (list[i] < list[0]) {
      // 找到前m个数的最小值，依次将最小值放到最前面
      [list[i], list[0]] = [list[0], list[i]];
      ajustHeap(list, 0, m);
  // 取出前m个数
  return list.splice(0, m);
// 构建大顶堆（构建的顺序是从下往上，先找到最后一个父节点，然后从最后一个父节点开始构建，然后依次往上构建，将最大值逐步替换成根节点）
function createHeap(arr, length) {
  // 找到堆中所有的非叶子节点（找到最后一个叶子节点，该节点之前都是非叶子节点）
  for (let i = Math.floor(length / 2) - 1; i >= 0; i--) {
    // 堆中，父节点为i，则子节点为2*i+1、2*i+2；反过来，知道了子节点为length,则最后一个子节点为Math.floor(length / 2) - 1。
    ajustHeap(arr, i, length); // 调整大顶堆，将最大值逐步替换成根节点
// 调整大顶堆（注意：调整的顺序是从上往下，将根节点替换后，先调整根节点，然后依次往下调整，对应的子节点如果发生替换，要重新调整下对应子节点，保证都满足子节点不大于父节点的条件，直到该大顶推全部调整完成）
// 比如，当调节根节点时，[a0, a1, a2], a2> a0, a2替换a0，则要重新调节a2这个分支上的节点，保证都满足子节点不大于父节点的条件
function ajustHeap(arr, index, length) {
  for (let i = 2 * index + 1; i < length; i = 2 * i + 1) {
    // 父节点为i，则子节点为2*i+1
    if (i + 1 < length && arr[i + 1] > arr[i]) {
      // 找到arr[i + 1] 和 arr[i] 中的最大值
    // 如果子节点比父节点大，交换两者的位置，将最大值移动到顶部
    if (arr[index] < arr[i]) {
      [arr[index], arr[i]] = [arr[i], arr[index]];
      index = i;
    } else {
      break;
console.log(heapSort([5, 10, 2, 15, 1, 12, 6], 4)); // [6, 5, 2, 1]


let tree = [
id: "1",
title: "节点 1",
children: [
id: "1-1",
title: "节点 1-1"
id: "1-2",
title: "节点 1-2"
id: "2",
title: "节点 2",
children: [
id: "2-1",
title: "节点 2-1"


function listToTree(data) {
// 使用对象重新存储数据, 空间换时间
let map = {};
// 存储最后结果
let treeData = [];
// 遍历原始数据 data，存到 map 中，id 为 key，值为数据
for (let i = 0; i < data.length; i++) {
map[data[i].id] = data[i];
// 遍历对象
for (let i in map) {
// 根据 parentId 找到的是父节点
if (map[i].parentId) {
if (!map[map[i].parentId].children) {
map[map[i].parentId].children = [];
// 将子节点 放到 父节点的 children 中
map[map[i].parentId].children.push(map[i]);
} else {
// parentId 找不到对应值，说明是根结点，直接插到根数组中
treeData.push(map[i]);
return treeData;
// 测试
let list = [
{ id: 1, title: "child1", parentId: 0 },
{ id: 2, title: "child2", parentId: 0 },
{ id: 6, title: "child2_1", parentId: 2 },
{ id: 4, title: "child1_1", parentId: 1 },
{ id: 5, title: "child1_2", parentId: 1 },
{ id: 3, title: "child3", parentId: 0 },
{ id: 7, title: "child3_1", parentId: 3 }
console.log(listToTree(list));


function deepTree(tree, arr = []) {
tree.forEach(data => {
arr.push(data.id);
// 遍历子树
data.children && deepTree(data.children, arr);
return arr;
let tree = [
id: "1",
title: "节点 1",
children: [
id: "1-1",
title: "节点 1-1"
id: "1-2",
title: "节点 1-2"
id: "2",
title: "节点 2",
children: [
id: "2-1",
title: "节点 2-1"
console.log(deepTree(tree)); // ['1', '1-1', '1-2', '2', '2-1']


// 广度优先
function rangeTree(tree, arr = []) {
let node,
list = [...tree];
while ((node = list.shift())) {
arr.push(node);
node.children && list.push(...node.children);
return arr;
let tree = [
id: "1",
title: "节点 1",
children: [
id: "1-1",
title: "节点 1-1"
id: "1-2",
title: "节点 1-2"
id: "2",
title: "节点 2",
children: [
id: "2-1",
title: "节点 2-1"
console.log(rangeTree(tree)); //  ['1', '2', '1-1', '1-2', '2-1']


function findTreeNode(tree, func) {
for (const data of tree) {
// 条件成立 直接返回
if (func(data)) return data;
if (data.children) {
const res = findTreeNode(data.children, func);
// 结果存在再返回
if (res) return res;
return null;
let tree = [
id: "1",
title: "节点 1",
children: [
id: "1-1",
title: "节点 1-1"
id: "1-2",
title: "节点 1-2"
id: "2",
title: "节点 2",
children: [
id: "2-1",
title: "节点 2-1"
console.log(
findTreeNode(tree, data => {
return data.title === "节点 1-1";
// 打印结果： {id: '1-1', title: '节点 1-1'}


function compareVersion(str1, str2) {
// 创建 rc beta alpha，对应的权重值，将版本号转化为纯数字
let map = { rc: 3, beta: 2, alpha: 1 };
Object.keys(map).forEach(key => {
str1 = str1.replace(key, map[key]);
str2 = str2.replace(key, map[key]);
const arr1 = str1.split(".");
const arr2 = str2.split(".");
function fn(arr1, arr2) {
let i = 0;
while (true) {
// 取出相同位置的数字
const s1 = arr1[i];
const s2 = arr2[i];
// 若 s1 或 s2 不存在，说明相同的位置已比较完成，剩余的位置比较 arr1 与 arr2 的长度，长的版本号大
if (s1 === undefined || s2 === undefined) {
return arr1.length - arr2.length;
if (s1 === s2) continue;
// 比较相同位置的数字大小
return s1 - s2;
return fn(arr1, arr2);
// 测试
let str1 = "1.rc.2.1";
let str2 = "1.beta.2";
console.log(compareVersion(str1, str2)); // 1


// 方法一：
// 先使用 Set 去重
// 然后两层遍历，时间复杂度为 O(n²)
function findAlone(str) {
let arr = str.split("");
// 通过 set 去重
let aloneArr = [...new Set(arr)];
let val = "";
for (let i = 0; i <= aloneArr.length - 1; i++) {
// 用原始字符串进行遍历 找到唯一的值
if (arr.filter(item => item == aloneArr[i]).length == 1) {
val = aloneArr[i];
break;
return val ? arr.indexOf(val) : -1;
let str = "abcabcde";
console.log(findAlone(str)); // 6
// 方法二：
// 思路: 使用 map 存储每个字符出现的次数
// 该方法时间复杂度和空间复杂度均为 O(n), 从时间上来说，要比第一种方法快
function findAlone1(str) {
if (!str) return -1;
// 使用 map 存储每个字符出现的次数
let map = {};
let arr = str.split("");
arr.forEach(item => {
let val = map[item];
// val 为 undefined 时，表示未存储，map[item] = 1；否则 map[item] = val + 1
map[item] = val ? val + 1 : 1;
// 一次遍历结果后，再遍历一遍找到出现 1 次的值
for (let i = 0; i < arr.length; i++) {
if (map[arr[i]] == 1) {
return i;
return -1;
console.log(findAlone1(str)); // 6


/\*\*
- 计算所有字符串的组合
- @param {array} list - 字符串列表
- @param {array} result - 最终的结果
- @param {string} current - 当前的字符串
- @param {string} temp - 当前固定的字符
- \*/
  function stringGroup(list = [], result = [], current = "", temp = "") {
  current += temp;
  if (list.length === 0) {
  // 递归的出口，将对应结果添加到 list 中
  return result.push(current);
  for (let i = 0; i < list.length; i++) {
  // 每次递归 固定第一个字符
  temp = list.shift();
  stringGroup(list, result, current, temp);
  // 将删除的 temp 重新添加到 queue 尾部，实现将数组反转的效果，如[a,b,c]反转为[c,b,a]
  list.push(temp);
  // 这里去重是解决 str 中有重复的字母，比如 str 为'aacd'
  return [...new Set(result)];
  console.log(stringGroup("abc".split(""))); // ['abc', 'acb', 'bca', 'bac', 'cab', 'cba']


// 方法一： 将字符串切分为数组，再逆序，再连接为字符串
function isReserveSame(str) {
let temp = str
.split("")
.reverse()
.join("");
return temp === str;
console.log(isReserveSame("abcba")); // true
// 方法二： 循环遍历，判断对称位置的字符是否相等
function isReserveSame1(s) {
let flag = true;
for (let i = 0; i < parseInt(s.length / 2); i++) {
if (s.charAt(i) !== s.charAt(s.length - 1 - i)) {
flag = false;
return flag;
console.log(isReserveSame1("abcba")); // true


// 链表 Node 节点
function Node(data) {
this.data = data;
this.next = null;
// 创建链表
class LinkedList {
constructor() {
this.count = 0; // 链表长度
this.head = null; // 链表开头
// 添加节点
push(data) {
let node = new Node(data);
if (!this.head) {
this.head = node;
} else {
let current = this.head;
while (current.next) {
current = current.next;
current.next = node;
this.count++;
// 插入节点
insert(data, index) {
if (index >= 0 && index <= this.count) {
let node = new Node(data);
let current = this.head;
if (index == 0) {
// 插到表头
this.head = node;
node.next = current;
} else {
for (let i = 0; i < index - 1; i++) {
// 找到要插入位置的前一个元素
current = current.next;
let next = current.next; // 暂存 next 以后的节点信息
current.next = node;
node.next = next;
this.count++;
// 返回插入成功的结果
return true;
} else {
return false;
// 按索引值查找
getIndexNode(index) {
if (index >= 0 && index < this.count) {
let current = this.head;
for (let i = 0; i < index; i++) {
current = current.next;
return current;
} else {
return null;
// 按索引值删除节点
removeNode(index) {
if (index >= 0 && index < this.count) {
if (index == 0) {
this.head = this.head.next;
} else {
let current = this.head;
const pre = this.getIndexNode(index - 1); // 找到要删除元素的前一个元素
current = pre.next; // 获取要删除的元素
pre.next = current.next;
this.count--;
return true;
} else {
return false;
// 查找节点的位置
indexOf(data) {
let current = this.head;
for (let i = 0; i < this.count; i++) {
if (data === current.data) {
return i;
current = current.next;
// 链表转字符串
toString() {
let current = this.head;
    let string = `${current.data}`;
    // current长度大于1，取下一个节点
    if (this.count > 1) current = current.next;
    for (let i = 1; i < this.count; i++) {
      string = `${string},${current.data}`;
      current = current.next;
    return string;
// 测试
const link = new LinkedList();
// 增加 5 个节点
for (let i = 1; i <= 5; i++) {
link.push(i);
// 索引为 1 的位置 插入节点 6
link.insert(6, 1);
// 获取索引 2 的节点
console.log(link.getIndexNode(2));
// 删除索引 3 的节点
console.log(link.removeNode(3));
// 查找位为 6 的索引
console.log(link.indexOf(6));
// 链表转字符串 1,6,2,4,5
console.log(link.toString());


const link = new LinkedList();
// 增加 5 个节点
for (let i = 1; i <= 5; i++) {
link.push(i);
// 创建环形链表，找到值为 5 的节点，将该节点的 next 指向值为 3 的节点
link.getIndexNode(4).next = link.getIndexNode(2);


// 查找环形链表节点
function EntryNodeOfLoop(head) {
if (!head || !head.next) {
return null;
let p1 = head.next;
// p2 一次走两步
let p2 = head.next.next;
// 若 p1 === p2 则证明该链表有环
while (p1 !== p2) {
if (p1 == null || p2.next === null) {
return null;
p1 = p1.next;
p2 = p2.next.next;
// 此时 p1 是 p1、p2 重合的点
let temp = p1;
let length = 1;
p1 = p1.next;
// 获取环的长度
while (p1 !== temp) {
p1 = p1.next;
length++;
// 找公共节点
// 此时为什么要将 p1 p2 重新赋值，因为 p2 只是重合的点，不一定是入口节点
p1 = p2 = head;
while (length-- > 0) {
p2 = p2.next;
while (p1 !== p2) {
p1 = p1.next;
p2 = p2.next;
return p1;
const link = new LinkedList();
// 增加 5 个节点
for (let i = 1; i <= 5; i++) {
link.push(i);
// 创建环形链表，值为 5 的节点，next 指向值为 3 的节点
link.getIndexNode(4).next = link.getIndexNode(2);
console.log(EntryNodeOfLoop(link.head)); // 打印节点 3


// 使用链表形成一个闭环，最后一个元素的指针指向第一个元素
function findLastNode(n, m) {
if (n < 1 || m < 1) return -1;
const head = { val: 0 };
let current = head;
for (let i = 1; i < n; i++) {
// 生成一个链表
current.next = { val: i };
// 将 next 下一项赋值给 current
current = current.next;
// 尾部指向头部，形成闭环
current.next = head;
while (current.next != current) {
// 此时 current 是最后一个节点
for (let i = 0; i < m - 1; i++) {
// 找到要删除节点的前一个节点（范围是 m-1,这里是从最后一个节点开始；如果是从 head 开始，范围则是 m-2）
current = current.next;
// 删除第 m 个节点
current.next = current.next.next;
return current.val;
console.log(findLastNode(5, 3)); // 3


// 创建栈 只能从栈尾添加和删除 实现先进后出的效果
class Stack {
constructor() {
this.arr = [];
// 从栈尾添加
insert(data) {
this.arr.push(data);
// 从栈尾删除
del() {
return this.arr.pop();
toString() {
return this.arr.toString();
let stack = new Stack();
stack.insert(1);
stack.insert(2);
stack.insert(3);
stack.del();
console.log(stack.toString()); // 1,2


// 创建队列 只能从栈尾添加和头部删除 实现先进先出的效果
class Queue {
constructor() {
this.arr = [];
insert(data) {
this.arr.push(data);
del() {
return this.arr.shift();
toString() {
return this.arr.toString();
let queue = new Queue();
queue.insert(1);
queue.insert(2);
queue.insert(3);
queue.del();
console.log(queue.toString()); // 2,3


// 判断两个整数序列，第一个序列为入栈顺序，第二个序列是否为出栈顺序
function isSameStack(arr, arr1) {
// 创建一个栈，模拟入栈、出栈的过程
let stack = [];
// id 用来记录 arr1 已出栈的位置
let id = 0;
for (let i = 0; i < arr.length; i++) {
// 入栈
stack.push(arr[i]);
// 当 stack 栈顶元素和 arr1 栈顶元素相同时，stack 出栈；索引 id+1，
while (stack.length && stack[stack.length - 1] === arr1[id]) {
// 出栈
stack.pop();
// 下次要对比 arr1[id+1]与 stack 栈顶元素是否相等
id++;
// 最终 stack 栈为空，表示 arr 全部元素已出栈
return stack.length == 0;
console.log(isSameStack([1, 2, 3, 4, 5], [2, 4, 5, 3, 1])); // true


function maxSlidingWindow(nums, k) {
// window 存储当前窗口中数据的下标
const window = [];
// result 存储窗口中的最大值
const result = [];
for (let i = 0; i < nums.length; i++) {
if (i - window[0] > k - 1) {
// 窗口不断往右移动，当最大值在窗口最左侧，但窗口的长度超出 k 时的情况，就要把左侧的最大值剔除，比如窗口为【3,-1,-3】，继续往右时，就要把左侧的 3 剔除
window.shift(); // 剔除窗口长度超出范围时左侧的最大值
for (let j = window.length - 1; j >= 0; j--) {
// 当前窗口的值依次和要插入的值做比较，如果小于要插入的值，剔除掉该值，直到 window 为空为止（保证 window 中最左侧的值为最大值）
if (nums[window[j]] <= nums[i]) {
window.pop();
// 添加右侧新加入的值，插入新值时有两种情况：
// 1、新值为最大值时，则 window 此时为空；
// 2、新值不为最大值时，window 已剔除掉比新值小的值。
// 始终保证 window 中最左侧的值为最大值
window.push(i);
if (i >= k - 1) {
// 窗口是从 0 开始移动，当移动的距离，大于等于目标范围后，以后再往后移动一次，就要写入当前窗口的最大值
result.push(nums[window[0]]);
return result;
console.log(maxSlidingWindow([1, 3, -1, -3, 5, 3, 6, 7], 3)); // [3, 3, 5, 5, 6, 7]


function bubbleSort(arr) {
const length = arr.length;
// 外层循环用控制 排序进行多少轮
for (let i = 0; i < length; i++) {
// 内层循环用于每一轮的数据比较
// 注意 j 的长度范围 length - i - 1
for (let j = 0; j < length - i - 1; j++) {
// 相邻元素，大的放到后面
if (arr[j] > arr[j + 1]) {
// 交换位置
[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
return arr;
console.log(bubbleSort([8, 7, 1, 4, 3])); // [1,3,4,7,8]


function selectSort(arr) {
// 定义 index 存储最小值的下标
let index;
// 外层循环用控制 排序进行多少轮
for (let i = 0; i < arr.length - 1; i++) {
index = i;
// 内层循环用于每一轮的数据比较
// 注意 j 的起始范围是 i + 1
for (let j = i + 1; j < arr.length; j++) {
// 寻找最小值
if (arr[j] < arr[index]) {
// 保存最小值的下标
index = j;
// 如果 index 不是目前的头部元素，则交换两者
if (index !== i) {
[arr[i], arr[index]] = [arr[index], arr[i]];
return arr;
console.log(selectSort([9, 1, 5, 3, 2, 8])); // [1, 2, 3, 5, 8, 9]


function insertSort(array) {
// 外层控制循环的次数
for (let i = 1; i < array.length; i++) {
let target = i;
// 内层循环用于每一轮的数据比较
for (let j = i - 1; j >= 0; j--) {
if (array[target] < array[j]) {
[array[target], array[j]] = [array[j], array[target]];
target = j;
} else {
break;
return array;
console.log(insertSort([9, 1, 5, 3, 2, 8])); // [1, 2, 3, 5, 8, 9]


// 快速排序
function quickSort(list) {
// 当 list.length <= 1 时，退出递归
if (list.length <= 1) return list;
// 找到中间节点
let mid = Math.floor(list.length / 2);
// 以中间节点为基准点，比该节点大的值放到 right 数组中，否则放到 left 数组中
let base = list.splice(mid, 1)[0];
let left = [];
let right = [];
list.forEach(item => {
if (item > base) {
right.push(item);
} else {
left.push(item);
// 重新组合数组
return quickSort(left).concat(base, quickSort(right));
console.log(quickSort([9, 1, 5, 3, 2, 8]));


function MergeSort(array) {
let len = array.length;
if (len <= 1) {
return array;
// 将给定的列表分为两半
let num = Math.floor(len / 2);
let left = MergeSort(array.slice(0, num));
let right = MergeSort(array.slice(num, array.length));
return merge(left, right);
function merge(left, right) {
let [l, r] = [0, 0];
let result = [];
while (l < left.length && r < right.length) {
if (left[l] < right[r]) {
result.push(left[l]);
} else {
result.push(right[r]);
result = result.concat(left.slice(l, left.length));
result = result.concat(right.slice(r, right.length));

10w字！前端知识体系+大厂面试总结（算法篇）

10w字！前端知识体系+大厂面试总结（算法篇）

正文

期待你的答案

算法

如何学习算法

算法基础知识

时间复杂度

空间复杂度

前端 数据结构

数组

最长递增子序列

买卖股票问题

买卖股票之交易明细

硬币找零问题

数组拼接最小值

奇偶排序

两数之和

三数之和

四数之和

连续整数之和

打印矩阵

斐波那契数列

二叉树

创建一棵二叉树

非递归版本实现中序遍历

重建二叉树

二叉查找树

二叉查找树搜索某个节点

二叉查找树的最大值和最小值

二叉查找树的前序遍历

二叉查找树的后续遍历

找到二叉树和为某一值的路径

堆

堆的作用

堆排序

树

列表转树

深度优先遍历

广度优先遍历

查找节点

字符串

版本号排序

第一个不重复字符的下标

字符串所有排列组合

字符串是否对称

链表

创建链表

环形链表

查找环形链表的入口节点

环中最后的数字

栈和队列

创建栈和队列

栈的入栈和出栈序列

滑动窗口最大值

排序算法

冒泡排序

选择排序

插入排序

快速排序

归并排序