剑指offer 解题报告

前言
¶

这两天奶奶做手术，我在医院里陪护，奶奶不会说普通话所以只好一直陪在旁边。实在有些闲得慌，正好在刷知乎的时候看到了《剑指offer》的推荐，搜了下发现有 OJ 收录了原书中的题目，于是开始尝试手机写代码23333（没有带电脑）。强迫症晚期，一上手就非要做完不可，还好题目量少。使用低效率的方式做一件并不紧要的事情实在是太浪费生命了。（不过也有人说，生命就是用来浪费的2333

为了偷懒节约篇幅，将过于基础的题放在了附录中。

01 二维数组的查找
¶

题目链接

题意简述
¶

有一个 $R \times C$ 的矩阵，每行从左至右数值递增，每列从上至下数值递增，求矩阵中是否包含给定的数值。

题目简析
¶

注意到矩阵中任意一个子矩阵仍然满足此特性，则可以二分子矩阵，直到子矩阵的大小为 $1 \times 1$ . 具体地，若当前所检查的子矩阵为 $(l_{1}, r_{1}, l_{2}, r_{2})$ ，取位置 $(x = ⌊ \frac{l_{1} + l_{2}}{2} ⌋, y = ⌊ \frac{r_{1} + r_{2}}{2} ⌋)$ ，则：

若目标值恰好等于此位置上的值，则直接返回 true；
否则，若目标值小于此位置上的值，则其只可能存在于子矩阵 $(l_{1}, x, l_{2}, y)$ 中；
否则，其只可能存在于子矩阵 $(x + 1, r_{1}, l_{2}, r_{2})$ 或子矩阵 $(l_{1}, r_{1}, y + 1, r_{2})$ 中

程序实现
¶

时间复杂度： $O (\log R \times \log C)$
额外空间复杂度： $O (\log R \times \log C)$

01.ts | 22 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
export function Find(target: number, array: number[][]): boolean {
  if (array.length <= 0) return false
  if (array[0].length <= 0) return false

  const R = array.length
  const C = array[0].length
  return search(0, R, 0, C)

  function search(lft1: number, rht1: number, lft2: number, rht2: number): boolean {
    if (lft1 >= R || lft2 >= C) return false
    if (lft1 > rht1 || lft2 > rht2) return false
    if (lft1 === rht1 && lft2 === rht2) return false

    const x = (lft1 + rht1) >> 1
    const y = (lft2 + rht2) >> 1
    const z = array[x][y]

    if (target === z) return true
    if (target < z) return search(lft1, x, lft2, y)
    return search(x + 1, rht1, lft2, rht2) || search(lft1, rht1, y + 1, rht2)
  }
}

04 重建二叉树
¶

题目链接

题目简述
¶

给定一棵 $N$ 个节点的二叉树的先序遍历和中序遍历结果，重建二叉树。

题目简析
¶

先序遍历的第一个节点为根节点，不妨记为 $x$ ，找到中序遍历中 $x$ 的位置，不妨记为 $p$ ，则中序遍历序列中：

$p$ 之前所有的节点都为 $x$ 的左子树中的节点；
而 $p$ 之后的所有节点都为 $x$ 的右子树的节点；

又因为无论先序遍历还是后序遍历都是先访问完左子树再访问右子树的，所以先序遍历序列中前 $p$ 个元素同样是 $x$ 的左子树中的节点，之后递归处理即可。

程序实现
¶

时间复杂度： $O (N)$
额外空间复杂度： $O (N)$

04.ts | 26 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function reConstructBinaryTree(pre: number[], vin: number[]): TreeNode {
  if (pre.length === 0 || pre.length !== vin.length) return null
  const tree = build(0, pre.length - 1, 0, vin.length - 1)
  return tree

  function build(lft1: number, rht1: number, lft2: number, rht2: number): TreeNode {
    const x = pre[lft1]

    // 找到
    let p = lft2
    for (; p <= rht2; ++p) if (vin[p] === x) break

    const o: TreeNode = {
      val: x,
      left: lft2 < p ? build(lft1 + 1, lft1 + p - lft2, lft2, p - 1) : null,
      right: rht2 > p ? build(lft1 + p - lft2 + 1, rht1, p + 1, rht2) : null,
    }
    return o
  }
}

06 旋转数组的最小数字
¶

题目链接

题目简述
¶

有一个长度为 $N$ 的非严格递增序列 $A = {a_{1}, a_{2}, \dots, a_{N}}$ ，将其前面 $K$ 个（ $0 ⩽ K < N$ ）个元素取出并按顺序放在原序列的末尾，得到新序列

B = {b_{1}, b_{2}, \dots, b_{N}} = {a_{K + 1}, a_{K + 2}, \dots, a_{N}, a_{1}, a_{2}, \dots, a_{K}}

求 $B$ 中的最小值。

题目简析
¶

先考虑简化版问题。若原数列严格递增，则存在两种情况：

$b_{1} < b_{N}$ ，即 $B$ 单调递增，此时 $b_{1}$ 即为所求答案
$b_{1} > b_{N}$ ，即 $B$ 先上升后突降再上升，取 $x = ⌊ \frac{1 + N}{2} ⌋$
- 若 $b_{x} < b_{N}$ ，则答案落在 ${b_{1}, b_{2}, \dots b_{x}}$ 中
- 否则，即 $b_{x} > b_{N}$ ，则答案落在 ${b_{x + 1}, b_{x + 2}, \dots, c_{N}}$ 中

原问题在简化版问题基础上的第二种情况种多了一种可能： $b_{1} = b_{N}$ 。此时取 $x = N - 1$ 即可。

程序实现
¶

时间复杂度： $O (\log N)$ （极端情况下可退化为 $O (N)$ ）
额外空间复杂度： $O (1)$

06.ts | 24 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
export function minNumberInRotateArray(rotateArray: number[]): number {
  const A: number[] = rotateArray
  if (A.length <= 0) return 0

  let lft = 0
  let rht = A.length
  while (lft < rht) {
    const last: number = A[rht - 1]
    if (lft + 1 === rht || last > A[lft]) return A[lft]

    const mid: number = (lft + rht) >> 1
    const x: number = A[mid]
    if (mid + 1 === rht || x < last) {
      // 因为前面已经判断过区间首元素和尾元素，所以此时
      // mid 不可能和 lft 相等
      if (x < A[mid - 1]) return x

      rht = mid
    } else if (x === last) rht -= 1
    // 复杂度退化的情况
    else lft = mid + 1
  }
  return A[rht - 1]
}

23 二叉搜索树的后序遍历序列
¶

题目链接

题目描述
¶

判断给定的数组 $A = {a_{1}, a_{2}, \dots, a_{N}}$ 是否为一棵二叉搜索树的后序遍历结果。

题目简析
¶

后续遍历中，最后一个元素为根节点，这启发我们逆序遍历 $A$ 进行判断。又因为原数组是一棵二叉搜索的遍历结果，即右子树的最小值总比左子树及根节点值都要大，事实上我们仅检验这一点就可以判断给定数组是否为某棵二叉搜索树的后序遍历结果了。

算法的核心思想是沿着树中最右侧的链遍历（访问过的节点可标记为删除）的方式去遍历整棵树，则每次要进入一个左子树时，里面元素的值不得超过当前遍最右侧链的最大值，否则其不为一个有效的二叉搜索树后序遍历结果。树上的最右侧链可以使用一个栈进行维护，不难发现其是一个严格递增的单调栈。每当树上某个节点的右子树访问完后，将其在栈中对应的元素从栈中移除，不难发现，移除操作总是弹出栈顶元素。

程序实现
¶

时间复杂度： $O (N)$
额外空间复杂度： $O (N)$

23.ts | 21 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
export function VerifySquenceOfBST(sequence: number[]): boolean {
  if (sequence.length <= 0) return false

  const stack: number[] = []
  let maxOfTree: number = Number.MAX_SAFE_INTEGER
  for (let i = sequence.length - 1; i > -1; --i) {
    const x = sequence[i]
    if (x >= maxOfTree) return false

    // 栈顶元素为树中最大的节点，当遇到一个比栈顶元素小的节点时，
    // 说明此后不应该再遇到比栈顶元素大的元素(因为是后续遍历的逆序，
    // 所以我们会先访问完右子树再访问左子树)，同时可以将栈中所以大于
    // 它的元素一并删除(所以这还是个单调栈)。
    while (stack.length > 0 && x < stack[stack.length - 1]) {
      maxOfTree = stack.pop()
    }

    stack.push(x)
  }
  return true
}

附录
¶

#02 替换空格：字符串替换

02.ts | 3 lines.

1
2
3
export function replaceSpace(text: string): string {
  return text.replace(/[ ]/, '%20')
}

#03 从尾到头打印链表：栈的应用

03.ts | 15 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
interface ListNode {
  val: number
  next: ListNode | null
}

const stack: number[] = []

export function printListFromTailToHead(head: ListNode): number[] {
  let tot = 0
  for (let o: ListNode = head; o; o = o.next) stack[tot++] = o.val

  const result: number[] = new Array(tot)
  for (let i = 0; tot--; ++i) result[i] = stack[tot]
  return result
}

#05 用两个栈实现队列：栈和队列的应用

05.ts | 16 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
const s1: number[] = []
const s2: number[] = []

export function push(node: number): void {
  s1.push(node)
}

export function pop(): number | undefined {
  // 如果 s2 为空，则将栈 s1 中的内容弹出并压入栈 s2 中
  if (s2.length <= 0) {
    while (s1.length > 0) s2.push(s1.pop()!)
  }

  // 从 s2 中弹栈的值遵循原序列的先入先出规则
  return s2.pop()
}

#07 斐波那契数列：递推

f (n) = {\begin{aligned} 0, & n ⩽ 0 \\ 1, & n = 1 \\ 1, & n = 2 \\ f (n - 1) + f (n - 2), & n ⩾ 3 \end{aligned}

07.ts | 13 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
export function Fibonacci(n: number): number {
  if (n <= 1) return n

  let a = 0
  let b = 1
  let c = 1
  for (let i = 3; i <= n; ++i) {
    a = b
    b = c
    c = a + b
  }
  return c
}

#08 跳台阶：递推

f (n) = {\begin{aligned} 0, & n ⩽ 0 \\ 1, & n = 1 \\ 2, & n = 2 \\ f (n - 1) + f (n - 2), & n ⩾ 3 \end{aligned}

08.ts | 14 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
export function jumpFloor(n: number): number {
  if (n <= 0) return 0
  if (n <= 2) return n

  let a = 1
  let b = 2
  let c = 3
  for (let i = 3; i < n; ++i) {
    a = b
    b = c
    c = a + b
  }
  return c
}

#09 跳台阶扩展问题：递推

f (n) = {\begin{aligned} 0, & n ⩽ 0 \\ 2^{n - 1}, & n > 0 \end{aligned}

09.ts | 4 lines.

1
2
3
4
export function jumpFloorII(n: number): number {
  if (n <= 0) return 0
  return 1 << (n - 1)
}

#10 跳台阶扩展问题：递推

f (n) = {\begin{aligned} 0, & n ⩽ 0 \\ 1, & n = 1 \\ 2, & n = 2 \\ f (n - 1) + f (n - 2), & n ⩾ 3 \end{aligned}

10.ts | 14 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
export function rectCover(n: number): number {
  if (n <= 0) return 0
  if (n <= 2) return n

  let a = 1
  let b = 2
  let c = 3
  for (let i = 3; i < n; ++i) {
    a = b
    b = c
    c = a + b
  }
  return c
}

#11 二进制中 1 的个数：数学，二进制

11.ts | 25 lines.

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
// 循环判断
export function NumberOf1(n: number): number {
  let result = 0
  for (n; n; n >>>= 1) {
    if (n & 1) result += 1
  }
  return result
}

// 使用 lowbit
export function NumberOf1_2(n: number): number {
  let result = 0
  for (n; n; n ^= n & -n) result += 1
  return result
}

// 使用偏移累加
export function NumberOf1_3(n: number): number {
  let x = (n & 0x55555555) + ((n >> 1) & 0x55555555)
  x = (x & 0x33333333) + ((x >> 2) & 0x33333333)
  x = (x & 0x0f0f0f0f) + ((x >> 4) & 0x0f0f0f0f)
  x = (x & 0x00ff00ff) + ((x >> 8) & 0x00ff00ff)
  x = (x & 0x0000ffff) + ((x >> 16) & 0x0000ffff)
  return x
}

#12 数值的整数次方：数学，快速幂

12.ts | 10 lines.

1
2
3
4
5
6
7
8
9
10
export function Power(base: number, exponent: number): number {
  if (base === 0) return 0

  let n = Math.abs(exponent)
  let result = 1
  for (let x = base; n > 0; n >>= 1, x = x * x) {
    if (n & 1) result *= x
  }
  return exponent < 0 ? 1 / result : result
}

#13 调整数组顺序使奇数位于偶数前面：数学，二进制

13.ts | 9 lines.

1
2
3
4
5
6
7
8
9
export function reOrderArray(nums: number[]): number[] {
  const A: number[] = []
  const B: number[] = []
  for (const x of nums) {
    if (x & 1) A.push(x)
    else B.push(x)
  }
  return A.concat(B)
}

#14 链表中倒数最后K个节点：链表，双指针

14.ts | 22 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
interface ListNode {
  val: number
  next: ListNode | null
}

export function FindKthToTail(pHead: ListNode, k: number): ListNode | null {
  let faster: ListNode | null = pHead
  let slower: ListNode = pHead

  // 快指针先走 k 步
  for (let step = 0; step < k; ++step) {
    if (faster == null) return null
    faster = faster.next
  }

  // 两个指针一起走
  while (faster != null) {
    faster = faster.next
    slower = slower.next!
  }
  return slower
}

#15 反转链表：链表

15.ts | 19 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
interface ListNode {
  val: number
  next: ListNode | null
}

export function ReverseList(pHead: ListNode): ListNode {
  if (pHead == null) return null

  let x: ListNode | null = pHead
  let y: ListNode | null = pHead.next
  while (y != null) {
    const z = y.next
    y.next = x
    x = y
    y = z
  }
  pHead.next = null
  return x
}

#16 合并两个排序的链表：归并排序

16.ts | 28 lines.

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
interface ListNode {
  val: number
  next: ListNode | null
}

export function Merge(pHead1: ListNode, pHead2: ListNode): ListNode {
  const fakeRoot: ListNode = {
    val: -1,
    next: null,
  }

  let x: ListNode = pHead1
  let y: ListNode = pHead2
  let z: ListNode = fakeRoot
  for (; x != null && y != null; z = z.next) {
    if (x.val < y.val) {
      z.next = x
      x = x.next
    } else {
      z.next = y
      y = y.next
    }
  }

  if (x != null) z.next = x
  if (y != null) z.next = y
  return fakeRoot.next
}

#17 树的子结构：二叉树，递归

17.ts | 25 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function HasSubtree(pRoot1: TreeNode, pRoot2: TreeNode): boolean {
  if (pRoot1 == null || pRoot2 == null) return false
  if (isSubTree(pRoot1, pRoot2)) return true
  if (pRoot1.left != null && HasSubtree(pRoot1.left, pRoot2)) return true
  if (pRoot1.right != null && HasSubtree(pRoot1.right, pRoot2)) return true
  return false
}

// 检查 v 是否为 u 的子树，且它们根节点相同
function isSubTree(u: TreeNode, v: TreeNode): boolean {
  if (u.val !== v.val) return false
  if (v.left != null) {
    if (u.left == null || !isSubTree(u.left, v.left)) return false
  }
  if (v.right != null) {
    if (u.right == null || !isSubTree(u.right, v.right)) return false
  }
  return true
}

#18 二叉树的镜像：二叉树，递归

18.ts | 15 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function Mirror(pRoot: TreeNode): TreeNode {
  if (pRoot == null) return null
  const x = pRoot.left
  pRoot.left = pRoot.right
  pRoot.right = x
  Mirror(pRoot.left)
  Mirror(pRoot.right)
  return pRoot
}

#19 顺时针打印矩阵：模拟

19.ts | 49 lines.

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
export function printMatrix(matrix: number[][]): number[] {
  if (matrix.length <= 0) return []
  if (matrix[0].length <= 0) return []

  const R = matrix.length
  const C = matrix[0].length

  const result: number[] = []
  const totalRound = Math.min(R, C) >> 1
  for (let round = 0; round < totalRound; ++round) {
    right(round, round, C - round)
    down(C - round - 1, round + 1, R - round)
    left(R - round - 1, C - round - 2, round - 1)
    up(round, R - round - 2, round)
  }

  if (Math.min(R, C) & 1) {
    if (C > R) {
      right(totalRound, totalRound, C - totalRound)
    } else {
      down(totalRound, totalRound, R - totalRound)
    }
  }
  return result

  function right(row: number, x: number, y: number): void {
    for (let i = x; i < y; ++i) {
      result.push(matrix[row][i])
    }
  }

  function down(col: number, x: number, y: number): void {
    for (let i = x; i < y; ++i) {
      result.push(matrix[i][col])
    }
  }

  function left(row: number, x: number, y: number): void {
    for (let i = x; i > y; --i) {
      result.push(matrix[row][i])
    }
  }

  function up(col: number, x: number, y: number): void {
    for (let i = x; i > y; --i) {
      result.push(matrix[i][col])
    }
  }
}

#20 包含min函数的栈：单调栈

20.ts | 27 lines.

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
const nums: number[] = [] // 普通栈
const stack: number[] = [] // 单调栈

export function push(node: number): void {
  nums.push(node)

  // 允许放入和栈顶元素相等的元素是为了避免在弹出元素时做特判
  if (stack.length <= 0 || stack[stack.length - 1] >= node) {
    stack.push(node)
  }
}

export function pop(): void {
  const x = nums.pop()

  // 单调栈中栈顶元素最小，如果 nums 弹出的元素和单调栈中的栈顶元素相同，
  // 则单调栈中也同时弹出元素
  if (x != null && x === min()) stack.pop()
}

export function top(): number | undefined {
  return nums.length > 0 ? nums[nums.length - 1] : undefined
}

export function min(): number {
  return stack[stack.length - 1]
}

#21 栈的压入、弹出序列：栈，模拟

根据 push 序列按顺序进行压栈，每次压完栈后根据 pop 序列检查是否要弹栈

21.ts | 17 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
export function IsPopOrder(pushV: number[], popV: number[]): boolean {
  const stack: number[] = []
  let i = 0
  let j = 0
  for (const x of pushV) {
    const y = popV[j]
    if (x === y) j += 1
    else stack[i++] = x

    while (i > 0) {
      if (stack[i - 1] !== popV[j]) break
      i -= 1
      j += 1
    }
  }
  return i === 0
}

#22 从上往下打印二叉树：二叉树，BFS

22.ts | 19 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function PrintFromTopToBottom(root: TreeNode): number[] {
  if (root == null) return []
  const Q: TreeNode[] = []
  const result: number[] = []
  Q.push(root)
  while (Q.length > 0) {
    const x = Q.shift()
    result.push(x.val)
    if (x.left) Q.push(x.left)
    if (x.right) Q.push(x.right)
  }
  return result
}

#24 二叉树中和为某一值的路径：二叉树，DFS

24.ts | 28 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function FindPath(root: TreeNode, target: number): number[][] {
  if (root == null) return []
  const results: number[][] = []
  const tmp: number[] = []
  let total = 0
  f(root, 0)
  return results

  function f(o: TreeNode, cur: number): void {
    tmp[cur] = o.val
    total += o.val
    if (o.left == null && o.right == null) {
      if (total === target) {
        results.push(tmp.slice(0, cur + 1))
      }
    } else {
      if (o.left != null) f(o.left, cur + 1)
      if (o.right != null) f(o.right, cur + 1)
    }
    total -= o.val
  }
}

#25 复杂链表的复制：链表，哈希表、Map

25.ts | 30 lines.

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
interface RandomListNode {
  label: number
  next: RandomListNode | null
  random: RandomListNode | null
}

export function Clone(o: RandomListNode): RandomListNode {
  const map = new Map()
  const root = { ...o }
  for (
    let u: RandomListNode = root, v: RandomListNode = root;
    v != null;
    u = u.next!, v = v.next!
  ) {
    map.set(v, u)
    if (v.next != null) {
      const w = map.get(v.next)
      if (w != null) {
        u.next = w
        break
      }
      u.next = { ...v.next }
    }
  }
  for (let u = root; u != null; u = u.next!) {
    const r = map.get(u.random)
    u.random = r === undefined ? null : r
  }
  return root
}

#26 二叉搜索树与双向链表：二叉树，中序遍历

26.ts | 25 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function Convert(pRootOfTree: TreeNode): TreeNode {
  if (pRootOfTree == null) return null

  f(null, pRootOfTree)
  let root = pRootOfTree
  while (root.left != null) root = root.left
  return root
}

function f(p: TreeNode, o: TreeNode): TreeNode {
  if (o.left) p = f(p, o.left)

  if (p != null) p.right = o
  o.left = p
  p = o

  if (o.right) p = f(p, o.right)
  return p
}

#27 字符串的排列：全排列

27.ts | 35 lines.

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
export function Permutation(str: string): string[] {
  if (str == null || str.length <= 0) return []
  const letters: string[] = str.split('').sort()
  const answers: string[] = []
  const _end = letters.length - 1

  while (true) {
    answers.push(letters.join(''))

    // 从右往左扫描找到第一个相邻且逆序的元素对 (i - 1, i)
    // 将第 i-1 个元素和最后一个元素交换，然后将 [i, N] 中的元素反转顺序

    let i = _end
    for (; i > 0; --i) {
      if (letters[i] > letters[i - 1]) break
    }

    // 若不存在这样的 i，则结束循环
    if (i <= 0) break

    let x = letters[i - 1]
    let k = _end
    for (; k >= i; --k) if (letters[k] > x) break
    letters[i - 1] = letters[k]
    letters[k] = x
    const L = i + _end
    const mid = L >> 1
    for (let j = i; j <= mid; ++j) {
      x = letters[j]
      letters[j] = letters[L - j]
      letters[L - j] = x
    }
  }
  return answers
}

#28 数组中出现次数超过一半的数字：中位数，随机测试，找第 $k$ 大数

排序

28.ts | 10 lines.

1
2
3
4
5
6
7
8
9
10
/**
 * 排序并返回中位数
 *
 * 时间复杂度： O(N \log N)
 * 额外空间复杂度： O(N)
 */
export function MoreThanHalfNum_Solution(nums: number[]): number {
  nums.sort((x, y) => x - y)
  return nums[nums.length >> 1]
}

随机测试

28_2.ts | 20 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/**
 * 随机测试
 *
 * 时间复杂度： O(N \log N)
 * 额外空间复杂度： O(1)
 */
export function MoreThanHalfNum_Solution_2(nums: number[]): number {
  let last: number = Number.NaN

  while (true) {
    const current = nums[Math.floor(Math.random() * nums.length)]

    if (last === current) continue
    last = current

    let cnt = 0
    for (const x of nums) if (x === current) cnt += 1
    if (cnt * 2 >= nums.length) return current
  }
}

找第 $k$ 大的数

28_3.ts | 46 lines.

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
/**
 * 快排思想找数组中第 k 大元素
 *
 * 时间复杂度： O(N)
 * 额外空间复杂度： O(log N)
 */
export function MoreThanHalfNum_Solution_3(nums: number[]): number {
  return kth(0, nums.length - 1, (nums.length + 1) >> 1)

  function kth(lft: number, rht: number, k: number): number {
    if (lft === rht) return nums[lft]

    // 选取一个随机值防止极端数据下的复杂度退化
    const x = lft + 7 <= rht ? lft + Math.floor((rht - lft) * Math.random()) : (lft + rht) >> 1
    const pivot = nums[x]
    nums[x] = nums[lft]

    let i = lft
    let j = rht + 1
    while (i < j) {
      for (j -= 1; i < j && nums[j] >= pivot; ) --j
      if (i === j) break
      nums[i] = nums[j]

      for (i += 1; i < j && nums[i] <= pivot; ) ++i
      if (i === j) break
      nums[j] = nums[i]
    }
    nums[i] = pivot

    // 优化，中间元素的边界尽可能延申，否则复杂度可能退化为 O(N^2)
    for (i -= 1; i >= lft; --i) if (nums[i] !== pivot) break
    for (j += 1; j <= rht; ++j) if (nums[j] !== pivot) break

    // 先检查左边的元素个数是否大于或等于 k 个
    let k2 = k - (i + 1 - lft)
    if (k2 <= 0) return kth(lft, i, k)

    // 再判断左边的元素个数+中间元素个数是否大于等于 k 个
    k2 -= j - i - 1
    if (k2 <= 0) return pivot

    // 否则，目标值再右边的元素列表中
    return kth(j, rht, k2)
  }
}

#29 最小的K个数：排序，小根堆，找第 $k$ 的数

小根堆

29.ts | 98 lines.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/**
 * 大根堆
 *
 * 时间复杂度： O(N \log N)
 * 额外空间复杂度： O(N)
 */
export function GetLeastNumbers_Solution(nums: number[], _k: number): number[] {
  if (_k <= 0) return []
  if (_k >= nums.length) return nums

  const Q: PriorityQueue<number> = createPriorityQueue<number>((x, y) => y - x)
  for (let i = 0; i < _k; ++i) Q.enqueue(nums[i])
  for (let i = _k; i < nums.length; ++i) {
    const x = nums[i]
    if (Q.top() <= x) continue
    Q.dequeue()
    Q.enqueue(x)
  }

  return Q.collect()
}

interface PriorityQueue<T> {
  enqueue: (val: T) => void
  dequeue: () => T | undefined
  collect: () => T[]
  top: () => T | undefined
  size: () => number
  isEmpty: () => boolean
}

// 优先队列
function createPriorityQueue<T>(cmp: (x: T, y: T) => -1 | 0 | 1 | number): PriorityQueue<T> {
  const _tree: T[] = [null]
  let _size: number = 0

  function enqueue(val: T): void {
    _tree[++_size] = val
    _up(_size)
  }

  function dequeue(): T | undefined {
    if (_size < 1) return undefined

    const target = _tree[1]
    _tree[1] = _tree[_size--]
    _down(1)

    return target
  }

  function top(): T | undefined {
    return _size > 0 ? _tree[1] : undefined
  }

  function collect(): T[] {
    return _tree.slice(1)
  }

  function _down(index: number): void {
    for (let i = index; i <= _size; ) {
      const lft = i << 1
      const rht = lft | 1
      if (lft > _size) break

      let q = lft
      if (rht <= _size && cmp(_tree[rht], _tree[q]) < 0) q += 1

      const x = _tree[q]
      if (cmp(_tree[i], x) <= 0) break

      _tree[q] = _tree[i]
      _tree[i] = x
      i = q
    }
  }

  function _up(index: number): void {
    for (let i = index; i > 1; ) {
      const q = i >> 1
      const x = _tree[q]
      if (cmp(x, _tree[i]) <= 0) break

      _tree[q] = _tree[i]
      _tree[i] = x
      i = q
    }
  }

  return {
    enqueue,
    dequeue,
    top,
    collect,
    size: () => _size,
    isEmpty: () => _size < 1,
  }
}

找第 $k$ 大的数

29_1.ts | 50 lines.

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
/**
 * 快排思想找数组中第 k 大元素
 *
 * 时间复杂度： O(N)
 * 额外空间复杂度： O(log N)
 */
export function GetLeastNumbers_Solution(nums: number[], _k: number): number[] {
  if (_k <= 0) return []
  if (_k >= nums.length) return nums

  kth(0, nums.length - 1, _k)
  return nums.slice(0, _k)

  function kth(lft: number, rht: number, k: number): number {
    if (lft === rht) return nums[lft]

    // 选取一个随机值防止极端数据下的复杂度退化
    const x = lft + 7 <= rht ? lft + Math.floor((rht - lft) * Math.random()) : (lft + rht) >> 1
    const pivot = nums[x]
    nums[x] = nums[lft]

    let i = lft
    let j = rht + 1
    while (i < j) {
      for (j -= 1; i < j && nums[j] >= pivot; ) --j
      if (i === j) break
      nums[i] = nums[j]

      for (i += 1; i < j && nums[i] <= pivot; ) ++i
      if (i === j) break
      nums[j] = nums[i]
    }
    nums[i] = pivot

    // 优化，中间元素的边界尽可能延申，否则复杂度可能退化为 O(N^2)
    for (i -= 1; i >= lft; --i) if (nums[i] !== pivot) break
    for (j += 1; j <= rht; ++j) if (nums[j] !== pivot) break

    // 先检查左边的元素个数是否大于或等于 k 个
    let k2 = k - (i + 1 - lft)
    if (k2 <= 0) return kth(lft, i, k)

    // 再判断左边的元素个数+中间元素个数是否大于等于 k 个
    k2 -= j - i - 1
    if (k2 <= 0) return pivot

    // 否则，目标值再右边的元素列表中
    return kth(j, rht, k2)
  }
}

#30 连续子数组的最大和：前缀和

30.ts | 13 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
export function FindGreatestSumOfSubArray(nums: number[]): number {
  if (nums.length <= 0) return 0

  let answer = nums[0]
  let x = 0
  let y = nums[0]
  for (let i = 1; i < nums.length; ++i) {
    x = Math.min(x, y)
    y += nums[i]
    if (y - x > answer) answer = y - x
  }
  return answer
}

#31 整数中 $1$ 出现的次数（从 $1$ 到 $n$ 整数中1出现的次数）：数学，排列组合

因为十进制数位中每个位置上 $1$ 的贡献度是彼此独立的，所以依次枚举每个位置，计算该位置为 $1$ 所有可能情况数，累计求和即可。

31.ts | 28 lines.

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
const tenth: number[] = []
for (let i = 0, t = 1; i < 18; ++i, t *= 10) {
  tenth.push(t)
}

export function NumberOf1Between1AndN_Solution(n: number): number {
  const nums: number[] = String(n)
    .split('')
    .map(x => Number(x))

  let result = 0
  for (let i = 0; i < nums.length; ++i) {
    result += toNum(0, i) * tenth[nums.length - i - 1]
    const x = nums[i]
    if (x < 1) continue
    else if (x > 1) result += tenth[nums.length - i - 1]
    else if (x === 1) result += toNum(i + 1, nums.length) + 1
  }
  return result

  function toNum(lft: number, rht: number): number {
    let result = 0
    for (let i = lft; i < rht; ++i) {
      result = result * 10 + nums[i]
    }
    return result
  }
}

#32 把数组排成最小的数：排序，贪心
方便起见，将原数组中所有的数字转为字符串。考虑每个顺序下两个相邻的数字 $x$ 和 $y$ ，若组成的字符串 $x y$ 字典序大于字符串 $y x$ ，则交换它们的位置可以得到一个更优的结果，且不会影响完整字符串中其它部分的大小。
32.ts | 9 lines.
1 2 3 4 5 6 7 8 9 export function PrintMinNumber(A: number[]): string { const result = A.map(x => String(x)) .sort((x, y) => { if (x === y) return 0 return x + y < y + x ? -1 : 1 }) .join('') return result }

#33 丑数：素因子，小根堆

每次取出小根堆中的根元素，然后放入其 $\times 2, \times 3, \times 5$ 的数值，直到取出了 $N$ 个数为止。

33.ts | 96 lines.

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
84
85
86
87
88
89
90
91
92
93
94
95
96
export function GetUglyNumber_Solution(N: number): number {
  for (let i = answers.length; i <= N; ++i) {
    const c = answers[i - 1]
    while (!Q.isEmpty()) {
      const x = Q.dequeue()
      if (x <= c) continue
      answers.push(x)
      Q.enqueue(x * 2)
      Q.enqueue(x * 3)
      Q.enqueue(x * 5)
      break
    }
  }
  return answers[N]
}

const answers: number[] = [0]
const Q: PriorityQueue<number> = createPriorityQueue<number>((x, y) => x - y)
Q.enqueue(1)

interface PriorityQueue<T> {
  enqueue: (val: T) => void
  dequeue: () => T | undefined
  collect: () => T[]
  top: () => T | undefined
  size: () => number
  isEmpty: () => boolean
}

// 优先队列
function createPriorityQueue<T>(cmp: (x: T, y: T) => -1 | 0 | 1 | number): PriorityQueue<T> {
  const _tree: T[] = [null]
  let _size: number = 0

  function enqueue(val: T): void {
    _tree[++_size] = val
    _up(_size)
  }

  function dequeue(): T | undefined {
    if (_size < 1) return undefined

    const target = _tree[1]
    _tree[1] = _tree[_size--]
    _down(1)

    return target
  }

  function top(): T | undefined {
    return _size > 0 ? _tree[1] : undefined
  }

  function collect(): T[] {
    return _tree.slice(1)
  }

  function _down(index: number): void {
    for (let i = index; i <= _size; ) {
      const lft = i << 1
      const rht = lft | 1
      if (lft > _size) break

      let q = lft
      if (rht <= _size && cmp(_tree[rht], _tree[q]) < 0) q += 1

      const x = _tree[q]
      if (cmp(_tree[i], x) <= 0) break

      _tree[q] = _tree[i]
      _tree[i] = x
      i = q
    }
  }

  function _up(index: number): void {
    for (let i = index; i > 1; ) {
      const q = i >> 1
      const x = _tree[q]
      if (cmp(x, _tree[i]) <= 0) break

      _tree[q] = _tree[i]
      _tree[i] = x
      i = q
    }
  }

  return {
    enqueue,
    dequeue,
    top,
    collect,
    size: () => _size,
    isEmpty: () => _size < 1,
  }
}

#34 第一个只出现一次的字符：哈希表，Map

34.ts | 13 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
export function FirstNotRepeatingChar(str: string): number {
  const duplicated: Record<string, boolean> = {}
  for (let i = 0; i < str.length; ++i) {
    const c = str[i]
    duplicated[c] = duplicated[c] === undefined ? false : true
  }

  for (let i = 0; i < str.length; ++i) {
    if (duplicated[str[i]]) continue
    return i
  }
  return -1
}

#35 数组中的逆序对：逆序对，树状数组，映射

35.ts | 42 lines.

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
interface IBinaryIndexTree {
  add(x: number, v: number): void
  sum(x: number): number
}

export function InversePairs(data: number[]): number {
  const _size = data.length

  const idx: number[] = new Array(_size)
  for (let i = 0; i < _size; ++i) idx[i] = i
  idx.sort((i, j) => data[i] - data[j])

  // 映射
  const rnk: number[] = []
  for (let i = 0; i < _size; ++i) rnk[idx[i]] = i + 1

  let result = 0
  const bit = createBIT(_size)
  for (const x of rnk) {
    result += bit.sum(_size) - bit.sum(x)
    bit.add(x, 1)
  }
  return result % (1e9 + 7)
}

function createBIT(n: number): IBinaryIndexTree {
  const lowbit = (x: number): number => x & -x

  const sumv: number[] = new Array(n + 1).fill(0)

  const add = (x: number, v: number): void => {
    for (let i = x; i <= n; i += lowbit(i)) sumv[i] += v
  }

  const sum = (x: number): number => {
    let answer = 0
    for (let i = x; i > 0; i -= lowbit(i)) answer += sumv[i]
    return answer
  }

  return { add, sum }
}

#36 两个链表的第一个公共节点：双指针

先分别从两个链表的表达走到末尾，得到所需步数分别为 $k_{1}$ 和 $k_{2}$ ，不妨设 $k_{1} > k_{2}$ ，即第一个链表比第二个长，先让快指针从第一个链表出发先走 $k_{1} - k_{2}$ 步，再让慢指针从第二个链表出发和快指针一起前进，当慢指针和快指针相等时即到达第一个公共节点

36.ts | 23 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
interface ListNode {
  val: number
  next: ListNode | null
}

export function FindFirstCommonNode(pHead1: ListNode, pHead2: ListNode): ListNode {
  let k1 = 0
  let k2 = 0

  for (let o = pHead1; o != null; o = o.next) k1 += 1
  for (let o = pHead2; o != null; o = o.next) k2 += 1

  const delta: number = Math.abs(k1 - k2)
  let faster: ListNode | null = k1 > k2 ? pHead1 : pHead2
  let slower: ListNode | null = k1 < k2 ? pHead1 : pHead2

  for (let i = 0; i < delta; ++i) faster = faster.next
  while (faster !== slower) {
    faster = faster.next
    slower = slower.next
  }
  return faster
}

#37 数字在升序数组中出现的次数：二分

37.ts | 14 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
export function GetNumberOfK(nums: number[], k: number): number {
  return lowerBound(k + 1) - lowerBound(k)

  function lowerBound(x: number): number {
    let lft = 0
    let rht = nums.length
    while (lft < rht) {
      const mid = (lft + rht) >> 1
      if (nums[mid] < x) lft = mid + 1
      else rht = mid
    }
    return lft
  }
}

#38 二叉树的深度：二叉树，DFS

38.ts | 10 lines.

1
2
3
4
5
6
7
8
9
10
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function TreeDepth(o: TreeNode | null): number {
  if (o == null) return 0
  return Math.max(TreeDepth(o.left), TreeDepth(o.right)) + 1
}

#39 平衡二叉树：二叉树，DFS

39.ts | 22 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function IsBalanced_Solution(pRoot: TreeNode): boolean {
  return dfs(pRoot) !== -1

  function dfs(o: TreeNode): 0 | -1 | number {
    if (o == null) return 0

    const h1 = dfs(o.left)
    if (h1 === -1) return -1

    const h2 = dfs(o.right)
    if (h2 === -1) return -1

    const delta = Math.abs(h1 - h2)
    return delta <= 1 ? Math.max(h1, h2) + 1 : -1
  }
}

#40 数组中只出现一次的两个数字：异或，分类
不妨记只出现一次的两个数字分别为 $x_{1}$ 和 $x_{2}$ 。先求出所有数字的异或结果 $s$ ，不难发现 $s = x_{1} \oplus x_{2}$ 。又因为 $x_{1} \neq x_{2}$ ，所以 $s \neq 0$ 。取出 $s$ 二进制位中任意一位不为 $0$ 的位 $b$ ，即 $s \oplus 2^{b - 1} = s - 2^{b - 1}$ ，将原数组中所有的数字划分为第 $b$ 为 $0$ 和第 $b$ 位为 $1$ 两大类，不难发现，
- 相同的数字会被分配到同一类中
- $x_{1}$ 和 $x_{2}$ 会被分配到不同的类别中
则问题转换为【一个数组中，除一个元素只出现一次外其它元素均恰好出现两次，求这个只出现一次的元素】，这个问题直接异或就可以了。
40.ts | 14 lines.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 export function FindNumsAppearOnce(nums: number[]): [number, number] { let s = 0 for (const x of nums) s ^= x const b = s & -s let x1 = 0 let x2 = 0 for (const x of nums) { if (x & b) x1 ^= x else x2 ^= x } return [Math.min(x1, x2), Math.max(x1, x2)] }

#41 和为 $S$ 的连续正数序列：前缀和

41.ts | 17 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
export function FindContinuousSequence(sum: number): number[][] {
  if (sum <= 0) return []

  const results: number[][] = []
  let lft = 1
  let total = 1
  for (let i = 2, _end = ((sum + 1) >> 1) + 1; i < _end; ++i) {
    total += i
    for (; total > sum; ++lft) total -= lft
    if (total === sum) {
      const answer: number[] = []
      for (let x = lft; x <= i; ++x) answer.push(x)
      results.push(answer)
    }
  }
  return results
}

#42 和为 $S$ 的两个数字：二分

42.ts | 24 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
export function FindNumbersWithSum(nums: number[], sum: number): number[] {
  const _size = nums.length
  if (_size <= 1) return []

  let i = lowerBound(1, _size, sum - nums[0])
  if (i === _size) return []

  for (; i > 0; --i) {
    const x = nums[i]
    const y = sum - x
    const j = lowerBound(0, i, y)
    if (j < i && nums[j] === y) return [y, x]
  }
  return []

  function lowerBound(lft: number, rht: number, x: number): number {
    while (lft < rht) {
      const mid = (lft + rht) >> 1
      if (nums[mid] < x) lft = mid + 1
      else rht = mid
    }
    return lft
  }
}

#43 左旋转字符串：数组切片

43.ts | 7 lines.

1
2
3
4
5
6
7
export function LeftRotateString(str: string, n: number): string {
  if (str == null || str.length <= 0) return ''
  const _size = str.length
  const k = ((n % _size) + _size) % _size
  if (k === 0) return str
  return str.slice(k) + str.slice(0, k)
}

#44 翻转单词序列：字符串

44.ts | 3 lines.

1
2
3
export function ReverseSentence(s: string): string {
  return s.split(/\s+/g).reverse().join(' ')
}

#45 扑克牌顺子：模拟，枚举

45.ts | 16 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
export function IsContinuous(numbers: number[]): boolean {
  const nums = numbers.slice().sort((x, y) => x - y)
  let i = 0
  for (; i < nums.length; ++i) if (nums[i]) break
  if (i + 1 >= nums.length) return true

  let x = nums[i]
  for (let j = i + 1; j < nums.length; ++j) {
    const y = nums[j]
    if (x === y) return false
    i -= y - x - 1
    if (i < 0) return false
    x = y
  }
  return true
}

#46 孩子们的游戏(圆圈中最后剩下的数)：数学，约瑟夫环

46.ts | 8 lines.

1
2
3
4
5
6
7
8
export function LastRemaining_Solution(n: number, m: number): number {
  if (n === 0) return -1
  if (n === 1) return 0
  const x = LastRemaining_Solution(n - 1, m)

  // 以上一个位置为零号位置重新编号
  return (m + x) % n
}

#47 求 $1 + 2 + \dots + n$ ：逻辑运算符，递归

47.ts | 3 lines.

1
2
3
export function Sum_Solution(n: number): number {
  return n > 0 && Sum_Solution(n - 1) + n
}

#48 不用加减乘除做加法：位运算，模拟

48.ts | 25 lines.

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
export function Add(num1: number, num2: number): number {
  let result = 0
  for (; num1 > 0 && num2 > 0; ) {
    let a = num1 & -num1
    let b = num2 & -num2
    if (a <= b) {
      num1 ^= a
      for (; a & result; a <<= 1) result ^= a
      result ^= a
    } else {
      num2 ^= b
      for (; b & result; b <<= 1) result ^= b
      result ^= b
    }
  }

  if (num2 > 0) num1 = num2
  for (; num1 > 0; ) {
    let a = num1 & -num1
    num1 ^= a
    for (; a & result; a <<= 1) result ^= a
    result ^= a
  }
  return result
}

#49 把字符串转换成整数：十进制，模拟

49.ts | 22 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
export function StrToInt(str: string): number {
  if (str == null || str.length <= 0) return 0

  let flag: boolean = false
  let result = 0
  let i = 0

  if (str[0] === '+') i += 1
  else if (str[0] === '-') {
    flag = true
    i += 1
  }

  if (i >= str.length) return 0
  const zero = '0'.codePointAt(0)
  for (; i < str.length; ++i) {
    const x = str.codePointAt(i) - zero
    if (x < 0 || x > 9) return 0
    result = result * 10 + x
  }
  return flag && result ? -result : result
}

#50 数组中重复的数字：判重

50.ts | 15 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
export function duplicate(nums: number[]): number {
  const _size: number = nums.length
  const set: Set<number> = new Set()

  // 校验输入数据
  for (const x of nums) {
    if (x < 0 || x >= _size) return -1
  }

  for (const x of nums) {
    if (set.has(x)) return x
    set.add(x)
  }
  return -1
}

#51 构建乘积数组：前缀积、后缀积

51.ts | 14 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
export function multiply(A: number[]): number[] {
  const _size = A.length
  const s1: number[] = [A[0]]
  const s2: number[] = []
  s2[_size - 1] = A[_size - 1]

  for (let i = 1; i < _size; ++i) s1[i] = s1[i - 1] * A[i]
  for (let i = _size - 2; i >= 0; --i) s2[i] = s2[i + 1] * A[i]

  const B: number[] = [s2[1]]
  for (let i = 1; i + 1 < _size; ++i) B[i] = s1[i - 1] * s2[i + 1]
  B[_size - 1] = s1[_size - 2]
  return B
}

#52 正则表达式匹配：字符串，匹配，递归

52.ts | 38 lines.

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
export function match(str: string, pattern: string): boolean {
  return f(0, 0)

  function f(i: number, j: number): boolean {
    if (i === str.length) {
      if ((pattern.length - j) & 1) return false
      for (j += 1; j < pattern.length; j += 2) {
        if (pattern[j] !== '*') return false
      }
      return true
    }
    if (j === pattern.length) return false

    const x = pattern[j]
    switch (x) {
      case '*': {
        return f(i, j + 1)
      }
      case '.': {
        if (j + 1 < pattern.length && pattern[j + 1] === '*') {
          for (; i <= str.length; ++i) {
            if (f(i, j + 2)) return true
          }
          return false
        }
        return f(i + 1, j + 1)
      }
      default: {
        if (j + 1 < pattern.length && pattern[j + 1] === '*') {
          if (f(i, j + 2)) return true
          for (; i < str.length && str[i] === x; ++i) if (f(i + 1, j + 2)) return true
          return false
        }
        return str[i] === x && f(i + 1, j + 1)
      }
    }
  }
}

#53 表示数值的字符串：字符串，匹配，正则表达式

53.ts | 3 lines.

1
2
3
export function isNumeric(str: string): boolean {
  return /^[+-]?(\.\d+|\d+(\.\d+)?)([eE][+-]?\d+)?$/.test(str)
}

#54 字符流中第一个不重复的字符： Set

54.ts | 24 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const queue: string[] = []
const set1: Set<string> = new Set<string>()
const set2: Set<string> = new Set<string>()

export function Init(): void {
  queue.length = 0
  set1.clear()
  set2.clear()
}

export function Insert(ch: string): void {
  if (set1.has(ch)) return void set2.add(ch)
  set1.add(ch)
  queue.push(ch)
}

export function FirstAppearingOnce(): string {
  while (queue.length > 0) {
    const x = queue[0]
    if (set2.has(x)) queue.shift()
    else return x
  }
  return '#'
}

#55 链表中环的入口结点：链表，双指针

参见不修改数组找出重复的数字#追击法

55.ts | 27 lines.

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
interface ListNode {
  val: number
  next: ListNode | null
}

export function EntryNodeOfLoop(pHead: ListNode): ListNode | null {
  if (pHead == null) return null

  let slower: ListNode | null = pHead
  let faster: ListNode | null = pHead
  do {
    faster = faster.next
    if (faster == null) return null

    faster = faster.next
    if (faster == null) return null

    slower = slower.next
  } while (slower !== faster)

  slower = pHead
  while (slower !== faster) {
    faster = faster.next
    slower = slower.next
  }
  return slower
}

#56 删除链表中重复的节点：链表，递归

56.ts | 19 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
interface ListNode {
  val: number
  next: ListNode | null
}

export function deleteDuplication(o: ListNode | null): ListNode | null {
  if (o == null) return null

  let v = o.next
  if (v == null) return o

  o.next = null
  if (o.val === v.val) {
    for (v = v.next; v != null; v = v.next) if (o.val !== v.val) break
    return deleteDuplication(v)
  }
  o.next = deleteDuplication(v)
  return o
}

#57 二叉树的下一个结点：二叉树，中序遍历

中序遍历的下一个节点要么是第一个还没有遍历右子节点的祖先节点，要么是右子树中的最左叶子节点。

57.ts | 21 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
interface TreeLinkNode {
  val: number
  left: TreeLinkNode | null
  right: TreeLinkNode | null
  next: TreeLinkNode | null
}

export function GetNext(o: TreeLinkNode): TreeLinkNode | null {
  if (o.right) {
    let v = o.right
    while (v.left) v = v.left
    return v
  }

  let v = o.next
  while (v && v.right === o) {
    o = v
    v = v.next
  }
  return v
}

#58 对称的二叉树：二叉树，BFS

58.ts | 43 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

interface Item {
  node: TreeNode
  step: number
}

export function isSymmetrical(pRoot: TreeNode): boolean {
  if (pRoot == null) return true
  const Q: Item[] = []
  const nums: number[] = []
  let tot = 0

  let currentStep = 0
  Q.push({ node: pRoot, step: 0 })
  while (Q.length > 0) {
    const { node, step } = Q.shift()

    if (currentStep < step) {
      currentStep = step
      for (let i = 0, j = tot - 1; i < j; ++i, --j) {
        if (nums[i] !== nums[j]) return false
      }
      tot = 0
    }

    if (node == null) nums[tot++] = -Number.MAX_SAFE_INTEGER
    else {
      nums[tot++] = node.val
      Q.push({ node: node.left, step: step + 1 })
      Q.push({ node: node.right, step: step + 1 })
    }
  }

  for (let i = 0, j = tot - 1; i < j; ++i, --j) {
    if (nums[i] !== nums[j]) return false
  }
  return true
}

#59 按之字形顺序打印二叉树：二叉树，BFS

59.ts | 38 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

interface Item {
  node: TreeNode
  step: number
}

export function Print(o: TreeNode): number[][] {
  if (o == null) return []
  const Q: Item[] = []
  const results: number[][] = []
  const tmp: number[] = []
  let currentStep = 1
  let tot = 0
  Q.push({ node: o, step: 1 })

  while (Q.length > 0) {
    const { node, step } = Q.shift()
    if (currentStep < step) {
      const result: number[] = tmp.slice(0, tot)
      if (step & 1) result.reverse()
      results.push(result)
      tot = 0
      currentStep = step
    }
    tmp[tot++] = node.val
    if (node.left) Q.push({ node: node.left, step: step + 1 })
    if (node.right) Q.push({ node: node.right, step: step + 1 })
  }
  const result: number[] = tmp.slice(0, tot)
  if ((currentStep + 1) & 1) result.reverse()
  results.push(result)
  return results
}

#60 把二叉树打印成多行：二叉树，BFS

60.ts | 38 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

interface Item {
  node: TreeNode
  step: number
}

export function Print(o: TreeNode): number[][] {
  if (o == null) return []

  const Q: Item[] = []
  const results: number[][] = []
  const tmp: number[] = []

  let currentStep = 1
  let tot = 0
  Q.push({ node: o, step: 1 })

  while (Q.length > 0) {
    const { node, step } = Q.shift()
    if (currentStep < step) {
      const result = tmp.slice(0, tot)
      results.push(result)
      tot = 0
      currentStep = step
    }
    tmp[tot++] = node.val
    if (node.left) Q.push({ node: node.left, step: step + 1 })
    if (node.right) Q.push({ node: node.right, step: step + 1 })
  }
  const result = tmp.slice(0, tot)
  results.push(result)
  return results
}

#61 序列化二叉树：二叉树，重建二叉树

序列化：求出先序遍历和后序遍历，并将其转为字符串
反序列化：通过先序遍历和后序遍历结果重建树

61.ts | 55 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function Serialize(pRoot: TreeNode): string {
  const pre: number[] = []
  const vin: number[] = []

  if (pRoot != null) {
    preTraverse(pRoot)
    vinTraverse(pRoot)
  }

  return pre.join(',') + '#' + vin.join(',')

  function preTraverse(o: TreeNode | null): void {
    if (o == null) return
    pre.push(o.val)
    preTraverse(o.left)
    preTraverse(o.right)
  }

  function vinTraverse(o): void {
    if (o == null) return
    vinTraverse(o.left)
    vin.push(o.val)
    vinTraverse(o.right)
  }
}

export function Deserialize(s: string): TreeNode | null {
  if (s === '#') return null
  const [x, y] = s.split('#')
  const pre: number[] = x.split(',').map(n => Number(n))
  const vin: number[] = y.split(',').map(n => Number(n))

  if (pre.length <= 0 || pre.length !== vin.length) return null
  const tree = f(0, pre.length - 1, 0, vin.length - 1)
  return tree

  function f(lft1: number, rht1: number, lft2: number, rht2: number): TreeNode {
    const t = pre[lft1]
    let x = lft2
    for (; x <= rht2; ++x) if (vin[x] === t) break

    const o = {
      val: t,
      left: lft2 < x ? f(lft1 + 1, lft1 + x - lft2, lft2, x - 1) : null,
      right: rht2 > x ? f(lft1 + x - lft2 + 1, rht1, x + 1, rht2) : null,
    }
    return o
  }
}

#62 二叉搜索树的第k个结点：二叉树，二叉搜索树，中序遍历

62.ts | 28 lines.

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
interface TreeNode {
  val: number
  left: TreeNode | null
  right: TreeNode | null
}

export function KthNode(pRoot: TreeNode, k: number): TreeNode | null {
  let result = null
  if (k <= 0) return result

  f(pRoot)
  return result

  function f(o: TreeNode): void {
    if (o == null) return

    f(o.left)
    if (result != null) return

    k -= 1
    if (k <= 0) {
      result = o
      return
    }

    f(o.right)
  }
}

#63 数据流中的中位数：堆，中位数

维护一个大根堆和小根堆：

大根堆中存放当前数列中前 $⌈ \frac{N}{2} ⌉$ 小的元素；
小根堆中存放当前数列中后 $⌊ \frac{N}{2} ⌋$ 大的元素；

则每次查询时，若元素个数为奇数，直接返回大根堆的根顶元素；否则，即元素个数为偶数，返回小根堆和大根堆的堆顶元素的平均值。

63.ts | 18 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import { PriorityQueue } from '@algorithm.ts/queue'

const lowerQ = new PriorityQueue<number>({ compare: (x, y) => y - x })
const upperQ = new PriorityQueue<number>({ compare: (x, y) => x - y })

export function Insert(num: number): void {
  if (lowerQ.size === upperQ.size) {
    upperQ.enqueue(num)
    lowerQ.enqueue(upperQ.dequeue()!)
  } else {
    lowerQ.enqueue(num)
    upperQ.enqueue(lowerQ.dequeue()!)
  }
}

export function GetMedian(): number {
  return lowerQ.size === upperQ.size ? (lowerQ.front()! + upperQ.front()!) / 2 : lowerQ.front()!
}

#64 滑动窗口的最大值：滑动窗口，单调栈

64.ts | 19 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
export function maxInWindows(nums: number[], size: number): number[] {
  if (nums.length < size || size <= 0) return []
  const stack: number[] = []
  for (let i = 0, _end = size - 1; i < _end; ++i) {
    const x = nums[i]
    while (stack.length > 0 && x >= nums[stack[stack.length - 1]]) stack.pop()
    stack.push(i)
  }

  const results: number[] = []
  for (let i = size - 1; i < nums.length; ++i) {
    const x = nums[i]
    if (stack.length > 0 && stack[0] + size === i) stack.shift()
    while (stack.length > 0 && x >= nums[stack[stack.length - 1]]) stack.pop()
    stack.push(i)
    results.push(nums[stack[0]])
  }
  return results
}

#65 矩阵中的路径：模拟，矩阵

65.ts | 32 lines.

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
export function hasPath(matrix: string[][], word: string): boolean {
  if (word == null || word.length <= 0) return true

  const R = matrix.length
  if (R <= 0) return false

  const C = matrix[0].length
  if (C <= 0) return false

  const vis: boolean[][] = []
  for (let x = 0; x < R; ++x) vis[x] = new Array(C).fill(false)

  for (let x = 0; x < R; ++x) {
    for (let y = 0; y < C; ++y) {
      if (f(x, y, 0)) return true
    }
  }
  return false

  function f(x: number, y: number, cur: number): boolean {
    if (x < 0 || x >= R || y < 0 || y >= C) return false
    if (vis[x][y] || matrix[x][y] !== word[cur]) return false

    cur += 1
    if (cur === word.length) return true

    vis[x][y] = true
    const flag = f(x - 1, y, cur) || f(x + 1, y, cur) || f(x, y - 1, cur) || f(x, y + 1, cur)
    vis[x][y] = false
    return flag
  }
}

#66 机器人的运动范围： BFS

66.ts | 30 lines.

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
export function movingCount(threshold: number, rows: number, cols: number): number {
  const vis: boolean[][] = []
  for (let i = 0; i < rows; ++i) {
    vis[i] = new Array(cols).fill(false)
  }

  let result = 0
  f(0, 0)
  return result

  function f(x: number, y: number): void {
    if (x < 0 || x >= rows || y < 0 || y >= cols) return
    if (vis[x][y]) return
    vis[x][y] = true
    const total = weight(x) + weight(y)
    if (total > threshold) return

    result += 1
    f(x - 1, y)
    f(x + 1, y)
    f(x, y - 1)
    f(x, y + 1)
  }

  function weight(x: number): number {
    let result = 0
    for (let i = x; i > 0; i = Math.round((i - (i % 10)) / 10)) result += i % 10
    return result
  }
}

#67 剪绳子：数学

考虑剪下来的某段长为 $x$ 的绳子，继续减它不会对其它段造成影响。

若 $x > 4$ ，则必然有 $(x - 3) \times 3 > x$ ；
当 $x ⩽ 4$ 时，有 $x > (x - 1) \times 1 ⩾ (x - 2) \times 2$

这启发我们尽可能将绳子剪成长度为 $3$ 的段，而当某一段长度为 $4$ 时，则不再剪它。

67.ts | 17 lines.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
export function cutRope(n: number): number {
  if (n <= 0) return 0
  if (n <= 4) return n

  let result = 1
  if (n % 3 === 1) {
    result = 4
    n -= 4
  } else if (n % 3 === 2) {
    result = 2
    n -= 2
  }
  for (; n > 0; n -= 3) {
    result *= 3
  }
  return result
}

@algorithm.ts/queue

前言¶

01 二维数组的查找¶

题意简述¶

题目简析¶

程序实现¶

04 重建二叉树¶

题目简述¶

题目简析¶

程序实现¶

06 旋转数组的最小数字¶

题目简述¶

题目简析¶

程序实现¶

23 二叉搜索树的后序遍历序列¶

题目描述¶

题目简析¶

程序实现¶

附录¶

Related¶

前言
¶

01 二维数组的查找
¶

题意简述
¶

题目简析
¶

程序实现
¶

04 重建二叉树
¶

题目简述
¶

题目简析
¶

程序实现
¶

06 旋转数组的最小数字
¶

题目简述
¶

题目简析
¶

程序实现
¶

23 二叉搜索树的后序遍历序列
¶

题目描述
¶

题目简析
¶

程序实现
¶

附录
¶

Related
¶