前端笔记

Appearance

算法 ​

LeetCode ​

题目 ​

排列组合 ​

  • 全排列: 回溯法
  • 实现 [['a', 'b'], ['n', 'm'], ['0', '1']]（长度不固定） 的全排列为 ['an0', 'an1', 'am0', 'am1', 'bn0', 'bn1', 'bm0', 'bm1']
ts
function combineList(list: string[][]) {
  const result: string[] = []

  function dfs(index: number, current: string) {
    if (index === list.length) {
      result.push(current)
      return
    }

    for (const char of list[index])
      dfs(index + 1, current + char)
  }

  dfs(0, '')

  return result
}

console.log(
  combineList([['a', 'b'], ['n', 'm'], ['0', '1']]),
)
function combineList(list: string[][]) {
  const result: string[] = []

  function dfs(index: number, current: string) {
    if (index === list.length) {
      result.push(current)
      return
    }

    for (const char of list[index])
      dfs(index + 1, current + char)
  }

  dfs(0, '')

  return result
}

console.log(
  combineList([['a', 'b'], ['n', 'm'], ['0', '1']]),
)
ts
function combineList2(list: string[][]) {
  if (list.length === 0)
    return []

  let result: string[] = []

  for (const sublist of list) {
    const newResult: string[] = []

    for (const char of sublist) {
      if (result.length === 0) {
        newResult.push(char)
      }
      else {
        for (const item of result)
          newResult.push(item + char)
      }
    }

    result = newResult
  }

  return result
}

console.log(
  combineList2([['a', 'b'], ['n', 'm'], ['0', '1']]),
)
function combineList2(list: string[][]) {
  if (list.length === 0)
    return []

  let result: string[] = []

  for (const sublist of list) {
    const newResult: string[] = []

    for (const char of sublist) {
      if (result.length === 0) {
        newResult.push(char)
      }
      else {
        for (const item of result)
          newResult.push(item + char)
      }
    }

    result = newResult
  }

  return result
}

console.log(
  combineList2([['a', 'b'], ['n', 'm'], ['0', '1']]),
)

快速排序 ​

红黑树的特性 ​

红黑树｜百度百科

腾讯前端实习一面问了我 红黑树……？ 面微信的时候又被问了