Interview -- 算法

Huy大约 8 分钟anonymousnote

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

哈希

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

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. 通过递归探索每一种可能的组合。
  2. 如果当前的组合满足条件（即和等于目标值），保存该组合。
  3. 如果和超过目标值，提前停止。
  4. 去重：每次递归时，限制数字的选择范围，防止重复组合。
function combinationSum(nums, target) {
  const res = []
  nums.sort((a, b) => a - b) // 先排序，方便提前剪枝

  const backtrack = (start, currentCombination, currentSum) => {
    // 找到目标
    if (currentSum === target) {
      res.push([...currentCombination])
      return
    }

    // 回溯
    for (let i = start; i < nums.length; i++) {
      // 提前减枝
      if (currentSum + nums[i] > target) break
      currentCombination.push(nums[i])
      backtrack(i, currentCombination, currentSum + nums[i]) // 递归允许重复选当前数
      currentCombination.pop() // 撤销选择
    }
  }

  backtrack(0, [], 0)
  return res
}

// 示例用法
const nums = [2, 3, 6, 7]
const target = 7
console.log(combinationSum(nums, target))
// 输出: [[2, 2, 3], [7]]
Loading...
本站原创内容基于 CC BY-SA 4.0 共享, 转载请注明出处。
Copyright © 2025 Huy