avatar

光和尘

有花满渚、有酒盈瓯

目录检索关于我

🔖 专题训练解题报告

前言

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

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

01 二维数组的查找

题目链接

题意简述

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

题目简析

注意到矩阵中任意一个子矩阵仍然满足此特性,则可以二分子矩阵,直到子矩阵的大小为 1 \times 1. 具体地,若当前所检查的子矩阵为 (l_1, r_1, l_2, r_2),取位置 \displaystyle \left(x = \left\lfloor\frac{l_1+l_2}{2}\right\rfloor, y = \left\lfloor\frac{r_1+r_2}{2}\right\rfloor\right),则:

  • 若目标值恰好等于此位置上的值,则直接返回 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=\lbrace a_1,a_2,\cdots,a_N \rbrace,将其前面 K 个(0 \leqslant K < N)个元素取出并按顺序放在原序列的末尾,得到新序列

B=\lbrace b_1, b_2, \cdots, b_N\rbrace = \lbrace a_{K+1},a_{K+2},\cdots,a_N, a_1, a_2, \cdots, a_K \rbrace

B 中的最小值。

题目简析

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

  1. b_1 < b_N,即 B 单调递增,此时 b_1 即为所求答案
  2. b_1 > b_N,即 B 先上升后突降再上升,取 x = \left\lfloor\frac{1 + N}{2}\right\rfloor
    • b_x < b_N,则答案落在 \lbrace b_1, b_2, \cdots b_x\rbrace
    • 否则,即 b_x > b_N,则答案落在 \lbrace b_{x+1}, b_{x+2}, \cdots, c_N\rbrace

原问题在简化版问题基础上的第二种情况种多了一种可能: 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=\lbrace a_1, a_2, \cdots, a_N \rbrace 是否为一棵二叉搜索树的后序遍历结果。

题目简析

后续遍历中,最后一个元素为根节点,这启发我们逆序遍历 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) {
    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) = \left\lbrace\begin{aligned} &0, &n \leqslant 0\\ &1, &n = 1\\ &1, &n = 2\\ &f(n-1) + f(n-2), &n \geqslant 3\\ \end{aligned}\right.
    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) = \left\lbrace\begin{aligned} &0, &n \leqslant 0\\ &1, &n = 1\\ &2, &n = 2\\ &f(n-1) + f(n-2), &n \geqslant 3\\ \end{aligned}\right.
    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) = \left\lbrace\begin{aligned} &0, &n \leqslant 0\\ &2^{n-1}, &n > 0\\ \end{aligned}\right.
    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) = \left\lbrace\begin{aligned} &0, &n \leqslant 0\\ &1, &n = 1\\ &2, &n = 2\\ &f(n-1) + f(n-2), &n \geqslant 3\\ \end{aligned}\right.
    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) {
    let faster = pHead
    let slower = 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  | 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 RandomListNode {
    label: number
    next: RandomListNode | null
    random: RandomListNode | null
    }
    export function Clone(o: RandomListNode): RandomListNode {
    if (o == null) return null
    const map = new Map()
    const root = { ...o }
    for (let u = root, v = o; v != null; u = u.next, v = v.next) {
    map.set(v, u)
    if (v.next != null) {
    let 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 (let x of nums) if (x === current) cnt += 1
      if (cnt << 1 >= 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_2.ts  | 1 lines.
      1
  • #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 出现的次数(从 1n 整数中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 把数组排成最小的数: 排序,贪心

    方便起见,将原数组中所有的数字转为字符串。考虑每个顺序下两个相邻的数字 xy,若组成的字符串 xy 字典序大于字符串 yx,则交换它们的位置可以得到一个更优的结果,且不会影响完整字符串中其它部分的大小。

    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  | 37 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
    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) {
    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_1k_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_1x_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},将原数组中所有的数字划分为第 b0 和第 b 位为 1 两大类,不难发现,

    • 相同的数字会被分配到同一类中
    • x_1x_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 + \cdots + 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) {
    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