前端面试常见算法题和应用题

应用题

lodash 中的 get 函数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function _get(
  origin: Record<string, any>,
  path: string | string[],
  defualtValue: any = 'explosion'
) {
  // judge
  if (typeof path === 'string') {
    // match
    const reg = /[^\[\].]+/g
    path = path.match(reg) as string[]
  }
  let result = origin
  for (const key of path) {
    if (result && typeof result === 'object' && key in result) {
      result = result[key]
    } else {
      return defualtValue
    }
  }
  return result
}

使用 Promise 实现红绿灯交替重复

采用 primise 中的 then 去循环

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
const red = () => {
  console.log('red')
}
const green = () => {
  console.log('green')
}
const yellow = () => {
  console.log('yellow')
}
const light = (timer: number, cb: Function): Promise<void> => {
  return new Promise((resolve, reject) => {
    cb()
    setTimeout(() => {
      resolve()
    }, timer)
  })
}
const step = () => {
  Promise.resolve()
    .then(() => {
      return light(3000, red)
    })
    .then(() => {
      return light(2000, green)
    })
    .then(() => {
      return light(1000, yellow)
    })
    .then(() => {
      return step()
    })
}
step()

防抖和节流

防抖: 在一段操作结束后, 执行最后一次操作的回调函数

节流: 在一段时间内只执行一次

1
2
3
4
5
6
7
8
9
10
// 防抖
const debounce = (fn, time) => {
  let timer
  return (...args) => {
    clearTimeout(timer)
    timer = setTimeout(() => {
      fn.apply(this, ...args)
    }, time)
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
// 节流
const throttled = (fn, time) => {
  let inThrottled = false
  return (...args) => {
    if (!inThrottled) {
      inThrottled = true
      fn.apply(this, ...args)
      setTimeout(() => {
        inThrottled = false
      }, time)
    }
  }
}

深拷贝

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
const isObjectType = (origin) =>
  (typeof origin === 'object' && origin !== null) ||
  typeof origin === 'function'
const deepClone = (origin, map = new WeakMap()) => {
  // 如果不是对象则直接返回
  if (!isObjectType(origin)) return origin
  // 判断是否是循环引用
  if (map.has(origin)) return map.get(origin)
  // 判断 Date| RegExp | Map | Set
  if (origin instanceof Date) {
    return new Date(origin)
  }
  if (origin instanceof RegExp) {
    return new RegExp(origin)
  }
  if (origin instanceof Map) {
    const target = new Map()
    origin.forEach((key, value) => {
      target.set(deepClone(key, map), deepClone(value, map))
    })
    return target
  }
  if (origin instanceof Set) {
    const target = new Set()
    origin.forEach((value) => {
      target.add(deepClone(value, map))
    })
    return target
  }
  const target = new origin.contruct()
  map.set(origin, target)
  for (const key in origin) {
    target[key] = deepClone(origin[key], origin)
  }
  return target
}

发布订阅模式 Events

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
type Callback = (...args: any[]) => any
type Subscription = {
  unsubscribe: () => void
}

class EventEmitter {
  Events: Map<string, Callback[]>
  constructor() {
    this.Events = new Map()
  }
  subscribe(eventName: string, callback: Callback): Subscription {
    // 给定eventName
    this.Events.set(
      eventName,
      this.Events.has(eventName)
        ? [...(this.Events.get(eventName) as Callback[]), callback]
        : [callback]
    )
    return {
      unsubscribe: () => {
        // 解绑当前的callback
        this.Events.set(
          eventName,
          (this.Events.get(eventName) as Callback[]).filter(
            (item) => item !== callback
          )
        )
      }
    }
  }

  emit(eventName: string, args: any[] = []): any[] {
    if (this.Events.has(eventName)) {
      const result: any[] = []
      ;(this.Events.get(eventName) as Callback[]).forEach((callback) => {
        result.push(callback(...args))
      })
      return result
    } else {
      return []
    }
  }
}

版本号排序

可以使用循环比较 也可以使用大树加权的做法去完成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
const versionSort = (versions: string[]) => {
  const sortfun = (next: string, prev: string) => {
    // 循环比较
    const nextArr = next.split('.')
    const prevArr = prev.split('.')
    let i = 0
    while (1) {
      if (nextArr[i] && prevArr[i]) {
        if (nextArr[i] === prevArr[i]) {
          i++
          continue
        }
        return Number(prevArr[i]) - Number(nextArr[i])
      }
      return prev.length - next.length
    }
    return 1
  }

  return versions.sort(sortfun)
}

大数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
// 没考虑小数和负数
const bigNumberAdd = (a: string, b: string): string => {
  const maxLength = Math.max(a.length, b.length)
  a = a.padStart(maxLength, '0')
  a = a.padStart(maxLength, '0')
  let curry = 0
  let sum = ''
  for (let i = maxLength - 1; i >= 0; i--) {
    const total = parseInt(a[i]) + parseInt(b[i]) + curry
    curry = Math.floor(total / 10)
    sum = String(total % 10) + sum
  }
  if (curry === 1) {
    sum = '1' + sum
  }
  return sum
}

实现数组拍平 树转数组 数组转树 对象拍平函数

数组拍平

1
2
3
4
5
6
7
8
9
const flatArr = (originArr, deep = 1) => {
  return deep > 0
    ? originArr.reduce(
        (pre, cur) =>
          pre.concat(Array.isArray(cur) ? flatArr(cur, deep - 1) : cur),
        []
      )
    : originArr.slice()
}

树转数组 递归实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const treeToList = (tree: any) => {
  const result: any[] = []
  const getItem = (tree: any) => {
    for (let i = 0; i < tree.length; i++) {
      if (tree[i].children) {
        getItem(tree[i].children)
        delete tree[i].children
      }
      result.push(tree[i])
    }
  }
  getItem(tree)
  return result
}

数组转树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const listToTree = (list: any) => {
  const result: any[] = []
  const getItem = (list: any, result: any[], pid: number) => {
    for (const item of list) {
      if (item.pid === pid) {
        const newItem = { ...item, children: [] }
        result.push(newItem)
        getItem(list, newItem.children, item.id)
      }
    }
  }
  getItem(list, result, 0)
  console.dir(result, {
    depth: null
  })
}

对象拍平

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const flateen = (originObj: any) => {
  const res: Record<string, any> = {}
  const flat = (item: any, preKey: any = '') => {
    Object.entries(item).forEach(([key, value]) => {
      let newKey = key
      if (Array.isArray(item)) {
        newKey = preKey ? `${preKey}[${key}]` : key
      } else {
        newKey = preKey ? `${preKey}.${key}` : key
      }
      if (value && typeof value === 'object') {
        flat(value, newKey)
      } else {
        res[newKey] = value
      }
    })
  }
  flat(originObj)
  return res
}

实现PromisePool|PromiseAllSet|PromiseAll|PromiseRace功能

PromisePool

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
const promisePool = async <T>(funcs: (() => T)[], limit: number) => {
  const pool = new Set()
  const ans: T[] = []
  const runTask = async (func: () => T) => {
    const p = Promise.resolve(func())
      .then((res) => {
        ans.push(res)
      })
      .finally(() => {
        pool.delete(p)
      })
    pool.add(p)
    if (pool.size > limit) {
      await Promise.race(pool)
    }
  }
  for (const func of funcs) {
    await runTask(func)
  }
  Promise.all(pool)
  return ans
}

PromiseAllSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const myPromiseAllSet = <T>(
  Funcs: (() => Promise<T>)[]
): Promise<{ status: string; data: T }[]> => {
  return new Promise((resolve, reject) => {
    let funCount = 0
    const n = Funcs.length
    const results = Array(n)
    Funcs.forEach((func, index) => {
      func()
        .then((res) => ({ status: 'Fullied', data: res }))
        .catch((err) => ({ status: 'Reject', data: err }))
        .then((res) => {
          results[index] = res
          funCount++
          if (funCount === n) resolve(results)
        })
    })
  })
}

PromiseAll

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const promiseAll = <T>(funcs: (() => Promise<T>)[]): Promise<T[]> => {
  return new Promise((resolve, reject) => {
    const result: T[] = []
    let count = 0
    funcs.forEach((func, index) => {
      func()
        .then((res) => {
          result[index] = res
          count++
          if (count === funcs.length) {
            resolve(result)
          }
        })
        .catch(reject)
    })
  })
}

PromiseRace

1
2
3
4
5
6
7
const promiseRace = <T>(funcs: (() => Promise<T>)[]): Promise<T> => {
  return new Promise((resolve, reject) => {
    funcs.forEach((func) => {
      func().then(resolve, reject)
    })
  })
}

实现bind|call|apply功能

bind

1
2
3
4
5
6
Function.prototype.bind = (context, ...args) => {
  context = context || window
  return () => {
    this.call(context, ...args)
  }
}

call

1
2
3
4
5
6
7
Function.prototype.call = (context, ...args) => {
  context = context || window
  context.fn = this
  let result = context.fn(...args)
  delete context.fn
  return result
}

apply

1
2
3
4
5
6
7
Function.prototype.call = (context, args) => {
  context = context || window
  context.fn = this
  let result = context.fn(...args)
  delete context.fn
  return result
}

new

1
2
3
4
5
6
const myNew = (fn: Function, ...args) => {
  const obj: Object = {}
  obj.__proto__ = fn.prototype
  let result = fn.apply(obj, ...args)
  return result instanceof Object ? result : obj
}

实现 Curry 柯粒化函数

1
2
3
4
5
6
7
8
9
10
11
12
const curry = (fn: Function) => {
  return function curried(...args) {
    const context = this
    if (fn.length <= args.length) {
      return fn.apply(context, ...args)
    } else {
      return (...newArgs) => {
        return curried.apply(context, ...args.concat(newArgs))
      }
    }
  }
}

Promise 中的事件循环机制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class TestErr extends Error {
  constructor(message, fn) {
    super(message)
    this.name = 'TestErr'
    this.fn = fn
    this.canceled = false
  }
  preventDefault() {
    this.canceled = true
  }
  start() {
    if (!this.canceled) {
      this.fn()
    }
    return this
  }
}
new Promise((res, rej) => {
  rej(new TestErr('Test1', () => console.error('Test1')).start())
}).catch((e) => {
  e.preventDefault()
  console.warn('Test1')
})

new Promise((res, rej) => {
  rej(new TestErr('Test2', () => console.error('Test2')).start())
}).catch((e) => {
  console.warn('Test2')
})

要求让可以使用e.preventDefault()去阻止执行 fn 的默认行为

本质上就是修改 start 函数的实行顺序, 让其在.catch 之后在去执行该函数
可以修改成微任务中包含一个微任务 抑或是 使用宏任务去完成

1
2
3
4
5
6
7
8
9
10
11
12
13
queueMicrotask(() => {
  Promise.resolve().then(() => {
    if (!this.canceled) {
      this.fn()
    }
  })
})
//
setTimeout(() => {
  if (!this.canceled) {
    this.fn()
  }
}, 0)

请求的串行, 重试, 超时等

串行

  1. 最简单的使用await

    1
    2
    3
    4
    5
    6
    7
    8
    9
    async function fetchSequentially(urls: string[]): Promise<any[]> {
      const results = []
      for (const url of urls) {
        const response = await fetch(url)
        const data = await response.json()
        results.push(data)
      }
      return results
    }

  2. 使用递归完成

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    const fetchSequentiallyRecursive = (urls: string[]): Promise<any> => {
      const results: any[] = []
      const fetchNext = (index: number): Promise<any> => {
        if (index >= urls.length) {
          return Promise.resolve(results)
        }
        return fetch(urls[index])
          .then((res) => res.json())
          .then((data) => {
            results.push(data)
            return fetchNext(index + 1)
          })
      }
      return fetchNext(0)
    }

  3. 使用 promise.then 完成

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    function fetchSequentiallyWithPromise(urls: string[]): Promise<any[]> {
      const results: any[] = []
      let promiseChain = Promise.resolve()

      urls.forEach((url) => {
        promiseChain = promiseChain
          .then(() => fetch(url))
          .then((response) => response.json())
          .then((data) => {
            results.push(data)
          })
      })

      return promiseChain.then(() => results)
    }

重试

循环

1
2
3
4
5
6
7
8
9
10
11
12
async function fetchWithRetry(url: string, retries: number): Promise<any> {
  while (retries > 0) {
    try {
      const response = await fetch(url)
      if (!response.ok) throw new Error('Fetch failed')
      return await response.json()
    } catch (error) {
      retries--
      if (retries === 0) throw error
    }
  }
}

递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function fetchWithRetry(url: string, retries: number): Promise<any> {
  return fetch(url)
    .then((response) => {
      if (!response.ok) throw new Error('Fetch failed')
      return response.json()
    })
    .catch((error) => {
      if (retries > 0) {
        return fetchWithRetry(url, retries - 1)
      } else {
        throw error
      }
    })
}

超时

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const fetchWithTimeout = (url: string, timeout: number): Promise<any> => {
  return new Promise((resolve, reject) => {
    const timer = setTimeout(() => {
      reject(new Error('Request timed out'))
    })
    fetch(url)
      .then((res) => {
        clearTimeout(timer)
        resolve(res.json())
      })
      .catch((err) => {
        clearTimeout(timer)
        reject(err)
      })
  })
}

请求的功能库

包括暂停,重启,开始,完成 等多个功能

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
class Queue {
  private requestQueue: string[]
  private limit: number
  private timeout: number
  private finishCb?: Function
  private stopCb?: Function
  private restartCb?: Function
  private activeRequests: number
  private paused: boolean
  private pendingRequests: string[]
  constructor(requestQueue?: string[], limit?: number, timeout?: number) {
    this.requestQueue = requestQueue || []
    this.limit = limit || 5
    this.timeout = timeout || 3000
    this.activeRequests = 0
    this.paused = false
    this.pendingRequests = []
  }
  onFinished(finishCb: Function) {
    this.finishCb = finishCb
  }
  onStop(stopCb: Function) {
    this.stopCb = stopCb
  }
  onRestart(restartCb: Function) {
    this.restartCb = restartCb
  }
  add(request: string) {
    this.requestQueue.push(request)
    this.processQueue()
  }
  start() {
    this.paused = false
    this.processQueue()
  }
  stop() {
    this.paused = false
    this.pendingRequests = []
    this.stopCb?.()
  }
  restart() {
    this.paused = false
    this.requestQueue.push(...this.pendingRequests)
    this.pendingRequests = []
    this.processQueue()
    this.restartCb?.()
  }
  private processQueue() {
    if (this.paused || this.activeRequests >= this.limit) {
      return
    }

    while (this.activeRequests < this.limit && this.requestQueue.length > 0) {
      const request = this.requestQueue.shift()!
      this.activeRequests++
      this.executeRequest(request).then(() => {
        this.activeRequests--
        this.processQueue()
      })
    }

    if (
      this.requestQueue.length === 0 &&
      this.activeRequests === 0 &&
      this.finishCb
    ) {
      this.finishCb()
    }
  }

  private executeRequest(request: string): Promise<void> {
    return new Promise((resolve) => {
      const timeoutId = setTimeout(() => {
        resolve()
      }, this.timeout)

      setTimeout(() => {
        clearTimeout(timeoutId)
        resolve()
      }, Math.random() * this.timeout)
    })
  }
}

TS 中的体操运算

实现逻辑或
1

常见的排序算法以及原理

冒泡排序: 双层循环去逐一比较

1
2
3
4
5
6
7
8
9
10
11
const bubbleSort = (arr: Number[]): Number[] => {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    for (let j = 0; j < len - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        ;[arr[j], arr[j + 1]] = [arr[j + 1], arr[j]]
      }
    }
  }
  return arr
}

选择排序: 每次找出最小的值放入前方

1
2
3
4
5
6
7
8
9
10
11
12
13
const selectionSort = (arr: Number[]): Number[] => {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    let minIndex = i
    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j
      }
    }
    ;[arr[i], arr[minIndex]] = [arr[minIndex], arr[i]]
  }
  return arr
}

插入排序: 从后面选择一个数字插入到前面已经排好的序列中

1
2
3
4
5
6
7
8
9
10
11
12
13
const insertSort = (arr: Number[]): Number[] => {
  const len = arr.length
  for (let i = 0; i < len; i++) {
    let prevIndex = i - 1
    let current = arr[i]
    while (arr[prevIndex] > current && prevIndex >= 0) {
      arr[prevIndex + 1] = arr[prevIndex]
      prevIndex--
    }
    arr[prevIndex + 1] = current
  }
  return arr
}

希尔排序: 定义一个 gap 去分组 gap 排序 直到 gap 为 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
const shellSort = (arr: Number[]): Number[] => {
  const len = arr.length
  // 设置成数组一半逐步减少间隔
  for (let gap = Math.floor(len / 2); gap > 0; gap = Math.floor(gap / 2)) {
    // 对每个间隔进行排序
    for (let i = gap; i < len; i++) {
      let j = i
      while (j >= gap && arr[j] < arr[j - gap]) {
        ;[arr[j], arr[j - gap]] = [arr[j - gap], arr[j]]
        j -= gap
      }
    }
  }
  return arr
}

归并排序: 采用递归去左右分治排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
const merge = (left: number[], right: number[]): number[] => {
  let result: number[] = []
  while (left.length && right.length) {
    if (left[0] < right[0]) {
      result.push(left.shift() as number)
    } else {
      result.push(right.shift() as number)
    }
  }
  if (left.length) {
    result = result.concat(left)
  } else {
    result = result.concat(right)
  }
  return result
}
const mergeSort = (arr: number[]): number[] => {
  if (arr.length < 2) return arr
  const mid = Math.floor(arr.length / 2)
  const leftArr = mergeSort(arr.slice(0, mid))
  const rightArr = mergeSort(arr.slice(mid))
  return merge(leftArr, rightArr)
}

快速排序: 找出一个基准值 然后左右分治

1
2
3
4
5
6
7
8
9
10
11
12
const quickSort = (arr: number[]): number[] => {
  if (arr.length <= 1) return arr
  const pivot = arr[Math.floor(arr.length / 2)]
  const left: number[] = []
  const right: number[] = []
  for (let i = 0; i < arr.length; i++) {
    if (i === Math.floor(arr.length / 2)) continue
    else if (arr[i] < pivot) left.push(arr[i])
    else right.push(arr[i])
  }
  return [...quickSort(left), pivot, ...quickSort(right)]
}

基数排序

桶排序

计数排序

堆排序

算法题

两数之和

1
2
3
4
5
6
7
8
9
10
11
function twoSum(nums: number[], target: number): number[] {
  // map <num, i>
  const hashMap = new Map<number, number>()
  for (let i = 0; i < nums.length; i++) {
    if (hashMap.has(target - nums[i])) {
      return [hashMap.get(target - nums[i]) as number, i]
    }
    hashMap.set(nums[i], i)
  }
  return []
}

两数之和 - 输入有序数组

可以采取相同的 hashMap 去运算, 或者由于题目中描述的是递增数列, 可以使用双指针来写

1
2
3
4
5
6
7
8
9
10
11
function twoSum(numbers: number[], target: number): number[] {
  let l = 0,
    r = numbers.length - 1
  while (l < r) {
    const sum = numbers[l] + numbers[r]
    if (sum === target) return [l + 1, r + 1]
    else if (sum < target) l++
    else r--
  }
  return []
}

和为 k 的子数组

利用前缀和 + 哈希表来完成这个工作

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function subarraySum(nums: number[], k: number): number {
  // <prefixSum, count>
  const hashMap = new Map<number, number>()
  hashMap.set(0, 1)
  let sum = 0
  let ans = 0
  for (const num of nums) {
    sum += num
    // 找到满足k的部分子数组
    if (hashMap.has(sum - k)) {
      ans += hashMap.get(sum - k) as number
    }
    // update
    hashMap.set(sum, hashMap.has(sum) ? (hashMap.get(sum) as number) + 1 : 1)
  }
  return ans
}

K 和数对的最大数目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function maxOperations(nums: number[], k: number): number {
  const hashMap = new Map<number, number>()
  let ans = 0
  for (const num of nums) {
    const cnt = hashMap.get(k - num)
    if (cnt) {
      hashMap.set(k - num, cnt - 1)
      ans++
    } else {
      hashMap.set(num, (hashMap.get(num) ?? 0) + 1)
    }
  }
  return ans
}

三数之和

遍历双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function threeSum(nums: number[]): number[][] {
  const ans: number[][] = []
  nums = nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length; i++) {
    if (i && nums[i] === nums[i - 1]) continue
    if (nums[i] > 0) continue
    let l = i + 1,
      r = nums.length - 1
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r]
      if (sum === 0) {
        ans.push([nums[i], nums[l], nums[r]])
        while (l < r && nums[l] === nums[++l]) {}
        while (l < r && nums[r] === nums[--r]) {}
      } else if (sum < 0) l++
      else r--
    }
  }
  return ans
}

接近三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
function threeSumClosest(nums: number[], target: number): number {
  nums = nums.sort((a, b) => a - b)
  let ans = 0
  // 维护一个sum - target的diff比较
  let maxDiff = Infinity
  for (let i = 0; i < nums.length - 2; i++) {
    if (i && nums[i] === nums[i - 1]) continue
    // 如果前三位比target大 说明已经结束力
    if (nums[i] + nums[i + 1] + nums[i + 2] >= target) {
      if (nums[i] + nums[i + 1] + nums[i + 2] - target < maxDiff) {
        ans = nums[i] + nums[i + 1] + nums[i + 2]
      }
      break
    }
    // 如果当前的i和最后的最大值比target小 --> 不用去采取while了
    if (nums[i] + nums[nums.length - 1] + nums[nums.length - 2] < target) {
      if (
        target - nums[i] - nums[nums.length - 1] - nums[nums.length - 2] <
        maxDiff
      ) {
        maxDiff =
          target - nums[i] - nums[nums.length - 1] - nums[nums.length - 2]
        ans = nums[i] + nums[nums.length - 1] + nums[nums.length - 2]
      }
      continue
    }
    // 正常遍历双指针
    let l = i + 1,
      r = nums.length - 1
    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r]
      if (sum === target) {
        return target
      } else if (sum < target) {
        if (target - sum < maxDiff) {
          maxDiff = target - sum
          ans = sum
        }
        l++
      } else {
        if (sum - target < maxDiff) {
          maxDiff = sum - target
          ans = sum
        }
        r--
      }
    }
  }
  return ans
}

四数之和

遍历 + 三数之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function fourSum(nums: number[], target: number): number[][] {
  const ans: number[][] = []
  nums = nums.sort((a, b) => a - b)
  for (let i = 0; i < nums.length; i++) {
    if (i && nums[i] === nums[i - 1]) continue
    if (nums[i] + nums[i + 1] + nums[i + 2] + nums[i + 3] > target) break
    if (
      nums[i] +
        nums[nums.length - 1] +
        nums[nums.length - 2] +
        nums[nums.length - 3] <
      target
    )
      continue
    const threeSum = target - nums[i]
    for (let j = i + 1; j < nums.length; j++) {
      if (j > i + 1 && nums[j] === nums[j - 1]) continue
      let l = j + 1,
        r = nums.length - 1
      while (l < r) {
        const sum = nums[j] + nums[l] + nums[r]
        if (sum === threeSum) {
          ans.push([nums[i], nums[j], nums[l], nums[r]])
          while (l < r && nums[l] === nums[++l]) {}
          while (l < r && nums[r] === nums[--r]) {}
        } else if (sum < threeSum) l++
        else r--
      }
    }
  }
  return ans
}

字母异位词分组

1
2
3
4
5
6
7
8
9
10
11
12
13
function groupAnagrams(strs: string[]): string[][] {
  const hashMap = new Map<string, string[]>()
  for (const str of strs) {
    const sortStr = str.split('').sort().join('')
    hashMap.set(
      sortStr,
      hashMap.has(sortStr)
        ? [...(hashMap.get(sortStr) as string[]), str]
        : [str]
    )
  }
  return Array.from(hashMap.values())
}

最长连续序列

1
2
3
4
5
6
7
8
9
10
11
12
function longestConsecutive(nums: number[]): number {
  nums = nums.sort((a, b) => a - b)
  const hashMap = new Map<number, number>()
  for (const num of nums) {
    if (hashMap.has(num - 1)) {
      hashMap.set(num, (hashMap.get(num - 1) as number) + 1)
    } else {
      hashMap.set(num, 1)
    }
  }
  return Math.max(...hashMap.values(), 0)
}

移动零

双指针 移动 0 到尾

1
2
3
4
5
6
7
8
9
10
11
12
13
function moveZeroes(nums: number[]): void {
  let i = 0,
    j = 0
  while (j < nums.length) {
    if (nums[j] !== 0) {
      if (i !== j) {
        ;[nums[i], nums[j]] = [nums[j], nums[i]]
      }
      i++
    }
    j++
  }
}

盛水最多的容器

双指针判断比较

1
2
3
4
5
6
7
8
9
10
11
12
function maxArea(height: number[]): number {
  let max = 0
  let l = 0,
    r = height.length - 1
  while (l < r) {
    max =
      height[l] > height[r]
        ? Math.max(max, (r - l) * height[r--])
        : Math.max(max, (r - l) * height[l++])
  }
  return max
}

接雨水

双指针找出 MaxLeft || MaxRight

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
function trap(height: number[]): number {
  let ans = 0
  if (height.length < 3) return ans
  const maxHeight = Math.max(...height)
  let leftMaxIndex = 0
  let rightMaxIndex = height.length - 1
  for (let i = 0; i < height.length; i++) {
    if (height[i] === maxHeight) {
      leftMaxIndex = i
      break
    }
  }
  for (let i = height.length - 1; i >= 0; i--) {
    if (height[i] === maxHeight) {
      rightMaxIndex = i
      break
    }
  }
  // 计算left - right 之间的
  for (let i = leftMaxIndex + 1; i < rightMaxIndex; i++) {
    ans += maxHeight - height[i]
  }
  // 计算0 - left 之间的
  let limit = height[0]
  for (let i = 1; i <= leftMaxIndex; i++) {
    if (height[i] < limit) {
      ans += limit - height[i]
    } else {
      limit = height[i]
    }
  }
  // 计算right - height.length - 1
  limit = height[height.length - 1]
  for (let i = height.length - 2; i >= rightMaxIndex; i--) {
    if (height[i] < limit) {
      ans += limit - height[i]
    } else {
      limit = height[i]
    }
  }
  return ans
}

无重复最长子串

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function lengthOfLongestSubstring(s: string): number {
  let max = 0
  let temp = ''
  for (const ch of s) {
    if (!temp.includes(ch)) {
      temp += ch
    } else {
      temp = temp.slice(temp.indexOf(ch) + 1)
      temp += ch
    }
    max = Math.max(max, temp.length)
  }
  return max
}

字符串中所有的字母异位词

指针 + 滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function findAnagrams(s: string, p: string): number[] {
  const ans: number[] = []
  const newArr: number[] = new Array(26).fill(0)
  for (const ch of p) {
    const index = ch.charCodeAt(0) - 'a'.charCodeAt(0)
    newArr[index]++
  }
  const ls = s.length,
    lp = p.length
  let l = 0,
    r = 0
  while (r < ls) {
    const rightIndex = s[r].charCodeAt(0) - 'a'.charCodeAt(0)
    newArr[rightIndex]--
    // 移动左窗口
    while (newArr[rightIndex] < 0) {
      const leftIndex = s[l].charCodeAt(0) - 'a'.charCodeAt(0)
      newArr[leftIndex]++
      l++
    }
    if (r - l + 1 === lp) ans.push(l)
    r++
  }
  return ans
}

滑动窗口最大值

维护一个存储下标的递减队列, 每次去判断取值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function maxSlidingWindow(nums: number[], k: number): number[] {
  const ans: number[] = []
  const stack: number[] = []
  for (let i = 0; i < k; i++) {
    while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) {
      stack.pop()
    }
    stack.push(i)
  }
  ans.push(nums[stack[0]])
  for (let i = k; i < nums.length; i++) {
    // 不在窗口中
    if (stack[0] <= i - k) stack.shift()
    while (stack.length && nums[stack[stack.length - 1]] <= nums[i]) stack.pop()
    stack.push(i)
    ans.push(nums[stack[0]])
  }
  return ans
}

最小覆盖子串

滑动窗口 + 数组频率 + 不断尝试收缩左边找出 min

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
const getStringId = (s: string): number => {
  return s >= 'A' && s <= 'Z'
    ? s.charCodeAt(0) - 'A'.charCodeAt(0) + 26
    : s.charCodeAt(0) - 'a'.charCodeAt(0)
}

function minWindow(s: string, t: string): string {
  let ans = ''
  // 目标数组的频率
  const targetFrequentArr = Array(60).fill(0)
  // 滑动窗口的频率
  const windowFrequentArr = Array(60).fill(0)
  // 字母数
  let count = 0
  for (const ch of t) {
    if (++targetFrequentArr[getStringId(ch)] === 1) {
      count++
    }
  }
  for (let l = 0, r = 0; r < s.length; r++) {
    const indexR = getStringId(s[r])
    if (++windowFrequentArr[indexR] === targetFrequentArr[indexR]) {
      count--
    }
    while (l < r) {
      const indexL = getStringId(s[l])
      if (windowFrequentArr[indexL] > targetFrequentArr[indexL]) {
        windowFrequentArr[indexL]--
        if (windowFrequentArr[indexL] >= 0) l++
      } else {
        break
      }
    }
    if (count === 0 && (!ans || ans.length > r - l + 1)) {
      ans = s.slice(l, r + 1)
    }
  }
  return ans
}

最大子数组和

mybe 类似于 dp ?

1
2
3
4
5
6
7
function maxSubArray(nums: number[]): number {
  const dp = [...nums]
  for (let i = 1; i < dp.length; i++) {
    dp[i] = Math.max(dp[i], dp[i] + dp[i - 1])
  }
  return Math.max(...dp)
}

合并区间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function merge(intervals: number[][]): number[][] {
  const ans: number[][] = []
  intervals = intervals.sort((a, b) => a[0] - b[0])
  let temp = intervals[0]
  for (let i = 1; i < intervals.length; i++) {
    if (temp[1] < intervals[i][0]) {
      ans.push(temp)
      temp = intervals[i]
    } else {
      if (temp[1] < intervals[i][1]) {
        temp = [temp[0], intervals[i][1]]
      }
    }
  }
  ans.push(temp)
  return ans
}

除自身以外数组的乘积

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function productExceptSelf(nums: number[]): number[] {
  const ans: number[] = Array(nums.length).fill(1)
  const help = [...nums]
  for (let i = 1; i < help.length; i++) {
    help[i] = help[i - 1] * help[i]
  }
  let right = 1
  for (let i = nums.length - 1; i >= 1; i--) {
    ans[i] = help[i - 1] * right
    right = right * nums[i]
  }
  ans[0] = right
  return ans
}

缺失的第一个正数

数组技巧

1
2
3
4
5
6
7
8
9
10
11
function firstMissingPositive(nums: number[]): number {
  const record: number[] = [1]
  for (const num of nums) {
    if (num > 0) {
      record[num] = 1
    }
  }
  return record.findIndex((item) => !item) === -1
    ? record.length
    : record.findIndex((item) => !item)
}

矩阵置零

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function setZeroes(matrix: number[][]): void {
  const row = matrix.length
  const col = matrix[0].length
  const rowSet = new Set<number>()
  const colSet = new Set<number>()
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (matrix[i][j] === 0) {
        rowSet.add(i)
        colSet.add(j)
      }
    }
  }
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (rowSet.has(i) || colSet.has(j)) {
        matrix[i][j] = 0
      }
    }
  }
}

螺旋矩阵

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
function spiralOrder(matrix: number[][]): number[] {
  const ans: number[] = []
  const m = matrix.length,
    n = matrix[0].length
  let l = 0,
    r = n - 1,
    top = 0,
    bottom = m - 1
  while (l <= r && top <= bottom) {
    // forEach top
    for (let i = l; i <= r && top <= bottom; i++) {
      ans.push(matrix[top][i])
    }
    top++
    // Right
    for (let i = top; i <= bottom && l <= r; i++) {
      ans.push(matrix[i][r])
    }
    r--
    // Bottom
    for (let i = r; i >= l && top <= bottom; i--) {
      ans.push(matrix[bottom][i])
    }
    bottom--
    // Left
    for (let i = bottom; i >= top && l <= r; i--) {
      ans.push(matrix[i][l])
    }
    l++
  }
  return ans
}

旋转图像

搜索二维矩阵

相交链表

循环 headA + headB && headB + headA 找出相同的 teturn 即可

1
2
3
4
5
6
7
8
9
10
11
12
function getIntersectionNode(
  headA: ListNode | null,
  headB: ListNode | null
): ListNode | null {
  let PA = headA
  let PB = headB
  while (PA !== PB) {
    PA = PA ? PA.next : headB
    PB = PB ? PB.next : headA
  }
  return PA
}

反转链表

1
2
3
4
5
6
7
8
9
10
11
function reverseList(head: ListNode | null): ListNode | null {
  let ans: ListNode | null = null
  let cur = head
  while (cur) {
    const next = cur.next
    cur.next = ans
    ans = cur
    cur = next
  }
  return ans
}

回文链表

可以转化成数组判断 || 使用 stack 栈来判断

1
2
3
4
5
6
7
8
9
10
11
12
function isPalindrome(head: ListNode | null): boolean {
  const arr: number[] = []
  let cur = head
  while (cur) {
    arr.push(cur.val)
    cur = cur.next
  }
  for (let i = 0; i < Math.floor(arr.length / 2); i++) {
    if (arr[i] !== arr[arr.length - 1 - i]) return false
  }
  return true
}

环形链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function hasCycle(head: ListNode | null): boolean {
  const recordSet = new Set<ListNode | null>()
  let cur = head
  while (cur) {
    if (recordSet.has(cur)) return true
    recordSet.add(cur)
    cur = cur.next
  }
  return false
}
function detectCycle(head: ListNode | null): ListNode | null {
  const hashMap = new WeakMap<ListNode, ListNode | null>()
  let cur = head
  while (cur) {
    if (hashMap.has(cur)) return hashMap.get(cur) as ListNode | null
    hashMap.set(cur, cur)
    cur = cur.next
  }
  return null
}

合并两个有序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function mergeTwoLists(
  list1: ListNode | null,
  list2: ListNode | null
): ListNode | null {
  const dumy = new ListNode(0, null)
  let cur = dumy
  while (list1 && list2) {
    if (list1.val < list2.val) {
      cur.next = list1
      list1 = list1.next
    } else {
      cur.next = list2
      list2 = list2.next
    }
    cur = cur.next
  }
  if (list1) {
    cur.next = list1
  } else {
    cur.next = list2
  }
  return dumy.next
}

两数相加

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
function addTwoNumbers(
  l1: ListNode | null,
  l2: ListNode | null
): ListNode | null {
  const dumy = new ListNode(0, null)
  let cur = dumy
  let curry = 0
  while (l1 || l2 || curry) {
    const val1 = l1?.val || 0
    const val2 = l2?.val || 0
    const sum = (val1 + val2 + curry) % 10
    curry = val1 + val2 + curry >= 10 ? 1 : 0
    cur.next = new ListNode(sum, null)
    cur = cur.next
    if (l1) l1 = l1.next
    if (l2) l2 = l2.next
  }
  return dumy.next
}

删除倒数第 N 个节点

快慢指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function removeNthFromEnd(head: ListNode | null, n: number): ListNode | null {
  const dumy = new ListNode(0, head)
  let slow = dumy
  let fast = dumy
  while (n-- > 0) {
    fast = fast.next as ListNode
  }
  while (fast && fast.next) {
    slow = slow.next as ListNode
    fast = fast.next
  }
  slow.next = slow.next!.next
  return dumy.next
}

两两交换链表

记录交换的节点关系 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function swapPairs(head: ListNode | null): ListNode | null {
  const dumy = new ListNode(0, head)
  let node0 = dumy
  let node1 = dumy.next
  while (node1 && node1.next) {
    let node2 = node1.next
    let node3 = node2.next
    node0.next = node2
    node2.next = node1
    node1.next = node3
    node0 = node1
    node1 = node3
  }
  return dumy.next
}

k 个一组翻转链表

链表翻转 + 递归

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class ListNode {
  val: number
  next: ListNode | null
  constructor(val?: number, next?: ListNode | null) {
    this.val = val || 0
    this.next = next || null
  }
}

const reveseListNode = (head: ListNode | null, tail: ListNode | null) => {
  let ans: ListNode | null = null
  let cur = head
  while (cur && cur !== tail) {
    const next = cur.next
    cur.next = ans
    ans = cur
    cur = next
  }
  return ans
}
function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
  let start = head
  let end = head
  for (let i = 0; i < k; i++) {
    if (!end) return head
    end = end.next
  }
  const reverserList = reveseListNode(start, end)
  start!.next = reverseKGroup(end, k)
  return reverserList
}

随机链表的复制

使用 weakMap 记录一下 ListNode

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class _Node {
  val: number
  next: _Node | null
  random: _Node | null
  constructor(val?: number, next?: _Node | null, random?: _Node | null) {
    this.val = val || 0
    this.next = next || null
    this.random = random || null
  }
}

function copyRandomList(head: _Node | null): _Node | null {
  const hashMap = new WeakMap<_Node, _Node | null>()
  const createListNode = (node: _Node | null): _Node | null => {
    if (!node) return null
    const newNode = new _Node(node.val)
    hashMap.set(node, newNode)
    if (node.next) newNode.next = createListNode(node.next)
    if (node.random) newNode.random = hashMap.get(node.random) as _Node | null
    return newNode
  }
  return createListNode(head)
}

链表排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function sortList(head: ListNode | null): ListNode | null {
  let arr: number[] = []
  while (head) {
    arr.push(head.val)
    head = head.next
  }
  arr = arr.sort((a, b) => a - b)
  let ans = new ListNode(0)
  let cur = ans
  for (const num of arr) {
    let newNode = new ListNode(num)
    cur.next = newNode
    cur = cur.next
  }
  return ans.next
}

合并 K 个升序链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function mergeKLists(lists: Array<ListNode | null>): ListNode | null {
  let listsArr: number[] = []
  for (let list of lists) {
    while (list) {
      listsArr.push(list.val)
      list = list.next
    }
  }
  listsArr = listsArr.sort((a, b) => a - b)
  const ans = new ListNode(0)
  let cur = ans
  for (const num of listsArr) {
    const newNode = new ListNode(num)
    cur.next = newNode
    cur = cur.next
  }
  return ans.next
}

LRU 缓存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class LRUCache {
  store: { key: number; val: number }[]
  capacity: number
  constructor(capacity: number) {
    this.capacity = capacity
    this.store = []
  }

  get(key: number): number {
    // 遍历当前的store
    const findIndex = this.store.findIndex((item) => item.key === key)
    if (findIndex !== -1) {
      // 找到了 更新
      const val = this.store[findIndex].val
      this.store = this.store.filter((item) => item.key !== key)
      this.store.push({ key: key, val: val })
      return val
    }
    return -1
  }

  put(key: number, value: number): void {
    const findIndex = this.store.findIndex((item) => item.key === key)
    // 找到了相同的 更新并赋新值
    if (findIndex !== -1) {
      this.store = this.store.filter((item) => item.key !== key)
      this.store.push({ key: key, val: value })
    } else {
      // 判断是否要溢出
      if (this.store.length === this.capacity) {
        this.store.shift()
      }
      this.store.push({ key: key, val: value })
    }
  }
}

二叉树中序遍历

1
2
3
4
5
6
7
8
9
10
11
function inorderTraversal(root: TreeNode | null): number[] {
  const res: number[] = []
  const midForeach = (root: TreeNode | null) => {
    if (!root) return
    midForeach(root.left)
    res.push(root.val)
    midForeach(root.right)
  }
  midForeach(root)
  return res
}

二叉树的最大深度

1
2
3
4
5
6
function maxDepth(root: TreeNode | null): number {
  if (!root) return 0
  const left = maxDepth(root.left)
  const right = maxDepth(root.right)
  return Math.max(left, right) + 1
}

翻转二叉树

1
2
3
4
5
6
7
8
function invertTree(root: TreeNode | null): TreeNode | null {
  if (!root) return null
  const left = invertTree(root.left)
  const right = invertTree(root.right)
  root.left = right
  root.right = left
  return root
}

对称二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isSymmetric(root: TreeNode | null): boolean {
  const isSameRoot = (left: TreeNode | null, right: TreeNode | null) => {
    if (left === null || right === null) {
      return left === right
    }
    return (
      left.val === right.val &&
      isSameRoot(left.left, right.right) &&
      isSameRoot(left.right, right.left)
    )
  }
  if (!root) return true
  return isSameRoot(root.left, root.right)
}

二叉树的直径

1
2
3
4
5
6
7
8
9
10
11
12
function diameterOfBinaryTree(root: TreeNode | null): number {
  let maxDiameter = 0
  const maxDepth = (root: TreeNode | null) => {
    if (!root) return 0
    const left = maxDepth(root.left)
    const right = maxDepth(root.right)
    maxDiameter = Math.max(maxDiameter, left + right)
    return Math.max(left, right) + 1
  }
  maxDepth(root)
  return maxDiameter
}

二叉树层序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function levelOrder(root: TreeNode | null): number[][] {
  const ans: number[][] = []
  if (!root) return ans
  const treeStack: TreeNode[] = [root]
  while (treeStack.length) {
    const preStack: TreeNode[] = []
    const preNums: number[] = []
    for (const { val, left, right } of treeStack) {
      preNums.push(val)
      left && preStack.push(left)
      right && preStack.push(right)
    }
    ans.push(preNums)
    treeStack.splice(0, treeStack.length, ...preStack)
  }
  return ans
}

有序数组转化成二叉树

1
2
3
4
5
6
7
8
9
10
function sortedArrayToBST(nums: number[]): TreeNode | null {
  const build = (nums: number[], l: number, r: number): TreeNode | null => {
    if (l > r) return null
    const mid = (l + r) >> 1
    const left = build(nums, l, mid - 1)
    const right = build(nums, mid + 1, r)
    return new TreeNode(nums[mid], left, right)
  }
  return build(nums, 0, nums.length - 1)
}

验证二叉搜索树

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function isValidBST(root: TreeNode | null): boolean {
  const ans: number[] = []
  const midForeach = (root: TreeNode | null) => {
    if (!root) return null
    midForeach(root.left)
    ans.push(root.val)
    midForeach(root.right)
  }
  midForeach(root)
  for (let i = 0; i < ans.length - 1; i++) {
    if (ans[i] >= ans[i + 1]) return false
  }
  return true
}

二叉树中第 k 小的元素

中序遍历

1
2
3
4
5
6
7
8
9
10
11
12
function kthSmallest(root: TreeNode | null, k: number): number {
  let ans = 0
  const midForeach = (root: TreeNode | null) => {
    if (!root) return null
    midForeach(root.left)
    k--
    if (k === 0) ans = root.val
    midForeach(root.right)
  }
  midForeach(root)
  return ans
}

二叉树的右视图

层序遍历的改变

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function rightSideView(root: TreeNode | null): number[] {
  const ans: number[] = []
  if (!root) return ans
  const treeStack: TreeNode[] = [root]
  while (treeStack.length) {
    const preLastNum: number[] = []
    const preUpdateStack: TreeNode[] = []
    for (const { val, left, right } of treeStack) {
      preLastNum.push(val)
      left && preUpdateStack.push(left)
      right && preUpdateStack.push(right)
    }
    preLastNum.length && ans.push(preLastNum[preLastNum.length - 1])
    treeStack.splice(0, treeStack.length, ...preUpdateStack)
  }
  return ans
}

前序中序构造二叉树

1
2
3
4
5
6
7
8
9
10
11
12
13
function buildTree(preorder: number[], inorder: number[]): TreeNode | null {
  // 左右分治
  const n = preorder.length
  if (n === 0) return null
  const leftSize = inorder.indexOf(preorder[0])
  const leftPreorder = preorder.slice(1, leftSize + 1)
  const leftInorder = inorder.slice(0, leftSize + 1)
  const rightPreorder = preorder.slice(leftSize + 1)
  const rightInorder = inorder.slice(leftSize + 1)
  const left = buildTree(leftPreorder, leftInorder)
  const right = buildTree(rightPreorder, rightInorder)
  return new TreeNode(preorder[0], left, right)
}

路径总合

dfs 去寻找 val 同时遍历左和右两种节点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function pathSum(root: TreeNode | null, targetSum: number): number {
  if (!root) return 0
  let ans = 0
  const dfs = (root: TreeNode | null, needVal: number) => {
    if (!root) return
    if (needVal - root.val === 0) ans++
    dfs(root.left, needVal - root.val)
    dfs(root.right, needVal - root.val)
  }
  dfs(root, targetSum)
  ans += pathSum(root.left, targetSum)
  ans += pathSum(root.right, targetSum)
  return ans
}

最近的公共祖先

1
2
3
4
5
6
7
8
9
10
11
function lowestCommonAncestor(
  root: TreeNode | null,
  p: TreeNode | null,
  q: TreeNode | null
): TreeNode | null {
  if (root === null || p === root || q === root) return root
  const left = lowestCommonAncestor(root.left, p, q)
  const right = lowestCommonAncestor(root.right, p, q)
  if (left && right) return root
  return left ?? right
}

二叉树的最大路径和

后序遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
function maxPathSum(root: TreeNode | null): number {
  let maxNumber = -Infinity
  const postOrderTravers = (root: TreeNode | null): number => {
    if (!root) return 0
    const left = postOrderTravers(root.left)
    const right = postOrderTravers(root.right)
    const preMax = Math.max(root.val, root.val + left, root.val + right)
    maxNumber = Math.max(preMax, maxNumber, root.val + left + right)
    return preMax
  }
  postOrderTravers(root)
  return maxNumber
}

岛屿数量

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function numIslands(grid: string[][]): number {
  let ans = 0
  const m = grid.length
  const n = grid[0].length
  const xArr = [1, 0, -1, 0]
  const yArr = [0, 1, 0, -1]
  const dfs = (i: number, j: number) => {
    if (i < 0 || i >= m || j < 0 || j >= n) return
    if (grid[i][j] === '0') return
    grid[i][j] = '0'
    for (let d = 0; d < 4; d++) {
      const [x, y] = [i + yArr[d], j + xArr[d]]
      dfs(x, y)
    }
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === '1') {
        ans++
        dfs(i, j)
      }
    }
  }
  return ans
}

腐烂的橘子

队列维护 广度优先

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
function orangesRotting(grid: number[][]): number {
  let ans = 0
  let count = 0
  const badOrangePosition: number[][] = []
  const m = grid.length,
    n = grid[0].length
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (grid[i][j] === 1) {
        count++
      } else if (grid[i][j] === 2) {
        badOrangePosition.push([i, j])
      }
    }
  }
  const xArr = [1, 0, -1, 0]
  const yArr = [0, 1, 0, -1]
  for (; count && badOrangePosition.length; ans++) {
    const nextBadOragePosition: number[][] = []
    for (const [i, j] of badOrangePosition) {
      for (let d = 0; d < 4; d++) {
        const [x, y] = [i + xArr[d], j + yArr[d]]
        if (x < 0 || x >= m || y < 0 || y >= n) continue
        if (grid[x][y] === 1) {
          count--
          grid[x][y] = 2
          nextBadOragePosition.push([x, y])
        }
      }
    }
    badOrangePosition.splice(
      0,
      badOrangePosition.length,
      ...nextBadOragePosition
    )
  }
  return count > 0 ? -1 : ans
}

实现 Trie

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
class TrieNode {
  val: string
  children: TrieNode[]
  isEnd: boolean
  constructor(val?: string, children?: TrieNode[], isEnd?: boolean) {
    this.val = val || ''
    this.children = children || []
    this.isEnd = !!isEnd
  }
}

class Trie {
  root: TrieNode
  constructor() {
    this.root = new TrieNode('')
  }
  insert(word: string): void {
    let cur = this.root
    for (const ch of word) {
      const find = cur.children.find((item) => item.val === ch)
      if (find) {
        cur = find
      } else {
        const next = new TrieNode(ch)
        cur.children.push(next)
        cur = next
      }
    }
    cur.isEnd = true
  }
  search(word: string): boolean {
    let cur = this.root
    for (const ch of word) {
      const find = cur.children.find((item) => item.val === ch)
      if (!find) return false
      cur = find
    }
    return cur.isEnd
  }
  startsWith(prefix: string): boolean {
    let cur = this.root
    for (const ch of prefix) {
      const find = cur.children.find((item) => item.val === ch)
      if (!find) return false
      cur = find
    }
    return true
  }
}

全排列

for + dfs 去寻找全部的可能, 从单个的字符出发去深度遍历全部的可能情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function permute(nums: number[]): number[][] {
  const ans: number[][] = []
  const dfs = (path: number[], perNums: number[]) => {
    if (path.length === nums.length) {
      ans.push(path)
    }
    for (let i = 0; i < perNums.length; i++) {
      // select i 的字符
      const pt = [...perNums]
      const t = pt.splice(i, 1)
      dfs([...path, t[0]], pt)
    }
  }
  dfs([], nums)
  return ans
}

子集

经典背包问题(? ) 考虑选择还是不选择当前 i 两种情况

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function subsets(nums: number[]): number[][] {
  const ans: number[][] = []
  const path: number[] = []
  const dfs = (i: number) => {
    if (i === nums.length) {
      ans.push(path.slice())
      return
    }
    dfs(i + 1)
    path.push(nums[i])
    dfs(i + 1)
    path.pop()
  }
  dfs(0)
  return ans
}

电话号码的字母组合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function letterCombinations(digits: string): string[] {
  const ans: string[] = []
  const teleMap = [
    '',
    '',
    'abc',
    'def',
    'ghi',
    'jkl',
    'mno',
    'pqrs',
    'tuv',
    'wxyz'
  ]
  const n = digits.length
  if (n === 0) return ans
  const path: string[] = Array(n).fill('')
  const dfs = (i: number) => {
    if (i === n) {
      ans.push(path.join(''))
      return
    }
    for (const ch of teleMap[digits[i]]) {
      path[i] = ch
      dfs(i + 1)
    }
  }
  dfs(0)
  return ans
}

组合总数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function combinationSum(candidates: number[], target: number): number[][] {
  candidates = candidates.sort((a, b) => a - b)
  const ans: number[][] = []
  const path: number[] = []
  const dfs = (i: number, needVal: number) => {
    if (needVal === 0) {
      ans.push(path.slice())
    }
    if (needVal < candidates[i]) return
    for (let j = i; j < candidates.length; j++) {
      path.push(candidates[j])
      dfs(j, needVal - candidates[j])
      path.pop()
    }
  }
  dfs(0, target)
  return ans
}

括号生成

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function generateParenthesis(n: number): string[] {
  const ans: string[] = []
  const m = 2 * n
  const path: string[] = new Array(m).fill('')
  const dfs = (i: number, open: number) => {
    if (i === m) {
      ans.push(path.join(''))
    }
    if (open < n) {
      path[i] = '('
      dfs(i + 1, open + 1)
    }
    if (i - open < open) {
      path[i] = ')'
      dfs(i + 1, open)
    }
  }
  dfs(0, 0)
  return ans
}

单词搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function exist(board: string[][], word: string): boolean {
  const m = board.length
  const n = board[0].length
  const xArr = [1, 0, -1, 0]
  const yArr = [0, 1, 0, -1]
  const dfs = (i: number, j: number, index: number): boolean => {
    if (board[i][j] !== word[index]) return false
    if (index === word.length - 1) return true
    let temp = board[i][j]
    board[i][j] = '*'
    for (let d = 0; d < 4; d++) {
      const [x, y] = [i + yArr[d], j + xArr[d]]
      if (x < 0 || x >= m || y < 0 || y >= n || board[x][y] === '*') continue
      if (dfs(x, y, index + 1)) return true
    }
    board[i][j] = temp
    return false
  }
  for (let i = 0; i < m; i++) {
    for (let j = 0; j < n; j++) {
      if (board[i][j] === word[0] && dfs(i, j, 0)) return true
    }
  }
  return false
}

搜索插入位置

不断二分找到最初的位置插入

1
2
3
4
5
6
7
8
9
10
11
function searchInsert(nums: number[], target: number): number {
  let l = 0,
    r = nums.length - 1
  if (nums[0] > target) return 0
  while (l <= r) {
    const mid = (l + r) >> 1
    if (nums[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return r + 1
}

搜索二维矩阵

二分 + 遍历

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const binarySearch = (arr: number[], target: number): boolean => {
  let l = 0,
    r = arr.length - 1
  while (l <= r) {
    const mid = (l + r) >> 1
    if (arr[mid] === target) return true
    else if (arr[mid] < target) l = mid + 1
    else r = mid - 1
  }
  return false
}
function searchMatrix(matrix: number[][], target: number): boolean {
  const n = matrix[0].length
  for (const nums of matrix) {
    if (nums[n - 1] < target) continue
    if (binarySearch(nums, target)) return true
  }
  return false
}

在排序数组中寻找第一个和最后一个位置

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function searchRange(nums: number[], target: number): number[] {
  let start = -1
  const ans: number[] = [start, start]
  let l = 0,
    r = nums.length - 1
  while (l <= r) {
    const mid = (l + r) >> 1
    if (nums[mid] === target) {
      start = mid
      r = mid - 1
    } else if (nums[mid] > target) r = mid - 1
    else l = mid + 1
  }
  if (start === -1) return ans
  ans[0] = start
  ans[1] = start
  for (let i = start + 1; i < nums.length; i++) {
    if (nums[i] !== nums[start]) break
    ans[1] = i
  }
  return ans
}

有效括号

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function isValid(s: string): boolean {
  const stack: string[] = []
  const stackMap = {
    '(': ')',
    '{': '}',
    '[': ']'
  }
  for (const ch of s) {
    if (stack.length && stackMap[stack[stack.length - 1]] === ch) {
      stack.pop()
    } else {
      stack.push(ch)
    }
  }
  return stack.length === 0
}

最小栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class MinStack {
  root: number[]
  min: number
  constructor() {
    this.root = []
    this.min = Infinity
  }

  push(val: number): void {
    this.root.push(val)
    if (val < this.min) {
      this.min = val
    }
  }

  pop(): void {
    this.root.pop()
    this.min = Math.min(...this.root)
  }

  top(): number {
    return this.root[this.root.length - 1]
  }

  getMin(): number {
    return this.min
  }
}

字符串解码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function decodeString(s: string): string {
  const stack: string[] = []
  for (const ch of s) {
    if (ch !== ']') {
      stack.push(ch)
    } else {
      let preChar = ''
      while (stack.length && stack[stack.length - 1] !== '[') {
        preChar = stack.pop() + preChar
      }
      stack.pop()
      let num = ''
      while (!isNaN(Number(stack[stack.length - 1]))) {
        num = stack.pop() + num
      }
      stack.push(preChar.repeat(Math.max(1, Number(num))))
    }
  }
  return stack.join('')
}

每日温度

在计算的过程中 维护一个单调栈既可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function dailyTemperatures(temperatures: number[]): number[] {
  const n = temperatures.length
  const ans: number[] = Array(n).fill(0)
  const stack: number[] = []
  for (let i = n - 1; i >= 0; i--) {
    const t = temperatures[i]
    while (stack.length && temperatures[stack[stack.length - 1]] <= t) {
      stack.pop()
    }
    if (stack.length) {
      ans[i] = stack[stack.length - 1] - i
    }
    stack.push(i)
  }
  return ans
}

买股票最佳时间

不断的更新最大值和最小值

1
2
3
4
5
6
7
8
9
function maxProfit(prices: number[]): number {
  let maxPrice = 0
  let minPrice = prices[0]
  for (const price of prices) {
    minPrice = Math.min(price, minPrice)
    maxPrice = Math.max(price - minPrice, maxPrice)
  }
  return maxPrice
}

跳跃游戏

维护一个最大的跳远变量去循环数组一一比较, 更新

1
2
3
4
5
6
7
8
function canJump(nums: number[]): boolean {
  let maxJumpStep = 0
  for (let i = 0; i < nums.length; i++) {
    if (maxJumpStep < i) return false
    maxJumpStep = Math.max(maxJumpStep, nums[i] + i)
  }
  return true
}
1
2
3
4
5
6
7
8
9
10
// 维护一个最大的[dp] 找出满足的j去构建i
function jump(nums: number[]): number {
  const n = nums.length
  const dp: number[] = Array(n).fill(0)
  for (let i = 1, j = 0; i < n; i++) {
    while (nums[j] + j < i) j++
    dp[i] = dp[j] + 1
  }
  return dp[n - 1]
}

划分字母区间

找出最大的 index 去遍历逐一比较

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function partitionLabels(s: string): number[] {
  const ans: number[] = []
  const recordLastIndex: Record<string, number> = {}
  for (let i = 0; i < s.length; i++) {
    recordLastIndex[s[i]] = i
  }
  let l = 0,
    r = 0
  for (let i = 0; i < s.length; i++) {
    r = Math.max(r, recordLastIndex[s[i]])
    if (r === i) {
      ans.push(r - l + 1)
      l = r + 1
    }
  }
  return ans
}

爬楼梯

1
2
3
4
5
6
7
8
9
10
function climbStairs(n: number): number {
  const dp = Array(n + 1).fill(0)
  dp[0] = 0
  dp[1] = 1
  dp[2] = 2
  for (let i = 3; i <= n; i++) {
    dp[i] = dp[i - 2] + dp[i - 1]
  }
  return dp[n]
}

杨辉三角

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function generate(numRows: number): number[][] {
  const ans: number[][] = []
  const dp = new Array(numRows).fill([])
  dp[0] = [1]
  dp[1] = [1, 1]
  for (let i = 2; i < numRows; i++) {
    dp[i] = []
    dp[i].push(1)
    for (let j = 1; j < i; j++) {
      dp[i].push(dp[i - 1][j - 1] + dp[i - 1][j])
    }
    dp[i].push(1)
  }
  for (let i = 0; i < numRows; i++) {
    ans.push(dp[i])
  }
  return ans
}

打家劫舍

1
2
3
4
5
6
7
8
function rob(nums: number[]): number {
  const n = nums.length
  const dp: number[] = Array(n + 2).fill(0)
  for (let i = 0; i < n; i++) {
    dp[i + 2] = Math.max(dp[i + 1], dp[i] + nums[i])
  }
  return dp[n + 1]
}

完全平方数

1
2
3
4
5
6
7
8
9
10
11
function numSquares(n: number): number {
  const dp = Array(n + 1)
    .fill(0)
    .map((item, index) => index)
  for (let i = 1; i <= n; i++) {
    for (let j = 1; j * j <= i; j++) {
      dp[i] = Math.min(dp[i], dp[i - j * j] + 1)
    }
  }
  return dp[n]
}

零钱兑换

1
2
3
4
5
6
7
8
9
10
11
12
function coinChange(coins: number[], amount: number): number {
  const dp: number[] = Array(amount + 1).fill(amount + 1)
  dp[0] = 0
  for (let i = 0; i <= amount; i++) {
    for (let j = 0; j < coins.length; j++) {
      if (coins[j] <= i) {
        dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1)
      }
    }
  }
  return dp[amount] > amount ? -1 : dp[amount]
}

单词拆分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function wordBreak(s: string, wordDict: string[]): boolean {
  const dictSet = new Set<string>(wordDict)
  const dp = Array(s.length + 1).fill(false)
  dp[0] = true
  for (let i = 0; i <= s.length; i++) {
    for (let j = 0; j < i; j++) {
      if (dp[j] && dictSet.has(s.slice(j, i))) {
        dp[i] = true
        break
      }
    }
  }
  return dp[s.length]
}

最长递增子序列

1
2
3
4
5
6
7
8
9
10
11
12
function lengthOfLIS(nums: number[]): number {
  const n = nums.length
  const dp: number[] = Array(n).fill(1)
  for (let i = 1; 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)
}

乘积最大子数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function maxProduct(nums: number[]): number {
  let max = nums[0]
  let min = nums[0]
  let maxmax = nums[0]
  for (let i = 1; i < nums.length; i++) {
    if (nums[i] < 0) {
      ;[max, min] = [min, max]
    }
    max = Math.max(nums[i], max * nums[i])
    min = Math.min(nums[i], min * nums[i])
    maxmax = Math.max(max, maxmax)
  }
  return maxmax
}

不同路径

1
2
3
4
5
6
7
8
9
function uniquePaths(m: number, n: number): number {
  const dp: number[][] = Array.from({ length: m }, () => Array(n).fill(1))
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
    }
  }
  return dp[m - 1][n - 1]
}

最小路径和

1
2
3
4
5
6
7
8
9
10
11
12
13
function minPathSum(grid: number[][]): number {
  const m = grid.length,
    n = grid[0].length
  // init
  for (let i = 1; i < m; i++) grid[i][0] = grid[i][0] + grid[i - 1][0]
  for (let j = 1; j < n; j++) grid[0][j] = grid[0][j] + grid[0][j - 1]
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      grid[i][j] = Math.min(grid[i - 1][j], grid[i][j - 1]) + grid[i][j]
    }
  }
  return grid[m - 1][n - 1]
}

最长回文子串

遍历 + 左右指针找出 max

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function longestPalindrome(s: string): string {
  let max = 0
  let start = -1
  for (let i = 0; i < s.length; i++) {
    let now = 1
    let l = i - 1
    while (s[i + 1] === s[i]) {
      now++
      i++
    }
    let r = i + 1
    while (s[l] && s[r] && s[l] === s[r]) {
      l--
      r++
      now += 2
    }
    if (now > max) {
      max = now
      start = l + 1
    }
  }
  return s.slice(start, start + max)
}

只出现一次的数字

利用技巧 ^ 相同的数字为 0 0 与任何数相^ 等于任何数

1
2
3
4
5
6
7
function singleNumber(nums: number[]): number {
  let ans = 0
  for (const num of nums) {
    ans ^= num
  }
  return ans
}

多数元素

1
2
3
4
5
6
7
8
9
10
11
function majorityElement(nums: number[]): number {
  let count = 0
  let candiate = nums[0]
  for (const num of nums) {
    if (count === 0) {
      candiate = num
    }
    count += num === candiate ? 1 : -1
  }
  return candiate
}

颜色分类

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function sortColors(nums: number[]): void {
  let l = 0,
    r = nums.length - 1,
    index = 0
  while (index <= r) {
    if (nums[index] === 0) {
      ;[nums[l], nums[index]] = [nums[index], nums[l]]
      l++
      index++
    } else if (nums[index] === 1) {
      index++
    } else {
      ;[nums[index], nums[r]] = [nums[r], nums[index]]
      r--
    }
  }
}

下一个排列

找出下降点 || 交换下降点和第一个大于他的数字 || 升序下降点之后的序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function nextPermutation(nums: number[]): void {
  let descrNum = nums.length - 1
  // 找到下降点
  while (descrNum > 0 && nums[descrNum - 1] >= nums[descrNum]) descrNum--
  // 找到需要交换的元素
  descrNum--
  if (descrNum >= 0) {
    let exChangeNum = nums.length - 1
    while (nums[exChangeNum] <= nums[descrNum]) exChangeNum--
    ;[nums[descrNum], nums[exChangeNum]] = [nums[exChangeNum], nums[descrNum]]
  }
  // 排序下降点之后的元素, 构成更小的排列
  let r = nums.length - 1
  descrNum++
  while (descrNum < r) {
    ;[nums[descrNum++], nums[r--]] = [nums[r], nums[descrNum]]
  }
}

寻找重复数

1
2
3
4
5
6
7
8
function findDuplicate(nums: number[]): number {
  const hashSet = new Set<number>()
  for (const num of nums) {
    if (hashSet.has(num)) return num
    hashSet.add(num)
  }
  return -1
}