算法与手写题

面向 5 年经验的前端/全栈工程师，手写题必须秒写，算法题侧重高频中等难度。
每道题均包含：题目 → 考察点 → 完整实现 → 复杂度分析 → 追问延伸
前 10 题为手写题（必须秒写），后 10 题为算法题（LeetCode 高频）

1. 手写 debounce（含 leading / trailing / cancel）

⭐⭐ 进阶 | 考察点：闭包、定时器

完整实现

javascript

function debounce(fn, delay, options = {}) {
  const { leading = false, trailing = true } = options
  let timer = null
  let isInvoked = false

  function debounced(...args) {
    if (timer) clearTimeout(timer)

    if (leading && !isInvoked) {
      fn.apply(this, args)
      isInvoked = true
    }

    timer = setTimeout(() => {
      if (trailing && isInvoked !== !leading) {
        fn.apply(this, args)
      }
      timer = null
      isInvoked = false
    }, delay)
  }

  debounced.cancel = () => {
    clearTimeout(timer)
    timer = null
    isInvoked = false
  }

  return debounced
}

测试用例

javascript

const log = debounce(console.log, 300)
log('a')
log('b')
log('c')
// 300ms 后输出 "c"

const logLeading = debounce(console.log, 300, { leading: true, trailing: false })
logLeading('a') // 立即输出 "a"
logLeading('b') // 忽略
logLeading('c') // 忽略
// 300ms 后冷却，再次调用才触发

复杂度

时间：O(1) 每次调用
空间：O(1) 闭包存储

追问延伸

如何实现 maxWait（类似 Lodash 的 _.debounce，在 delay 期间最多等 maxWait 毫秒）？
requestAnimationFrame 版本的 debounce 适合什么场景？
React 中如何正确使用 debounce？（useRef + useCallback 或 useDebouncedCallback）

2. 手写 throttle（含时间戳 / 定时器 / 组合版）

⭐⭐ 进阶 | 考察点：闭包、时间控制

完整实现

时间戳版（leading 触发）：

javascript

function throttleTimestamp(fn, interval) {
  let lastTime = 0

  return function (...args) {
    const now = Date.now()
    if (now - lastTime >= interval) {
      fn.apply(this, args)
      lastTime = now
    }
  }
}

定时器版（trailing 触发）：

javascript

function throttleTimer(fn, interval) {
  let timer = null

  return function (...args) {
    if (!timer) {
      timer = setTimeout(() => {
        fn.apply(this, args)
        timer = null
      }, interval)
    }
  }
}

组合版（leading + trailing）：

javascript

function throttle(fn, interval, options = {}) {
  const { leading = true, trailing = true } = options
  let lastTime = 0
  let timer = null

  function throttled(...args) {
    const now = Date.now()
    if (!lastTime && !leading) lastTime = now
    const remaining = interval - (now - lastTime)

    if (remaining <= 0 || remaining > interval) {
      if (timer) {
        clearTimeout(timer)
        timer = null
      }
      fn.apply(this, args)
      lastTime = now
    } else if (!timer && trailing) {
      timer = setTimeout(() => {
        lastTime = leading ? Date.now() : 0
        timer = null
        fn.apply(this, args)
      }, remaining)
    }
  }

  throttled.cancel = () => {
    clearTimeout(timer)
    timer = null
    lastTime = 0
  }

  return throttled
}

测试用例

javascript

const onScroll = throttle(() => {
  console.log('scroll', Date.now())
}, 200)

window.addEventListener('scroll', onScroll)

复杂度

时间：O(1) 每次调用
空间：O(1)

追问延伸

leading: false, trailing: false 同时设置会怎样？（函数永远不会执行）
滚动事件用 throttle 还是 requestAnimationFrame？区别是什么？
如何实现一个"在 idle 时执行"的节流？（requestIdleCallback）

3. 手写 deepClone（处理循环引用 / 特殊类型）

⭐⭐⭐ 深入 | 考察点：递归、WeakMap、类型判断

完整实现

javascript

function deepClone(source, cache = new WeakMap()) {
  if (source === null || typeof source !== 'object') return source
  if (cache.has(source)) return cache.get(source)

  if (source instanceof Date) return new Date(source.getTime())
  if (source instanceof RegExp) return new RegExp(source.source, source.flags)
  if (source instanceof Error) return new Error(source.message)

  if (source instanceof Map) {
    const map = new Map()
    cache.set(source, map)
    source.forEach((val, key) => {
      map.set(deepClone(key, cache), deepClone(val, cache))
    })
    return map
  }

  if (source instanceof Set) {
    const set = new Set()
    cache.set(source, set)
    source.forEach(val => set.add(deepClone(val, cache)))
    return set
  }

  const target = Array.isArray(source)
    ? []
    : Object.create(Object.getPrototypeOf(source))

  cache.set(source, target)

  for (const key of Reflect.ownKeys(source)) {
    target[key] = deepClone(source[key], cache)
  }

  return target
}

测试用例

javascript

const obj = {
  num: 42,
  str: 'hello',
  date: new Date(),
  regex: /test/gi,
  nested: { a: { b: 1 } },
  arr: [1, [2, 3]],
  map: new Map([['key', 'value']]),
  set: new Set([1, 2, 3]),
  [Symbol('id')]: 'sym'
}
obj.self = obj

const cloned = deepClone(obj)

console.log(cloned !== obj)                    // true
console.log(cloned.nested !== obj.nested)      // true
console.log(cloned.self === cloned)            // true — 循环引用正确
console.log(cloned.date instanceof Date)       // true
console.log(cloned.map.get('key'))             // "value"

复杂度

时间：O(n)，n 为对象中所有属性的总数
空间：O(n)，WeakMap 缓存 + 递归调用栈

追问延伸

structuredClone() 原生 API 和手写版有什么区别？（不支持函数、DOM 节点、Proxy）
如何用迭代代替递归实现深拷贝（避免栈溢出）？
Reflect.ownKeys() 和 Object.keys() + Object.getOwnPropertySymbols() 的区别？

4. 手写 flat（数组拍平，支持指定深度）

⭐⭐ 进阶 | 考察点：递归、迭代

完整实现

递归版：

javascript

function flat(arr, depth = 1) {
  if (depth <= 0) return arr.slice()

  return arr.reduce((result, item) => {
    if (Array.isArray(item)) {
      result.push(...flat(item, depth - 1))
    } else {
      result.push(item)
    }
    return result
  }, [])
}

迭代版（用栈模拟）：

javascript

function flatIterative(arr, depth = 1) {
  const stack = arr.map(item => [item, depth])
  const result = []

  while (stack.length) {
    const [item, d] = stack.shift()
    if (Array.isArray(item) && d > 0) {
      stack.unshift(...item.map(i => [i, d - 1]))
    } else {
      result.push(item)
    }
  }

  return result
}

完全拍平版（depth = Infinity）：

javascript

function flatDeep(arr) {
  const result = []
  const stack = [...arr]

  while (stack.length) {
    const item = stack.shift()
    if (Array.isArray(item)) {
      stack.unshift(...item)
    } else {
      result.push(item)
    }
  }

  return result
}

测试用例

javascript

console.log(flat([1, [2, [3, [4]]]]))        // [1, 2, [3, [4]]]
console.log(flat([1, [2, [3, [4]]]], 2))     // [1, 2, 3, [4]]
console.log(flat([1, [2, [3, [4]]]], Infinity)) // [1, 2, 3, 4]
console.log(flat([1, , 3]))                   // [1, 3] — 跳过空位（原生行为）

复杂度

时间：O(n)，n 为拍平后的元素总数
空间：O(n)

追问延伸

Array.prototype.flat() 的 polyfill 还需要处理哪些边界情况？（空位、类数组）
用 Generator 实现惰性版 flat？
flatMap 和 flat(1).map() 的区别？性能差异？

5. 手写 curry（柯里化，支持占位符）

⭐⭐ 进阶 | 考察点：递归、闭包、函数式编程

完整实现

基础版：

javascript

function curry(fn) {
  return function curried(...args) {
    if (args.length >= fn.length) {
      return fn.apply(this, args)
    }
    return function (...nextArgs) {
      return curried.apply(this, [...args, ...nextArgs])
    }
  }
}

占位符版：

javascript

curry.placeholder = Symbol('_')

function curryWithPlaceholder(fn) {
  const _ = curry.placeholder

  return function curried(...args) {
    const complete = args.length >= fn.length && !args.slice(0, fn.length).includes(_)

    if (complete) {
      return fn.apply(this, args)
    }

    return function (...nextArgs) {
      const merged = []
      let nextIdx = 0

      for (let i = 0; i < args.length; i++) {
        if (args[i] === _ && nextIdx < nextArgs.length) {
          merged.push(nextArgs[nextIdx++])
        } else {
          merged.push(args[i])
        }
      }

      while (nextIdx < nextArgs.length) {
        merged.push(nextArgs[nextIdx++])
      }

      return curried.apply(this, merged)
    }
  }
}

测试用例

javascript

function add(a, b, c) {
  return a + b + c
}

const curriedAdd = curry(add)
console.log(curriedAdd(1)(2)(3))    // 6
console.log(curriedAdd(1, 2)(3))    // 6
console.log(curriedAdd(1)(2, 3))    // 6
console.log(curriedAdd(1, 2, 3))    // 6

const _ = curry.placeholder
const curriedAdd2 = curryWithPlaceholder(add)
console.log(curriedAdd2(_, 2, 3)(1))   // 6
console.log(curriedAdd2(_, _, 3)(1)(2)) // 6

复杂度

时间：O(n) 每次合并参数，n 为参数个数
空间：O(n) 闭包存储参数

追问延伸

柯里化和偏函数（Partial Application）的区别？
Lodash 的 _.curry 和 _.partial 有什么不同？
函数式编程中柯里化的实际应用场景？（compose、中间件、配置工厂）

6. 手写 EventEmitter（含 on / off / emit / once）

⭐⭐ 进阶 | 考察点：发布订阅模式

完整实现

javascript

class EventEmitter {
  constructor() {
    this.events = new Map()
  }

  on(event, listener) {
    if (!this.events.has(event)) {
      this.events.set(event, [])
    }
    this.events.get(event).push(listener)
    return this
  }

  off(event, listener) {
    const listeners = this.events.get(event)
    if (!listeners) return this
    const idx = listeners.indexOf(listener)
    if (idx !== -1) listeners.splice(idx, 1)
    if (listeners.length === 0) this.events.delete(event)
    return this
  }

  once(event, listener) {
    const wrapper = (...args) => {
      listener.apply(this, args)
      this.off(event, wrapper)
    }
    wrapper._original = listener
    this.on(event, wrapper)
    return this
  }

  emit(event, ...args) {
    const listeners = this.events.get(event)
    if (!listeners) return false
    listeners.slice().forEach(fn => fn.apply(this, args))
    return true
  }

  listenerCount(event) {
    return this.events.get(event)?.length || 0
  }

  removeAllListeners(event) {
    if (event) {
      this.events.delete(event)
    } else {
      this.events.clear()
    }
    return this
  }
}

测试用例

javascript

const emitter = new EventEmitter()

const handler = (msg) => console.log('received:', msg)
emitter.on('message', handler)
emitter.emit('message', 'hello')  // received: hello

emitter.once('login', (user) => console.log('Welcome', user))
emitter.emit('login', 'Alice')    // Welcome Alice
emitter.emit('login', 'Bob')      // 无输出（once 只触发一次）

emitter.off('message', handler)
emitter.emit('message', 'world')  // 无输出

console.log(emitter.listenerCount('message')) // 0

关键细节

emit 中用 listeners.slice() 遍历副本，防止 once 的 off 在遍历中修改数组
once 的 wrapper 保存 _original 引用，方便 off 时用原始 listener 移除
链式调用：on/off/once/removeAllListeners 都返回 this

追问延伸

Node.js 的 EventEmitter 还有哪些功能？（prependListener、maxListeners、error 事件）
如何实现一个类型安全的 EventEmitter（TypeScript 泛型版）？
EventEmitter 在什么场景下会导致内存泄漏？如何排查？

7. 手写 Promise.all / Promise.race

⭐⭐ 进阶 | 考察点：Promise 静态方法

完整实现

Promise.all：

javascript

function promiseAll(promises) {
  return new Promise((resolve, reject) => {
    const items = Array.from(promises)
    if (items.length === 0) return resolve([])

    const results = new Array(items.length)
    let completed = 0

    items.forEach((item, index) => {
      Promise.resolve(item).then(
        (value) => {
          results[index] = value
          if (++completed === items.length) resolve(results)
        },
        reject
      )
    })
  })
}

Promise.race：

javascript

function promiseRace(promises) {
  return new Promise((resolve, reject) => {
    const items = Array.from(promises)
    if (items.length === 0) return

    items.forEach((item) => {
      Promise.resolve(item).then(resolve, reject)
    })
  })
}

附赠 Promise.allSettled：

javascript

function promiseAllSettled(promises) {
  return new Promise((resolve) => {
    const items = Array.from(promises)
    if (items.length === 0) return resolve([])

    const results = new Array(items.length)
    let completed = 0

    items.forEach((item, index) => {
      Promise.resolve(item).then(
        (value) => {
          results[index] = { status: 'fulfilled', value }
          if (++completed === items.length) resolve(results)
        },
        (reason) => {
          results[index] = { status: 'rejected', reason }
          if (++completed === items.length) resolve(results)
        }
      )
    })
  })
}

测试用例

javascript

promiseAll([
  Promise.resolve(1),
  new Promise(r => setTimeout(() => r(2), 100)),
  42
]).then(console.log)  // [1, 2, 42]

promiseAll([
  Promise.resolve(1),
  Promise.reject('fail')
]).catch(console.log) // "fail"

promiseRace([
  new Promise(r => setTimeout(() => r('slow'), 200)),
  new Promise(r => setTimeout(() => r('fast'), 50))
]).then(console.log)  // "fast"

promiseAllSettled([
  Promise.resolve(1),
  Promise.reject('err')
]).then(console.log)
// [{ status: 'fulfilled', value: 1 }, { status: 'rejected', reason: 'err' }]

追问延伸

Promise.race([]) 返回什么？（永远 pending 的 Promise）
如何实现带超时的 Promise？（Promise.race([fetchPromise, timeoutPromise])）
Promise.any 和 Promise.race 的区别？手写 Promise.any？

8. 手写 async/await 自动执行器

⭐⭐⭐ 深入 | 考察点：Generator、Promise

完整实现

javascript

function asyncToGenerator(generatorFn) {
  return function (...args) {
    const gen = generatorFn.apply(this, args)

    return new Promise((resolve, reject) => {
      function step(key, value) {
        let result
        try {
          result = gen[key](value)
        } catch (err) {
          return reject(err)
        }

        const { value: nextValue, done } = result

        if (done) {
          resolve(nextValue)
        } else {
          Promise.resolve(nextValue).then(
            val => step('next', val),
            err => step('throw', err)
          )
        }
      }

      step('next', undefined)
    })
  }
}

测试用例

javascript

function delay(ms, value) {
  return new Promise(r => setTimeout(() => r(value), ms))
}

const fetchData = asyncToGenerator(function* () {
  const a = yield delay(100, 'hello')
  const b = yield delay(100, 'world')
  return `${a} ${b}`
})

fetchData().then(console.log) // "hello world"

const withError = asyncToGenerator(function* () {
  try {
    yield Promise.reject(new Error('oops'))
  } catch (e) {
    return `caught: ${e.message}`
  }
})

withError().then(console.log) // "caught: oops"

原理分析

async/await 是 Generator 的语法糖：

async function → Generator 函数 + 自动执行器
await expr → yield expr
自动执行器负责在每次 yield 后，等 Promise resolve，再调用 gen.next(value) 继续

追问延伸

co 库的实现原理？它和这个自动执行器有什么区别？
Generator 除了模拟 async/await，还有什么实际用途？（惰性序列、状态机、Redux-Saga）
for await...of 的底层原理？异步迭代器协议？

9. 手写 LazyMan（链式调用 + sleep）

⭐⭐⭐ 深入 | 考察点：任务队列、链式调用、宏/微任务

完整实现

javascript

class _LazyMan {
  constructor(name) {
    this.tasks = []
    this.tasks.push(() => {
      console.log(`Hi! This is ${name}!`)
      this.next()
    })
    setTimeout(() => this.next(), 0)
  }

  next() {
    const task = this.tasks.shift()
    task && task()
  }

  sleep(seconds) {
    this.tasks.push(() => {
      setTimeout(() => {
        console.log(`Wake up after ${seconds}s`)
        this.next()
      }, seconds * 1000)
    })
    return this
  }

  sleepFirst(seconds) {
    this.tasks.unshift(() => {
      setTimeout(() => {
        console.log(`Wake up after ${seconds}s`)
        this.next()
      }, seconds * 1000)
    })
    return this
  }

  eat(food) {
    this.tasks.push(() => {
      console.log(`Eat ${food}`)
      this.next()
    })
    return this
  }
}

function LazyMan(name) {
  return new _LazyMan(name)
}

测试用例

javascript

LazyMan('Jack')
// Hi! This is Jack!

LazyMan('Jack').eat('lunch')
// Hi! This is Jack!
// Eat lunch

LazyMan('Jack').sleep(2).eat('dinner')
// Hi! This is Jack!
// (等2秒)
// Wake up after 2s
// Eat dinner

LazyMan('Jack').eat('lunch').sleepFirst(3).eat('dinner')
// (等3秒)
// Wake up after 3s
// Hi! This is Jack!
// Eat lunch
// Eat dinner

核心设计

任务队列：所有操作（sayHi/eat/sleep）都推入队列，不立即执行
延迟启动：setTimeout(() => this.next(), 0) 利用事件循环，等链式调用全部注册完再开始执行
sleepFirst：用 unshift 插入队列头部，实现优先执行
next：每个任务执行完主动调用 next()，串联异步任务

追问延伸

如何把 LazyMan 改写成 async/await 版本？
如果要支持 cancel() 取消后续所有任务，怎么实现？
这种"任务队列 + 延迟启动"的设计模式还在哪些地方使用？（Webpack tapable、Koa 中间件）

10. 手写并发请求控制器（最大并发数限制）

⭐⭐⭐ 深入 | 考察点：Promise、并发控制

完整实现

javascript

function concurrentLimit(tasks, limit) {
  return new Promise((resolve, reject) => {
    const results = new Array(tasks.length)
    let completed = 0
    let currentIndex = 0
    let hasRejected = false

    function runNext() {
      if (hasRejected) return
      if (currentIndex >= tasks.length) return
      
      const index = currentIndex++
      const task = tasks[index]

      Promise.resolve(task()).then(
        (value) => {
          results[index] = value
          completed++
          if (completed === tasks.length) {
            resolve(results)
          } else {
            runNext()
          }
        },
        (reason) => {
          hasRejected = true
          reject(reason)
        }
      )
    }

    const initialCount = Math.min(limit, tasks.length)
    for (let i = 0; i < initialCount; i++) {
      runNext()
    }

    if (tasks.length === 0) resolve([])
  })
}

类版本（更灵活，支持动态添加任务）：

javascript

class ConcurrencyPool {
  constructor(limit) {
    this.limit = limit
    this.running = 0
    this.queue = []
  }

  async add(task) {
    if (this.running >= this.limit) {
      await new Promise(resolve => this.queue.push(resolve))
    }

    this.running++
    try {
      return await task()
    } finally {
      this.running--
      if (this.queue.length > 0) {
        this.queue.shift()()
      }
    }
  }
}

测试用例

javascript

function createTask(id, delay) {
  return () => new Promise(resolve => {
    console.log(`Task ${id} started`)
    setTimeout(() => {
      console.log(`Task ${id} done`)
      resolve(id)
    }, delay)
  })
}

const tasks = [
  createTask(1, 1000),
  createTask(2, 500),
  createTask(3, 800),
  createTask(4, 300),
  createTask(5, 600)
]

concurrentLimit(tasks, 2).then(console.log)
// Task 1 started
// Task 2 started
// (500ms) Task 2 done → Task 3 started
// (800ms) Task 3 done → Task 4 started  (注：1也在这之前完成)
// ... 最终输出 [1, 2, 3, 4, 5]

const pool = new ConcurrencyPool(3)
const urls = ['/api/1', '/api/2', '/api/3', '/api/4', '/api/5']

const results = await Promise.all(
  urls.map(url => pool.add(() => fetch(url).then(r => r.json())))
)

核心设计

方案	函数版 `concurrentLimit`	类版 `ConcurrencyPool`
一次性	✅ 固定任务数组	❌ 支持动态添加
复用	❌	✅ 实例可反复使用
原理	池子初始填满 limit 个，每完成一个拉一个	`await` 等待空位，`finally` 中释放并通知下一个

追问延伸

如何实现"任一失败不影响其他"的版本？（类似 allSettled 语义）
p-limit（npm 包）的实现原理？和上面的有什么不同？
浏览器的 HTTP 并发限制（同域 6 个）和这个并发控制有什么关系？

二、LeetCode 高频算法

11. 两数之和 ⭐

给定整数数组 nums 和目标值 target，找出和为目标值的两个整数的下标。

考察点：哈希表、时间/空间复杂度权衡

typescript

function twoSum(nums: number[], target: number): number[] {
  const map = new Map<number, number>()

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i]
    if (map.has(complement)) {
      return [map.get(complement)!, i]
    }
    map.set(nums[i], i)
  }

  throw new Error('No solution')
}

解题思路

方法	时间复杂度	空间复杂度	思路
暴力双循环	O(n²)	O(1)	两两配对，逐一检查
哈希表（一次遍历）	O(n)	O(n)	边存边查，用 `target - nums[i]` 查表

关键点：哈希表方案之所以只需一次遍历，是因为当遍历到 nums[i] 时，它的"搭档"如果在它前面，早已存入 Map。

追问延伸

如果数组已排序，能否用 O(1) 空间？（双指针对撞）
三数之和（LeetCode 15）怎么做？和两数之和有什么关系？
如果允许返回所有满足条件的下标对呢？

12. 有效的括号 ⭐

给定只包含 '('、')'、'{'、'}'、'['、']' 的字符串，判断是否有效。

考察点：栈、字符匹配

typescript

function isValid(s: string): boolean {
  const stack: string[] = []
  const pairs: Record<string, string> = {
    ')': '(',
    ']': '[',
    '}': '{'
  }

  for (const ch of s) {
    if (ch in pairs) {
      if (stack.pop() !== pairs[ch]) return false
    } else {
      stack.push(ch)
    }
  }

  return stack.length === 0
}

解题思路

遇到左括号 → 压栈
遇到右括号 → 弹栈，检查是否匹配
最终栈为空 → 有效

边界情况	结果	原因
`""`	`true`	空字符串合法
`"("`	`false`	栈不为空
`")(`	`false`	弹栈时栈空，`undefined !== '('`
`"([)]"`	`false`	交叉不匹配
`"{[]}"`	`true`	嵌套匹配

追问延伸

如果字符串中混杂了其他字符（如 "a(b)c"），如何处理？
最长有效括号子串（LeetCode 32）怎么做？
能否不用栈、用计数器解决？（仅限单一括号类型）

13. 反转链表 ⭐

反转单链表，返回新的头节点。

考察点：链表指针操作、迭代 vs 递归

typescript

class ListNode {
  val: number
  next: ListNode | null
  constructor(val = 0, next: ListNode | null = null) {
    this.val = val
    this.next = next
  }
}

// 迭代法
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null
  let curr = head

  while (curr) {
    const next = curr.next
    curr.next = prev
    prev = curr
    curr = next
  }

  return prev
}

// 递归法
function reverseListRecursive(head: ListNode | null): ListNode | null {
  if (!head || !head.next) return head

  const newHead = reverseListRecursive(head.next)
  head.next.next = head
  head.next = null

  return newHead
}

核心图解

迭代过程（prev / curr / next 三指针）：

初始:  null   1 → 2 → 3 → null
       prev  curr

第1步: null ← 1   2 → 3 → null
             prev curr

第2步: null ← 1 ← 2   3 → null
                  prev curr

第3步: null ← 1 ← 2 ← 3
                       prev  curr=null → 结束

递归过程（回溯时翻转指针）：

递归到底:  reverseList(3) → 返回 3

回溯:     head=2, head.next=3
          3.next = 2     → 3 → 2
          2.next = null   → 3 → 2 → null

回溯:     head=1, head.next=2
          2.next = 1     → 3 → 2 → 1
          1.next = null   → 3 → 2 → 1 → null

方法	时间	空间	特点
迭代	O(n)	O(1)	三个指针滑动
递归	O(n)	O(n)	调用栈开销，代码更简洁

追问延伸

反转链表的第 m 到 n 个节点（LeetCode 92）？
K 个一组翻转链表（LeetCode 25）？
如何判断链表是否有环？（快慢指针）

14. 二叉树的层序遍历 ⭐⭐

给定二叉树，返回其节点值的层序遍历结果（逐层从左到右）。

考察点：BFS、队列

typescript

class TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
  constructor(val = 0, left: TreeNode | null = null, right: TreeNode | null = null) {
    this.val = val
    this.left = left
    this.right = right
  }
}

function levelOrder(root: TreeNode | null): number[][] {
  if (!root) return []

  const result: number[][] = []
  const queue: TreeNode[] = [root]

  while (queue.length > 0) {
    const levelSize = queue.length
    const currentLevel: number[] = []

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift()!
      currentLevel.push(node.val)

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

    result.push(currentLevel)
  }

  return result
}

核心要点

        3
       / \
      9  20
         / \
        15   7

队列状态变化:
[3]            → 取出 3, 放入 9、20    → 第1层: [3]
[9, 20]        → 取出 9(无子)、20(放15,7) → 第2层: [9, 20]
[15, 7]        → 取出 15、7            → 第3层: [15, 7]

输出: [[3], [9, 20], [15, 7]]

关键技巧：每轮循环开始时记录 queue.length 作为当前层的节点数量（levelSize），这样即使在循环中 push 了下层节点，也不会混淆层级。

追问延伸

锯齿形层序遍历（LeetCode 103）？（奇偶层交替方向）
二叉树最大深度用 BFS 怎么做？用 DFS 呢？
queue.shift() 的时间复杂度是 O(n)，如何优化？（用指针替代 shift）

15. 最大子数组和 ⭐⭐

给定整数数组，找到具有最大和的连续子数组，返回其最大和。

考察点：动态规划、Kadane 算法

typescript

// Kadane 算法
function maxSubArray(nums: number[]): number {
  let maxSum = nums[0]
  let currentSum = nums[0]

  for (let i = 1; i < nums.length; i++) {
    currentSum = Math.max(nums[i], currentSum + nums[i])
    maxSum = Math.max(maxSum, currentSum)
  }

  return maxSum
}

// DP 显式写法（含路径还原）
function maxSubArrayWithPath(nums: number[]): {
  maxSum: number
  subArray: number[]
} {
  const n = nums.length
  const dp = new Array(n)
  dp[0] = nums[0]

  let maxSum = dp[0]
  let endIndex = 0

  for (let i = 1; i < n; i++) {
    dp[i] = Math.max(nums[i], dp[i - 1] + nums[i])
    if (dp[i] > maxSum) {
      maxSum = dp[i]
      endIndex = i
    }
  }

  const subArray: number[] = []
  let sum = maxSum
  for (let i = endIndex; i >= 0; i--) {
    subArray.unshift(nums[i])
    sum -= nums[i]
    if (sum === 0) break
  }

  return { maxSum, subArray }
}

核心思想

nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]

i:          0   1   2   3   4   5   6   7   8
nums[i]:   -2   1  -3   4  -1   2   1  -5   4
current:   -2   1  -2   4   3   5   6   1   5
maxSum:    -2   1   1   4   4   5   6   6   6

决策: currentSum = max(nums[i], currentSum + nums[i])
含义: 要么"从我重新开始"，要么"接着前面的累加"
→ 最大子数组: [4, -1, 2, 1]，和为 6

状态定义	`dp[i]` = 以 `nums[i]` 结尾的最大子数组和
转移方程	`dp[i] = max(nums[i], dp[i-1] + nums[i])`
空间优化	只依赖前一个状态，用变量替代数组 → O(1)

追问延伸

如果要求返回子数组本身（不只是和），怎么做？（上面已给出）
分治法解这道题？（O(n log n)，理解递归思维）
最大子矩阵和（二维版）怎么做？

16. LRU 缓存 ⭐⭐⭐

设计和实现一个 LRU（最近最少使用）缓存机制，支持 get 和 put 操作，均为 O(1) 时间复杂度。

考察点：Map 有序性、双向链表、数据结构设计

typescript

// 方案一：利用 Map 的插入顺序特性（ES6+）
class LRUCache {
  private capacity: number
  private cache: Map<number, number>

  constructor(capacity: number) {
    this.capacity = capacity
    this.cache = new Map()
  }

  get(key: number): number {
    if (!this.cache.has(key)) return -1

    const value = this.cache.get(key)!
    this.cache.delete(key)
    this.cache.set(key, value)
    return value
  }

  put(key: number, value: number): void {
    if (this.cache.has(key)) {
      this.cache.delete(key)
    } else if (this.cache.size >= this.capacity) {
      const oldestKey = this.cache.keys().next().value!
      this.cache.delete(oldestKey)
    }
    this.cache.set(key, value)
  }
}

typescript

// 方案二：手写双向链表 + HashMap（经典实现）
class DLinkedNode {
  key: number
  value: number
  prev: DLinkedNode | null = null
  next: DLinkedNode | null = null

  constructor(key = 0, value = 0) {
    this.key = key
    this.value = value
  }
}

class LRUCacheLinkedList {
  private capacity: number
  private size: number
  private cache: Map<number, DLinkedNode>
  private head: DLinkedNode
  private tail: DLinkedNode

  constructor(capacity: number) {
    this.capacity = capacity
    this.size = 0
    this.cache = new Map()

    this.head = new DLinkedNode()
    this.tail = new DLinkedNode()
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  get(key: number): number {
    const node = this.cache.get(key)
    if (!node) return -1

    this.moveToHead(node)
    return node.value
  }

  put(key: number, value: number): void {
    const node = this.cache.get(key)

    if (node) {
      node.value = value
      this.moveToHead(node)
    } else {
      const newNode = new DLinkedNode(key, value)
      this.cache.set(key, newNode)
      this.addToHead(newNode)
      this.size++

      if (this.size > this.capacity) {
        const removed = this.removeTail()
        this.cache.delete(removed.key)
        this.size--
      }
    }
  }

  private addToHead(node: DLinkedNode): void {
    node.prev = this.head
    node.next = this.head.next
    this.head.next!.prev = node
    this.head.next = node
  }

  private removeNode(node: DLinkedNode): void {
    node.prev!.next = node.next
    node.next!.prev = node.prev
  }

  private moveToHead(node: DLinkedNode): void {
    this.removeNode(node)
    this.addToHead(node)
  }

  private removeTail(): DLinkedNode {
    const node = this.tail.prev!
    this.removeNode(node)
    return node
  }
}

两种方案对比

维度	Map 方案	双向链表 + HashMap
实现难度	⭐ 简单	⭐⭐⭐ 复杂
`get` / `put`	O(1)（依赖 Map 实现）	严格 O(1)
面试场景	快速实现，说明 Map 顺序特性	展示数据结构功底
关键点	`delete` → `set` 实现"移到末尾"	哨兵节点避免空指针判断

双向链表结构 (Head 为最新, Tail 为最旧):

  head ⟷ [最新] ⟷ [次新] ⟷ ... ⟷ [最旧] ⟷ tail
  (dummy)                              (dummy)

get(key):  找到节点 → 移到 head 后面
put(key):  已有 → 更新+移到 head; 新增 → 插入 head 后, 满了 → 删 tail 前

追问延伸

LFU 缓存（最不经常使用）和 LRU 有什么区别？怎么实现？
为什么用双向链表而不是单向链表？（删除操作需要 O(1) 访问前驱）
浏览器的 HTTP 缓存、Vue 的 keep-alive 都和 LRU 有关？

17. 合并两个有序数组 ⭐

给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中（nums1 有足够空间）。

考察点：双指针、从后往前填充

typescript

function merge(
  nums1: number[], m: number,
  nums2: number[], n: number
): void {
  let p1 = m - 1
  let p2 = n - 1
  let p = m + n - 1

  while (p2 >= 0) {
    if (p1 >= 0 && nums1[p1] > nums2[p2]) {
      nums1[p] = nums1[p1]
      p1--
    } else {
      nums1[p] = nums2[p2]
      p2--
    }
    p--
  }
}

核心思想

为什么从后往前填充？

nums1 = [1, 2, 3, 0, 0, 0], m = 3
nums2 = [2, 5, 6],           n = 3

如果从前往前：填入位置会覆盖 nums1 中还未处理的元素
从后往前：填入末尾的空位，不会覆盖任何有效元素

步骤:
p1=2, p2=2, p=5:  nums1[2]=3 < nums2[2]=6 → nums1[5]=6, p2--
p1=2, p2=1, p=4:  nums1[2]=3 < nums2[1]=5 → nums1[4]=5, p2--
p1=2, p2=0, p=3:  nums1[2]=3 > nums2[0]=2 → nums1[3]=3, p1--
p1=1, p2=0, p=2:  nums1[1]=2 = nums2[0]=2 → nums1[2]=2, p2--
p2 < 0 → 结束

结果: [1, 2, 2, 3, 5, 6] ✅

要点	说明
循环条件	`p2 >= 0`（nums2 处理完即可，nums1 剩余的已在正确位置）
比较逻辑	`p1 >= 0 && nums1[p1] > nums2[p2]` 先检查越界
时间/空间	O(m+n) / O(1) 原地操作

追问延伸

合并 K 个有序数组怎么做？（归并 / 最小堆）
合并两个有序链表（LeetCode 21）？
如果 nums1 没有额外空间怎么办？（需要辅助数组）

18. 爬楼梯 ⭐

每次可以爬 1 或 2 个台阶，爬到第 n 阶有多少种方法？

考察点：动态规划入门、斐波那契数列

typescript

// 空间优化版
function climbStairs(n: number): number {
  if (n <= 2) return n

  let prev1 = 1
  let prev2 = 2

  for (let i = 3; i <= n; i++) {
    const curr = prev1 + prev2
    prev1 = prev2
    prev2 = curr
  }

  return prev2
}

// 完整 DP 版（便于理解）
function climbStairsDP(n: number): number {
  if (n <= 2) return n

  const dp = new Array(n + 1)
  dp[1] = 1
  dp[2] = 2

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

  return dp[n]
}

DP 分析

到达第 i 阶的方式 = 从第 i-1 阶跨 1 步 + 从第 i-2 阶跨 2 步

dp[1] = 1         (1)
dp[2] = 2         (1+1, 2)
dp[3] = 3         (1+1+1, 1+2, 2+1)
dp[4] = 5         (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)
dp[5] = 8
...

本质就是斐波那契数列！

维度	完整 DP	空间优化
时间	O(n)	O(n)
空间	O(n)	O(1)
适用	需要所有中间状态	只需最终结果

追问延伸

如果每次可以爬 1、2、3 个台阶呢？（dp[i] = dp[i-1] + dp[i-2] + dp[i-3]）
如果某些台阶不能踩（代价数组），怎么改？（最小代价爬楼梯 LeetCode 746）
能否用矩阵快速幂优化到 O(log n)？

19. 全排列 ⭐⭐

给定一个不含重复数字的数组，返回其所有可能的全排列。

考察点：回溯算法、递归树

typescript

function permute(nums: number[]): number[][] {
  const result: number[][] = []

  function backtrack(path: number[], used: boolean[]) {
    if (path.length === nums.length) {
      result.push([...path])
      return
    }

    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue

      path.push(nums[i])
      used[i] = true

      backtrack(path, used)

      path.pop()
      used[i] = false
    }
  }

  backtrack([], new Array(nums.length).fill(false))
  return result
}

// 交换法（不需要额外 used 数组）
function permuteSwap(nums: number[]): number[][] {
  const result: number[][] = []

  function backtrack(start: number) {
    if (start === nums.length) {
      result.push([...nums])
      return
    }

    for (let i = start; i < nums.length; i++) {
      [nums[start], nums[i]] = [nums[i], nums[start]]
      backtrack(start + 1)
      ;[nums[start], nums[i]] = [nums[i], nums[start]]
    }
  }

  backtrack(0)
  return result
}

回溯递归树

nums = [1, 2, 3]

                        []
           /             |            \
         [1]            [2]           [3]
        /   \          /   \         /   \
     [1,2] [1,3]   [2,1] [2,3]   [3,1] [3,2]
       |     |       |     |       |     |
   [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]

回溯的核心: "选择 → 递归 → 撤销选择"

回溯模板

typescript

function backtracking(选择列表, 路径, 结果集) {
  if (满足结束条件) {
    结果集.push(路径的拷贝)
    return
  }

  for (const 选择 of 选择列表) {
    // 剪枝（可选）
    做选择(path.push, used[i] = true)
    backtracking(选择列表, 路径, 结果集)
    撤销选择(path.pop, used[i] = false)
  }
}

问题	变化点
全排列 II（有重复数字）	先排序，`i > 0 && nums[i] === nums[i-1] && !used[i-1]` 跳过
子集	不需要终止条件长度限制，每个节点都收集结果
组合总和	`start` 控制不重复选择，加和判断剪枝
N 皇后	列、主对角线、副对角线三个集合判断冲突

追问延伸

全排列 II（LeetCode 47）含重复数字如何去重？
回溯和 DFS 的区别是什么？（回溯强调"撤销选择"）
时间复杂度 O(n! × n) 中的 × n 是哪来的？（每次拷贝 path）

20. 接雨水 ⭐⭐⭐

给定 n 个非负整数表示宽度为 1 的柱子高度图，计算雨后能接多少水。

考察点：双指针、单调栈、动态规划

typescript

// 方案一：双指针（最优）
function trap(height: number[]): number {
  let left = 0
  let right = height.length - 1
  let leftMax = 0
  let rightMax = 0
  let water = 0

  while (left < right) {
    if (height[left] < height[right]) {
      if (height[left] >= leftMax) {
        leftMax = height[left]
      } else {
        water += leftMax - height[left]
      }
      left++
    } else {
      if (height[right] >= rightMax) {
        rightMax = height[right]
      } else {
        water += rightMax - height[right]
      }
      right--
    }
  }

  return water
}

// 方案二：单调递减栈（横向计算）
function trapStack(height: number[]): number {
  const stack: number[] = []
  let water = 0

  for (let i = 0; i < height.length; i++) {
    while (stack.length > 0 && height[i] > height[stack[stack.length - 1]]) {
      const bottom = stack.pop()!

      if (stack.length === 0) break

      const left = stack[stack.length - 1]
      const width = i - left - 1
      const h = Math.min(height[left], height[i]) - height[bottom]
      water += width * h
    }
    stack.push(i)
  }

  return water
}

// 方案三：预处理（DP 思想）
function trapDP(height: number[]): number {
  const n = height.length
  if (n === 0) return 0

  const leftMax = new Array(n)
  const rightMax = new Array(n)

  leftMax[0] = height[0]
  for (let i = 1; i < n; i++) {
    leftMax[i] = Math.max(leftMax[i - 1], height[i])
  }

  rightMax[n - 1] = height[n - 1]
  for (let i = n - 2; i >= 0; i--) {
    rightMax[i] = Math.max(rightMax[i + 1], height[i])
  }

  let water = 0
  for (let i = 0; i < n; i++) {
    water += Math.min(leftMax[i], rightMax[i]) - height[i]
  }

  return water
}

核心原理

height = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]

每个位置能接的水 = min(左边最高, 右边最高) - 当前高度

图示 (# = 柱子, ~ = 水):

         #
 #~~~~~~~#~#
 #~#~~#~##~#
_#~#~##~##~#_
 0 1 0 2 1 0 1 3 2 1 2 1

位置2: min(1, 3) - 0 = 1
位置4: min(2, 3) - 1 = 1
位置5: min(2, 3) - 0 = 2
...
总水量 = 6

三种方案对比

方案	时间	空间	思路
预处理 DP	O(n)	O(n)	两遍扫描预处理 leftMax / rightMax
双指针	O(n)	O(1)	矮的那边决定水位，向内收缩
单调栈	O(n)	O(n)	横向一层层算，遇到更高的就结算"凹槽"

双指针核心逻辑：

为什么 height[left] < height[right] 时处理左边？

因为右边一定存在 ≥ height[right] 的墙（right 自身或更右边）
所以左边的水位由 leftMax 决定，不需要知道右边的精确最大值。
反之亦然。

追问延伸

盛最多水的容器（LeetCode 11）和接雨水有什么区别？
二维接雨水（LeetCode 407）怎么做？（最小堆 BFS）
单调栈解法中，为什么维护递减栈而不是递增栈？

算法与手写题 ​

1. 手写 debounce（含 leading / trailing / cancel） ​

完整实现 ​

测试用例 ​

复杂度 ​

2. 手写 throttle（含时间戳 / 定时器 / 组合版） ​

完整实现 ​

测试用例 ​

复杂度 ​

3. 手写 deepClone（处理循环引用 / 特殊类型） ​

完整实现 ​

测试用例 ​

复杂度 ​

4. 手写 flat（数组拍平，支持指定深度） ​

完整实现 ​

测试用例 ​

复杂度 ​

5. 手写 curry（柯里化，支持占位符） ​

完整实现 ​

测试用例 ​

复杂度 ​

6. 手写 EventEmitter（含 on / off / emit / once） ​

完整实现 ​

测试用例 ​

关键细节 ​

7. 手写 Promise.all / Promise.race ​

完整实现 ​

测试用例 ​

8. 手写 async/await 自动执行器 ​

完整实现 ​

测试用例 ​

原理分析 ​

9. 手写 LazyMan（链式调用 + sleep） ​

完整实现 ​

测试用例 ​

核心设计 ​

10. 手写并发请求控制器（最大并发数限制） ​

完整实现 ​

测试用例 ​

核心设计 ​

二、LeetCode 高频算法 ​

11. 两数之和 ⭐ ​

解题思路 ​

12. 有效的括号 ⭐ ​

解题思路 ​

13. 反转链表 ⭐ ​

核心图解 ​

14. 二叉树的层序遍历 ⭐⭐ ​

核心要点 ​

15. 最大子数组和 ⭐⭐ ​

核心思想 ​

16. LRU 缓存 ⭐⭐⭐ ​

两种方案对比 ​

17. 合并两个有序数组 ⭐ ​

核心思想 ​

18. 爬楼梯 ⭐ ​

DP 分析 ​

19. 全排列 ⭐⭐ ​

回溯递归树 ​

回溯模板 ​

20. 接雨水 ⭐⭐⭐ ​

核心原理 ​

三种方案对比 ​

算法与手写题

1. 手写 debounce（含 leading / trailing / cancel）

完整实现

测试用例

复杂度

2. 手写 throttle（含时间戳 / 定时器 / 组合版）

完整实现

测试用例

复杂度

3. 手写 deepClone（处理循环引用 / 特殊类型）

完整实现

测试用例

复杂度

4. 手写 flat（数组拍平，支持指定深度）

完整实现

测试用例

复杂度

5. 手写 curry（柯里化，支持占位符）

完整实现

测试用例

复杂度

6. 手写 EventEmitter（含 on / off / emit / once）

完整实现

测试用例

关键细节

7. 手写 Promise.all / Promise.race

完整实现

测试用例

8. 手写 async/await 自动执行器

完整实现

测试用例

原理分析

9. 手写 LazyMan（链式调用 + sleep）

完整实现

测试用例

核心设计

10. 手写并发请求控制器（最大并发数限制）

完整实现

测试用例

核心设计

二、LeetCode 高频算法

11. 两数之和 ⭐

解题思路

12. 有效的括号 ⭐

解题思路

13. 反转链表 ⭐

核心图解

14. 二叉树的层序遍历 ⭐⭐

核心要点

15. 最大子数组和 ⭐⭐

核心思想

16. LRU 缓存 ⭐⭐⭐

两种方案对比

17. 合并两个有序数组 ⭐

核心思想

18. 爬楼梯 ⭐

DP 分析

19. 全排列 ⭐⭐

回溯递归树

回溯模板

20. 接雨水 ⭐⭐⭐

核心原理

三种方案对比