17 算法

Huy大约 25 分钟anonymousnote

前端算法不多，但是还是可以总结一套 力扣热题 100 的知识点。在此篇中，不对数据结构做过多讨论，旨在梳理知识点。

哈希

在 JavaScript 中，哈希通常指的是哈希函数或哈希表的概念，而不是哈希值。

Set 和 Map 是两种常见的集合类型，它们是基于哈希表实现的，但它们并不是传统意义上的哈希表。

此外，Set 和 Map 都保证按插入顺序迭代，删除后重新添加会改变顺序，修改值不会改变顺序。这一点和普通对象不同。

Set 知识点

Set 使用哈希表来存储唯一值，但它的哈希表并不直接暴露给用户。

// 1.1 new Set() 创建一个空的 Set
const set = new Set()

// 1.2 可以通过传递一个可迭代对象（如数组）来初始化 Set。
const set = new Set([1, 2, 3, 4])

// 2 唯一性: Set 只存储唯一的值。如果尝试添加已经存在的值，add 操作将被忽略。
set.add(5)

// 3 大小: 使用 size 属性可以获取 Set 中值的数量。
const setSize = set.size()

// 4 判断值是否存在: 使用 has 方法可以检查值是否存在于 Set 中。
const hasVal = set.has(2) // true

// 5 删除: 使用 delete 方法可以删除 Set 中的特定值。
set.delete(2)

// 6 清空: 使用 clear 方法可以清空整个 Set。
set.clear()

// 7 迭代: Set 是可迭代的，可以使用 for...of 循环或 forEach 方法进行迭代

for (const item of set) {
  console.log(item)
}

set.forEach((item) => {
  console.log(item)
})

// 8 转换为数组: 可以使用 Array.from 或者扩展运算符 ... 将 Set 转换为数组
const arrayFromSet = Array.from(set)
const arraySpread = [...set]

Map 知识点

  1. 基本用法：

    • Map 是一个构造函数，用于创建一个空的 Map 对象。可以通过传递一个可迭代对象（如数组）来初始化 Map。
    const myMap = new Map()
myMap.set('key1', 'value1')
myMap.set('key2', 'value2')

  2. 键值对：

    • Map 存储键值对，其中每个键和值可以是任意类型的数据，包括原始值、对象、函数等。
    const complexMap = new Map()
const keyObj = { key: 'obj' }
complexMap.set(1, 'value1')
complexMap.set(keyObj, 'value2')

  3. 唯一性：

    • Map 中的键是唯一的，如果尝试使用相同的键添加新值，将会覆盖之前的值。
    complexMap.set(1, 'new value')
console.log(complexMap.get(1)) // 输出: 'new value'

  4. 大小：

    • 使用 size 属性可以获取 Map 中键值对的数量。
    console.log(complexMap.size) // 输出: 2

  5. 判断键是否存在：

    • 使用 has 方法可以检查键是否存在于 Map 中。
    console.log(complexMap.has(keyObj)) // 输出: true

  6. 获取值：

    • 使用 get 方法可以通过键获取对应的值。
    console.log(complexMap.get(1)) // 输出: 'new value'

  7. 删除键值对：

    • 使用 delete 方法可以删除 Map 中的特定键值对。
    complexMap.delete(keyObj)
console.log(complexMap.size) // 输出: 1

  8. 清空：

    • 使用 clear 方法可以清空整个 Map。
    complexMap.clear()
console.log(complexMap.size) // 输出: 0

  9. 迭代：

    • Map 是可迭代的，可以使用 for...of 循环或者 forEach 方法进行迭代。
    for (const [key, value] of complexMap) {
  console.log(key, value)
}

complexMap.forEach((value, key) => {
  console.log(key, value)
})

  10. 应用场景：

    • Map 在需要存储键值对，并且键可以是任意类型的场景中很有用，例如在处理对象作为键时比普通对象更方便。
    const objectAsKeyMap = new Map()
const objKey = { key: 'obj' }
objectAsKeyMap.set(objKey, 'value')
console.log(objectAsKeyMap.get(objKey)) // 输出: 'value'

算法题

1. 两数之和

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

function twoSum(nums: number[], target: number): number[] {
  // 创建哈希表
  const map = new Map() // {val, index}

  for (let i: number = 0; i < nums.length; i++) {
    const num = nums[i]

    if (map.has(target - num)) {
      return [map.get(target - num), i]
    } else {
      // 未找到
      map.set(num, i)
    }
  }

  return []
}

49. 字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

function groupAnagrams(strs: string[]): string[][] {
  const map = new Map()

  for (const str of strs) {
    const key = Array.from(str).sort().toString()
    const arr = map.has(key) ? map.get(key) : []
    arr.push(str)
    map.set(key, arr)
  }

  return Array.from(map.values()) // values 为值的迭代器
}

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

function longestConsecutive(nums: number[]): number {
  // 边界检测
  if (nums.length < 2) return nums.length

  // 哈希化储存数组
  const set: Set<number> = new Set()
  for (const num of nums) {
    set.add(num)
  }

  let maxLen: number = 1
  // 检测最长递增序列
  for (const num of set) {
    // 检测是否为起始最小值
    if (!set.has(num - 1)) {
      // 开始序列增长
      let left = num
      let len = 1
      while (set.has(++left)) {
        len++
      }

      // 更新最长序列
      if (len > maxLen) maxLen = len
    }
  }

  return maxLen
}

双指针

双指针主要处理数组和链表问题，常见的解法是左右指针和快慢指针以及较难的滑动窗口。

左右指针

左右指针常见的解题有回文判断、反转数组、二分法查找等。

  1. 回文判断

    function isPalindrome(str) {
  let left = 0,
    right = str.length - 1
  while (left < right) {
    if (str[left] !== str[right]) {
      return false
    }
    left++
    right--
  }
  return true
}

  2. 反转数组

    function reverse(arr) {
  let left = 0,
    right = str.length - 1
  while (left < right) {
    ;[arr[left], arr[right]] = [arr[right], arr[left]]

    left++
    right--
  }
}

  3. 二分法查找

    function binarySearch(nums, target) {
  let left = 0,
    right = nums.length - 1
  while (left <= right) {
    const mid = Math.floor((right - left) / 2) // 向下取整
    if (nums[mid] === target) {
      return true
    } else if (nums[mid] < target) {
      // 向右切
      left = mid + 1
    } else {
      // 向左切
      right = mid - 1
    }
  }
  return -1
}

快慢指针

快慢指针也就是一快一慢。

数组原地修改

快慢指针用于非严格递增数组原地去重，结果返回数组长度。

function removeDuplicates(nums) {
  // 边界检测
  if (nums.length <= 1) return nums.length

  let slow = 0,
    fast = 0

  while (fast < nums.length) {
    // 检测快慢指针是否相同
    if (nums[slow] !== nums[fast]) {
      // 俩数不同, 慢指针开始移动
      nums[++slow] = nums[fast]
    }

    fast++
  }

  return slow + 1
}

单链表的倒数第 k 个节点

快指针先走 k 步，后快慢指针依次递进最终得到倒数第 K 个节点。

单链表的中点

快指针比慢多走一步，得到链表中点。以此类推三分之一、四分之一。

判断链表是否包含环

快指针比慢指针多走一步，若快慢指针相交则说明闭环。因为快指针相对于慢指针在环里是每次向前走一步的。

寻找环的交点

快指针比慢指针多走一步，等到俩指针相交，此时将其中一指针重置到起点，俩指针依次向前步进（都是每次走一步），最后相交的地方为环的交点。

原理：2(a + b) = a + b + n(b + c) => a = c + (n-1)(b+c)

即 a 的交点为第一次俩指针交点后，再让俩指针依次步进后的下一次交点。

二叉树

二叉树基本上就是迭代和递归的调用，解题思路：是否需要遍历所有子树，如果需要则用 travers 函数递归遍历所有子树，并配合外部变量来实现;

前中后序遍历

const traverse = function (root) {
  if (root === null) {
    return
  }
  // 前序位置
  traverse(root.left)
  // 中序位置
  traverse(root.right)
  // 后序位置
}

层序遍历

如获取二叉树的最大深度：

function maxDepth(root) {
  if (root == null) return 0

  const leftDepth = maxDepth(root.left)
  const rightDepth = maxDepth(root.right)

  return Math.max(leftDepth, rightDepth) + 1
}

层序遍历所有节点:

function levelTraverse(root) {
  if (root == null) return

  const queue = [] // 维护状态数组
  queue.push(root) // 初始化

  while(queue.length > 0) {
    const curLevelNodeSize = queue.length
    for (let ind = 0; ind < curLevelNodeSize, ind++) {
      const curNode = queue.shift() // 取出当前节点

      if (curNode.left) queue.push(curNode.left)
      if (curNode.right) queue.push(curNode.right)
    }
  }
}

递归

递归就是函数调用自身，递归的解题思路是：将问题拆解成规模更小的子问题，直到达到递归终止条件。来看一道简单题: 青蛙跳台阶。

青蛙跳台阶

假设有 n 阶台阶，每次可以跳 1 或 2 个台阶，问有多少种跳法。

function jump(n) {
  if (n === 1) return 1
  if (n === 2) return 2

  return jump(n - 1) + jump(n - 2)
}

但是这里的时间复杂度近似 O(2^n)，因为每次递归都会产生两个分支，所以时间复杂度是指数级的。我们可以利用循环进行优化：

function jump(n) {
  if (n === 1) return 1
  if (n === 2) return 2

  const arr = []
  arr[1] = 1
  arr[2] = 2

  for (let i = 3; i <= n; i++) {
    arr[i] = arr[i - 1] + arr[i - 2]
  }

  return arr[n]
}

动态规划

动态规划的难点在于拆子问题 + 记结果 + 循环递推。解题可以从五步走，后面还会总结一些解题规律。

  1. 确定状态 dp[i][j] 的含义，以二维为例背包问题的状态 dp[i][j] = 前 i 个物品、容量为 j 时的最优值。

  2. 确定状态转移方程，常见模式：

    • 最优子结构: dp[i] = max/min(dp[子问题] + 当前选择)，如 0-1 背包：dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])。一维写法：dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i])。这类题目有：问能否装满背包、最多能装多少、背包装满最大价值。
    • 方案数统计: dp[i] += dp[子问题]，如爬楼梯：dp[i] = dp[i-1] + dp[i-2]。这类题目有：问装满背包有多少种方案、求所有方案。

  3. 确定初始状态，dp 的起点，边界情况要想清楚。通常是：

    • 方案数问题：dp[0] = 1（凑成 0 的方法只有“不选”）
    • 最优值问题：dp[0] = 0（容量为 0 时价值为 0）

  4. 确定遍历顺序和循环内外层。以完全背包为例，算计算出来的是组合数还是排列数。

    • 组合数：先遍历物品，再遍历背包。每个物品只在自己的那一轮扩展一次，顺序不敏感，因此组合数（{1,2} 和 {2,1} 算同一种方案）

      for (let i = 0; i < n; i++) {
  // 遍历物品
  for (let j = w[i]; j <= W; j++) {
    // 遍历容量（从小到大, 起点为 w[i]，因为最小容量不能比起始物品小，否则放不下 ）
    dp[j] += dp[j - w[i]]
  }
}

    • 排列数：先遍历背包，再遍历物品。每个物品可以在任意轮扩展，顺序敏感，因此排列数（{1,2} 和 {2,1} 算不同方案）

      for (let j = 0; j <= W; j++) {
  // 遍历容量（从小到大, 起点为 0）
  for (let i = 0; i < n; i++) {
    // 遍历物品
    if (j >= w[i]) dp[j] += dp[j - w[i]]
  }
}

    • 而循环方向(（j 是否从小到大）)则决定了是完全背包还是 0-1 背包。

      • 小到大(j++) → 可以重复用同一物品 → 完全背包。

      • 大到小(j--) → 只能用一次 → 0-1 背包。

        // 从大到小遍历容量，这样可以保证「同一个物品」在同一轮只会被用一次。
for (let i = 0; i < n; i++) {
  // 遍历物品
  for (let j = W; j >= w[i]; j--) {
    // 容量从大到小
    dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i])
  }
}

拓展多重背包

多重背包: 每个物品有多个，每个物品的数量为 s[i]。实际上这个和 0-1 背包非常像，只需将物品展开即可。

如题目: 有 N 种物品和一个容量为 V 的背包。第 i 种物品最多有 Mi 件可用，每件耗费的空间是 Ci ，价值是 Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

解题时只需在每种商品遍历的个数放在 01 背包里面在遍历一遍，即可。

function multipleBackpack(n, V, w, v, s) {
  const dp = Array.from({ length: V + 1 }, () => 0)
  for (let i = 0; i < n; i++) {
    // 1. 遍历物品
    for (let j = V; j >= w[i]; j--) {
      // 2. 遍历容量（从大到小）
      for (let k = 0; k <= s[i]; k++) {
        // 3. 遍历个数(从 0 到 s[i], 多出这一步)
        if (j >= k * w[i]) {
          dp[j] = Math.max(dp[j], dp[j - k * w[i]] + k * v[i])
        }
      }
    }
  }
  return dp[V]
}

股票买卖问题

股票买卖问题算动态规划的一种，但是比较复杂。一般可以写成下面这样的 dp 状态方程:

// dp[i][j][0] 表示第 i 天【不持有】股票的最大利润
// dp[i][j][1] 表示第 i 天【持有】股票的最大利润

dp[i][j][0] = max(dp[i - 1][j][0], dp[i - 1][j][1] + prices[i]) // 今天不持有 = 昨天不持有 or 今天卖出
dp[i][j][1] = max(dp[i - 1][j][1], dp[i - 1][j - 1][0] - prices[i]) // 今天持有 = 昨天持有 or 今天买入

// 注意, 买入时要消耗一次交易机会，所以买入状态依赖 dp[i-1][j-1][0]。
// 卖出时不增加交易次数，所以卖出状态依赖 dp[i-1][j][1]。

力扣题目 121.open in new window 只能交易一次，交易次数 k = 1，所以只需要 dp[i][1][0] 和 dp[i][1][1]，所以就不需要中间这项。

function maxProfit(prices) {
  const dp = Array.from({ length: prices.length }, () => [0, 0])
  dp[0][0] = -prices[0]
  for (let i = 1; i < prices.length; i++) {
    dp[i][0] = Math.max(dp[i - 1][0], -prices[i])
    dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] + prices[i])
  }
  return dp[prices.length - 1][1]
}

力扣题目 122.open in new window 可以交易多次，交易次数 k = +∞，但由于买了卖、卖了买可以无限重复，所以「交易次数约束」失效了。这时 dp[i][j] 中的 j 已经没意义了，直接简化成：

dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]) // 今天不持有
dp[i][1] = max(dp[i - 1][1], dp[i - 1][0] - prices[i]) // 今天持有

力扣题目 123.open in new window 最多两次交易。此时 j 就起作用了，j = 0 表示不交易，j = 1 表示第一次交易，j = 2 表示第二次交易。

var maxProfit = function (prices) {
  // 两笔交易: 不操作 买入1 卖出1 买入2 卖出2
  const n = prices.length
  const dp = Array.from({ length: prices.length }, () => [0, 0, 0, 0, 0])
  dp[0][1] = -prices[0]
  dp[0][3] = -prices[0]
  for (let i = 1; i < n; i++) {
    dp[i][0] = dp[i - 1][0]
    // 只买一次
    dp[i][1] = Math.max(dp[i - 1][0] - prices[i], dp[i - 1][1])
    // 只卖一次
    dp[i][2] = Math.max(dp[i - 1][1] + prices[i], dp[i - 1][2])
    // 买俩次 卖一次
    dp[i][3] = Math.max(dp[i - 1][2] - prices[i], dp[i - 1][3])
    // 卖俩次
    dp[i][4] = Math.max(dp[i - 1][3] + prices[i], dp[i - 1][4])
  }
  // 返回俩次卖出结果
  return dp[n - 1][4]
}

再往后延伸，力扣题目 188.open in new window 最多 k 次交易。

var maxProfit = function (k, prices) {
  const n = prices.length
  if (n === 0) return 0

  const dp = Array.from({ length: n }, () => new Array(2 * k + 1).fill(0))

  // 初始化买入状态: 奇数 2k-1买入, 偶数2k卖出
  for (let j = 1; j <= k; j++) {
    dp[0][2 * j - 1] = -prices[0]
  }

  for (let i = 1; i < n; i++) {
    for (let j = 1; j <= k; j++) {
      // 买入
      dp[i][2 * j - 1] = Math.max(
        dp[i - 1][2 * j - 1],
        dp[i - 1][2 * j - 2] - prices[i]
      )
      // 卖出
      dp[i][2 * j] = Math.max(
        dp[i - 1][2 * j],
        dp[i - 1][2 * j - 1] + prices[i]
      )
    }
  }

  return dp[n - 1][2 * k]
}

子序列问题

核心思想都是基于「子序列/子数组」的性质来定义状态。状态设计通常是：

  • 单串：dp[i] 表示以第 i 个元素结尾的最优解。
  • 双串：dp[i][j] 表示前 i/j 个字符的子问题结果。

转移方式:

  • 单串题：依赖前面某个位置 j < i 的状态，结合当前元素关系（大小/相等）。
  • 双串题：一般用「是否匹配」来决定取 dp[i-1][j-1] 还是 max(dp[i-1][j], dp[i][j-1])。

边界条件:

  • 单串：通常初始化为 1 或 nums[i]（至少包含自己）。
  • 双串：首行、首列初始化为 0 或特殊值（比如空串匹配）。

  1. 最长上升子序列open in new window: 找一个严格递增的子序列，长度最长是多少。

    var lengthOfLIS = function (nums) {
  // 动态规划 dp [i] = Math.max(dp[i], dp[j] + 1)
  const dp = new Array(nums.length).fill(1)
  for (let i = 0; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[j] < nums[i]) {
        dp[i] = Math.max(dp[i], dp[j] + 1)
      }
    }
  }
  return Math.max(...dp)
}

  2. 最长连续递增子序列open in new window: 区别于上一题，在于连续递增。因此仅需比对前后即可。

    var findLengthOfLCIS = function (nums) {
  // 动规
  const n = nums.length
  if (n === 0) return n

  const dp = Array.from({ length: n }, () => 1)
  for (let i = 1; i < n; i++) {
    if (nums[i] > nums[i - 1]) {
      dp[i] = Math.max(dp[i], dp[i - 1] + 1)
    }
  }
  return Math.max(...dp)
}

  3. 最长重复子数组open in new window，双串字符，需要对比俩字符串前是否相等，相等则 dp[i][j] = dp[i-1][j-1] + 1。

    var findLength = function (nums1, nums2) {
  const dp = Array.from({ length: nums1.length + 1 }, () =>
    new Array(nums2.length + 1).fill(0)
  )
  let res = 0
  for (let i = 1; i <= nums1; i++) {
    for (let j = 1; j <= nums2; j++) {
      if (nums1[i - 1] === nums2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
        res = Math.max(res, dp[i][j])
      }
    }
  }
  return res
}

  4. 最长公共子序列open in new window，双串字符，需要对比俩字符串前是否相等，相等则 dp[i][j] = dp[i-1][j-1] + 1，不相等则保持之前最大子序列 dp[i][j] = max(dp[i-1][j], dp[i][j-1])。

    var longestCommonSubsequence = function (text1, text2) {
  const dp = Array.from({ length: text1.length + 1 }, () =>
    new Array(text2.length + 1).fill(0)
  )
  const rows = text1.length
  const cols = text2.length

  for (let i = 1; i <= rows; i++) {
    for (let j = 1; j <= cols; j++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1] + 1
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])
      }
    }
  }
  return dp[rows][cols]
}

  5. 不同的子序列open in new window, 给你两个字符串 s 和 t ，统计并返回在 s 的 子序列 中 t 出现的个数。这题解题思路在于取值与不取值。

    function numDistinct(s: string, t: string): number {
  /** 
    动规
    dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。
     dp[0][0]=1, 表示s前0个字符为''，t前0个字符为''
     dp[i][0] 表示：以i-1为结尾的s可以随便删除元素，出现空字符串的个数, 个数为1
     dp[0][j] 表示: 空字符串中出现 t 字符串的个数为0
   */
  const dp: number[][] = new Array(s.length + 1)
    .fill(0)
    .map((_) => new Array(t.length + 1).fill(0))
  for (let i: number = 0; i <= s.length; i++) {
    dp[i][0] = 1
  }
  for (let i: number = 1; i <= s.length; i++) {
    for (let j: number = 1; j <= t.length; j++) {
      if (s[i - 1] === t[j - 1]) {
        /** 
         1. 用 t[j-1]: s[i-1] 等于 t[j-1], 所以只需考虑 s[i-2] 和 t[j-2] 的情况 --> dp[i-1][j-1]
         2. 不用t[j-1]: 用 s[i-2] 与 t[j-1] 进行比较. 虽然没有用 t[j-1] 但是 s[i-2] 还是要考虑内部是否存在 t[j-1] 子序列的情况 --> dp[i-1][j]
        */
        dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j]
      } else {
        dp[i][j] = dp[i - 1][j]
      }
    }
  }
  return dp[s.length][t.length]
}

  6. 编辑距离open in new window 给你两个单词 word1 和 word2， 请返回将 word1 转换成 word2 所使用的最少操作数。相对于上一问,就是处理了插入,删除,替换三种操作。会稍微麻烦一点。

回溯

只要出现这些特征，优先考虑回溯：

  1. 列举所有可能解
  2. 组合 / 排列 / 子集 / 分割
  3. 有明确的选择集合
  4. 有约束条件
  5. 解的数量呈指数级

回溯的通用解题思路：

const res = []
let path = []
function backtrack(状态参数) {
  if (终止条件) {
    res.push(当前路径)
    return
  }

  for (选择 in 当前选择列表) {
    if (不合法) continue

    做选择
    backtrack(更新后的状态)
    撤销选择
  }
}
backtrack(初始状态)
return res

求目标和

给定一组不含重复数字的非负数组和一个非负目标数字, 在数组中找出所有数加起来等于给定目标数组的组合。

思路--回溯法：

  1. 通过递归探索每一种可能的组合。
  2. 如果当前的组合满足条件（即和等于目标值），保存该组合。
  3. 如果和超过目标值，提前停止。
  4. 去重：每次递归时，限制数字的选择范围，防止重复组合。
var combinationSum = function (candidates, target) {
  // 选择排列
  const res = []
  const path = []

  function trackBack(start = 0, sum = 0) {
    if (sum > target) return
    if (sum === target) return res.push([...path])

    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i])
      sum += candidates[i]

      trackBack(i, sum)

      sum -= candidates[i]
      path.pop()
    }
  }
  trackBack()
  return res
}

// 示例用法
const nums = [2, 3, 6, 7]
const target = 7
console.log(combinationSum(nums, target))
// 输出: [[2, 2, 3], [7]]

利润最大化

给定一组理财产品列表 products，每个产品包含 { id: string, risk: number, profit: number } 和用户风险承受等级 maxRisk，找出在风险总和不超过 maxRisk 的情况下，利润最大的产品组合（每个产品最多选一次）。

function findBestProducts(products, maxRisk) {
  let maxVal = 0
  let maxPath = []
  let path = []

  function trackBack(ind, risk, sum) {
    // 终止条件
    if (risk > maxRisk) return

    if (sum > maxVal) {
      maxVal = sum
      maxPath = [...path]
    }
    // 产品已选完
    if (ind >= products.length) return

    // 不选
    trackBack(ind + 1, risk, sum)

    // 选
    const { risk: curRisk, profit } = products[ind]
    path.push(profit)
    trackBack(ind + 1, risk + curRisk, sum + profit)
    path.pop()
  }
  trackBack(0, 0, 0)
  return { maxPath, maxVal }
}

const products = [
  { id: 'A', risk: 1, profit: 2 },
  { id: 'B', risk: 2, profit: 5 },
  { id: 'C', risk: 3, profit: 6 },
]

console.log(findBestProducts(products, 4))

应用场景

实现一个版本号的排序

versions 是一个项目的版本号列表，因多人维护，不规则 var versions=['1.5.1','1.45.0','1.5','6','3.3.3.3.3.3.3'] 要求从小到大排序，注意 '1.45' 比 '1.5'大。

function sortVersions(versions = []) {
  return versions.sort((a, b) => {
    const aArr = a.split('.').map(Number)
    const bArr = b.split('.').map(Number)
    const maxLen = Math.max(aArr.length, bArr.length)

    for (let i = 0; i < maxLen; i++) {
      const curA = aArr[i] ?? 0
      const curB = bArr[i] ?? 0
      if (curA !== curB) {
        return curA - curB
      }
    }
    // 相等
    return 0
  })
}

// 测试
const versions = ['1.5.1', '1.45.0', '1.5', '6', '3.3.3.3.3.3.3']
const sorted = sortVersions(versions)
console.log(sorted)

寻找 RTT 最短的 ip 地址

有很多 IP 地址，如何最快找出 RTT 最短的 IP 地址？

假设最大并发数为 5。RTT（Round-Trip Time）：往返时延

function chunks(ips, num) {
  const arr = []
  for (let i = 0; i < ips.length; i = i + num) {
    arr.push(ips.slice(i, i + num))
  }
  return arr
}

function raceChunk(chunk, maxTime) {
  return new Promise((resolve) => {
    const controller = new AbortController()
    const signal = controller.signal

    // 设定超时, 没有比当前时间短的
    const timeout = setTimeout(() => controller.abort(), maxTime)

    // 开始并发请求
    const startTime = new Date()
    const promises = chunk.map((ip) =>
      fetch(ip, { signal }).then(() => ({
        rttTime: new Date() - startTime,
        ip,
      }))
    )

    Promise.race(promises)
      .then((result) => {
        resolve(result)
        // 取消其它请求
        controller.abort()
        clearTimeout(timeout)
      })
      .catch(() => resolve(null)) // 处理所有 fetch 失败的情况
  })
}

async function findShortestRTT(ips, num = 5) {
  // 分组
  const ipChunks = chunks(ips, num)
  let result = {
    rttTime: Infinity,
    ip: '',
  }

  for (const chunk of ipChunks) {
    const temp = await raceChunk(chunk, result.rttTime)
    if (temp) {
      result = temp
    }
  }

  return result.ip
}

数组去重方法汇总

  1. 利用 Set 去重
  2. 利用 for 循环遍历，includes （能识别 NAN）、indexOf（不能识别 NAN）
// 1. set 去重
function unique(arr) {
  // 或者 return Array.from(new Set(arr))
  return [...new Set(arr)]
}

// 2. for 循环遍历
function unique2(arr) {
  if (!Array.isArray(arr)) return
  const resArr = []
  for (const item of arr) {
    if (!resArr.includes(item)) {
      resArr.push(item)
    }
  }
  return resArr
}

// 3. 依据对象 key 对对象数组去重
function unique3(arr, key) {
  const map = new Map()
  return arr.filter((item) => {
    if (!map.has(item[key])) {
      map.set(item[key], true)
      return true
    }
    return false
  })
}

对象相等判断

function deepEqual(obj1, obj2) {
  if (obj1 === obj2) return true
  if (
    typeof obj1 !== 'object' ||
    obj1 === null ||
    typeof obj2 !== 'object' ||
    obj2 === null
  ) {
    return false
  }

  const keys1 = Object.keys(obj1)
  const keys2 = Object.keys(obj2)

  if (keys1.length !== keys2.length) return false

  for (const key of keys1) {
    if (!keys2.includes(key) || !deepEqual(obj1[key], obj2[key])) return false
  }
  return true
}

手写 Array 的 filter、map、some、every 和 reduce 方法

手写 filter

Array.prototype.myFilter = function (callback) {
  const len = this.length
  const res = []
  for (let i = 0; i < len; i++) {
    const item = this[i] // 当前项
    if (callback(item)) {
      res.push(item)
    }
  }
  return res
}

const words = ['spray', 'elite', 'exuberant', 'destruction', 'present']
const result = words.myFilter((word) => word.length > 6)
console.log('🚀 ~ myFilter:', result)

手写 map

Array.prototype.myMap = function (callback) {
  const len = this.length
  const res = []
  for (let i = 0; i < len; i++) {
    const item = this[i]
    res.push(callback(item))
  }
  return res
}

const array = [1, 4, 9, 16]
const map1 = array.myMap((x) => x * 2)
console.log('🚀 ~ myMap:', map1)

手写 some

Array.prototype.mySome = function (callback) {
  const len = this.length
  for (let i = 0; i < len; i++) {
    const item = this[i]
    if (callback(item)) {
      return true
    }
  }
  return false
}

const array = [1, 2, 3, 4, 5]
const even = (element) => element % 2 === 0
console.log('🚀 ~ mySome:', array.mySome(even))

手写 every

Array.prototype.myEvery = function (callback) {
  const len = this.length
  for (let i = 0; i < len; i++) {
    const item = this[i]
    if (!callback(item)) {
      return false
    }
  }
  return true
}

const isBelowThreshold = (currentValue) => currentValue < 40
const array = [1, 30, 39, 29, 10, 13]

console.log('🚀 ~ myEvery:', array.every(isBelowThreshold))

手写 reduce

Array.prototype.myReduce = function (callback, pre) {
  const len = this.length
  let i = 0
  if (pre === undefined) {
    pre = this[i++]
  }
  while (i < len) {
    pre = callback(pre, this[i], i, this)
    i++
  }
  return pre
}

const array = [1, 2, 3, 4]

// 0 + 1 + 2 + 3 + 4
const initialValue = 0
const sumWithInitial = array.reduce(
  (accumulator, currentValue) => accumulator + currentValue,
  initialValue
)
console.log('🚀 ~ myReduce:', sumWithInitial)

实现一个 Promise 的串行执行

const runPromisesInSequence = (array, initialValue) => {
  array.reduce((promiseChain, currentFunction) => {
    return promiseChain.then(currentFunction)
  }, Promise.resolve(initialValue))
}

实现多线程的并发

const runPromisesInSequence = (array, taskNum) => {
  return new Promise((resolve, reject) => {
    const result = new Array(array.length)
    let index = 0 // 执行了多少数量
    let finished = 0 // 完成任务数

    function run() {
      // 所有任务完成
      if (finished === array.length) return resolve(result)
      // 没有任务
      if (index >= array.length) return

      const curIndex = index++
      const task = array[curIndex]
      task()
        .then((res) => {
          result[curIndex] = res
        })
        .catch(reject)
        .finally(() => {
          finished++
          run()
        })
    }
    for (let i = 0; i < taskNum; i++) {
      run()
    }
  })
}

更优雅版本

function runPromises(tasks, limit = 3) {
  const results = []
  let index = 0

  const workers = new Array(limit).fill(null).map(async () => {
    while (index < tasks.length) {
      const curIndex = index++
      results[curIndex] = await tasks[curIndex]()
    }
  })

  return Promise.all(workers).then(() => results)
}

实现一个简单的模板引擎

const tpl = template('<p>hey there {{ name }} {{ name }}</p>')
const res = tpl({ name: 'Neo' })
console.log('🚀 ~ template:', res)

function template(str) {
  return function (obj) {
    for (let key in obj) {
      const val = obj[key]
      const reg = new RegExp(`{{\\s+${key}\\s+}}`, 'g')
      str = str.replace(reg, val)
    }
    return str
  }
}

数组扁平化

// 1. 简单粗暴
arr.flat(Infinity)

// 2. 递归实现
function flatten(arr) {
  const res = []
  for (const item of arr) {
    if (Array.isArray(item)) {
      res.push(...flatten(item))
    } else {
      res.push(item)
    }
  }
  return res
}

// 3. reduce 版本
function flatten2(arr) {
  return arr.reduce((pre, cur) => {
    if (Array.isArray(cur)) {
      return pre.concat(flatten2(cur))
    } else {
      return pre.concat(cur)
    }
  }, [])
}

// 4. 防止栈爆
func flatten3(arr) {
  const stack = [...arr]
  const res = []

  while (stack.length) {
    const item = stack.pop()
    if (Array.isArray(item)) {
      stack.push(...item)
    } else {
      res.push(item)
    }
  }
  return res
}

对象扁平化

/**
 * 对象扁平化
 * 说明：请实现 flatten(input) 函数，input 为一个 javascript 对象（Object 或者 Array），返回值为扁平化后的结果。
 * 示例：
 *   var input = {
 *     a: 1,
 *     b: [ 1, 2, { c: true }, [ 3 ] ],
 *     d: { e: 2, f: 3 },
 *     g: null,
 *   }
 *   var output = flatten(input);
 *   output如下
 *   {
 *     "a": 1,
 *     "b[0]": 1,
 *     "b[1]": 2,
 *     "b[2].c": true,
 *     "b[3][0]": 3,
 *     "d.e": 2,
 *     "d.f": 3,
 *     // "g": null,  值为null或者undefined，丢弃
 *  }
 */
function flatten(obj) {
  const res = {}
  const recur = (target, oldKey) => {
    for (const key in target) {
      let newKey = ''
      if (oldKey) {
        // 区分是否是初次递归
        if (Array.isArray(target)) {
          newKey = `${oldKey}[${key}]`
        } else {
          newKey = `${oldKey}.${key}`
        }
      } else {
        if (Array.isArray(target)) {
          newKey = `[${key}]`
        } else {
          newKey = key
        }
      }

      if (target[key] != null) {
        // 剔除非空结果
        if (typeof target[key] === 'object') {
          recur(target[key], newKey) // 递归扁平值
        } else {
          res[newKey] = target[key] // 添加结果
        }
      }
    }
  }

  recur(obj, '')

  // 返回扁平结果
  return res
}

const inputObj = {
  a: 1,
  b: [1, 2, { c: true }, [3]],
  d: { e: 2, f: 3 },
  g: null,
}
console.log('🚀 ~ flatten:', flatten(inputObj))

根据表达式计算字母数

/**
 * 根据表达式计算字母数
 * 说明：
 *   给定一个描述字母数量的表达式，计算表达式里的每个字母实际数量
 *   表达式格式：
 *     字母紧跟表示次数的数字，如 A2B3
 *     括号可将表达式局部分组后跟上数字，(A2)2B
 *     数字为1时可缺省，如 AB3。
 * 示例：
 *   countOfLetters('A2B3'); // { A: 2, B: 3 }
 *   countOfLetters('A(A3B)2'); // { A: 7, B: 2 }
 *   countOfLetters('C4(A(A3B)2)2'); // { A: 14, B: 4, C: 4 }
 */

function countOfLetters(str) {
  const stack = []
  let curObj = {}
  let i = 0
  while (i < str.length) {
    const s = str[i++]

    if (s === '(') {
      // 入栈
      stack.push(curObj)
      curObj = {}
    } else if (s === ')') {
      // 出栈, 获取后面的数字
      let num = ''
      while (i < str.length && !isNaN(Number(str[i]))) {
        num += str[i++]
      }
      num = Number(num) || 1

      for (const key of Object.keys(curObj)) {
        curObj[key] *= num
      }
      const preObj = stack.pop()
      for (const key of Object.keys(preObj)) {
        curObj[key] = (curObj[key] || 0) + preObj[key]
      }
    } else {
      curObj[s] = (curObj[s] || 0) + 1
      // 探测后续是否为数字
      let num = ''
      while (i < str.length && !isNaN(Number(str[i]))) {
        num += str[i++]
      }
      num = Number(num) || 1
      curObj[s] += num - 1
    }
  }
  return curObj
}

// 测试
console.log(countOfLetters('A2B3')) // { A: 2, B: 3 }
console.log(countOfLetters('A(A3B)2')) // { A: 7, B: 2 }
console.log(countOfLetters('C4(A(A3B)2)2')) // { A: 14, B: 4, C: 4 }

数组转 tree 结构的数据

思路:

  1. 建立查找表：遍历原始数组，创建一个对象（查找表），其中每个节点的 id 是键，节点本身（包括一个空的 children 数组）是值。这一步允许我们快速查找每个节点。

  2. 构建树结构：再次遍历原始数组，根据每个节点的 parentId 将其添加到相应父节点的 children 数组中。如果节点没有 parentId，则将其视为根节点，直接添加到最终的树数组中。

function arrayToTree(array) {
  const tree = []
  const lookup = {}

  // 创建一个查找表，以便快速访问每个节点
  array.forEach((item) => {
    lookup[item.id] = { ...item, children: [] }
  })

  // 构建树结构
  array.forEach((item) => {
    if (item.parentId === null) {
      // 如果没有 parentId，说明是根节点
      tree.push(lookup[item.id])
    } else {
      // 否则，将当前节点添加到其父节点的 children 数组中
      if (lookup[item.parentId]) {
        lookup[item.parentId].children.push(lookup[item.id])
      }
    }
  })

  return tree
}

// 示例数据
const data = [
  { id: 1, parentId: null, name: '根节点1' },
  { id: 2, parentId: 1, name: '子节点1-1' },
  { id: 3, parentId: 1, name: '子节点1-2' },
  { id: 4, parentId: 2, name: '子节点1-1-1' },
  { id: 5, parentId: null, name: '根节点2' },
  { id: 6, parentId: 5, name: '子节点2-1' },
]

const tree = arrayToTree(data)
console.log(JSON.stringify(tree, null, 2))

css 类名压缩

本质是把长 class 名压缩成短字符串，并且保证同一个 class 永远映射成同一个值

  1. 全局缓存设计
  2. Excel 列名的进制算法
  3. 字符串处理能力
function optim(classNames) {
  // 全局缓存
  if (!optim.map) {
    optim._map = new Map()
    optim._index = 0
  }

  function generate() {
    let ind = optim._index++
    let name = ''

    let str = 'abcdefghijklmnopqrstuvwxyz'
    if (ind > 0) str += '0123456789'

    // excel 列名算法
    while (ind >= 0) {
      name += str[ind % str.length]
      ind = Math.floor(ind / str.length) - 1
    }

    return name
  }

  const str = classNames.trim().split(/\s+/)
  const names = str.map((item) => {
    if (!optim._map.has(item)) {
      optim._map.set(item, generate())
    }

    return optim._map.get(item)
  })

  return names.join(' ')
}

console.log(optim('class-a')) // 'a'
console.log(optim('classaa')) // 'b'
console.log(optim('class-a')) // 'a'
console.log(optim('class-a  classaa class-ee')) // 'a b c'

质因数分解

function calc(n) {
  const res = []
  let num = 2
  while (n > 1) {
    while (n % num === 0) {
      res.push(num)
      n /= num
    }
    num++
  }
  return res
}

console.log(calc(2))
// [2]
console.log(calc(8))
// [2, 2, 2]
console.log(calc(24))
// [2, 2, 2, 3]
console.log(calc(30))
// [2, 3, 5]
Loading...
本站原创内容基于 CC BY-SA 4.0 共享, 转载请注明出处。
Copyright © 2026 Huy