^-^
算法复习
最近更新：2025-03-14   |   字数总计：10.1k   |   阅读估时：43分钟   |   阅读量：次
  1. 介绍
  2. 数据结构
    1. 数组链表
    2. 哈希表原理及应用
      1. 一个常见误区
      2. 核心概念
      3. LinkHashMap
      4. ArrayHashMap
    3. 二叉树基础及遍历
      1. 几种常见的二叉树
      2. 算法题中常见实现示例
      3. 二叉树遍历
        1. 递归遍历（DFS）
        2. 层序遍历（BFS）
        3. 拓展例题
    4. 多叉树基础及遍历
      1. 多叉树递归遍历（DFS）
      2. 多叉树层序遍历（BFS）
    5. 二叉搜索树
      1. TreeMap/TreeSet 实现原理
      2. 性能问题
    6. 二叉堆原理
    7. 线段树核心原理
    8. 图结构
      1. 邻接表和邻接矩阵实现图结构
      2. 不同种类的图结构
      3. 图结构的通用代码实现
      4. 图的遍历
        1. DFS
          1. 遍历所有节点
          2. 遍历所有路径
        2. BFS
  3. 刷题
    1. 链表
    2. 数组
      1. 滑动窗口题目
      2. 二分搜索
      3. 前缀和数组
      4. 差分数组
    3. 队列/栈
      1. 栈习题
      2. 队列习题
      3. 单调栈
      4. 单调队列
    4. 二叉树 & 递归思想
      1. 递归思维模式
      2. 二叉树解题思维模式

介绍

算法复习笔记，存档后便于以后复习，不会有很详细的解释，但是会有大致的复习路径和模块，最后会补充习题单便于测试自己复习情况

数据结构

数组链表

环形数组 这个技巧是重点，可以用 O(1) 的时间复杂度在数组头部进行插入删除操作。

环形数组 技巧利用求模（余数）运算，将普通数组变成逻辑上的 环形数组，可以让我们用 O(1) 的时间在数组头部增删元素。

环形数组 的关键在于，它维护了两个指针 start 和 end，start 指向第一个有效元素的索引，end 指向最后一个有效元素的下一个位置索引。

这样，当我们在数组头部添加或删除元素时，只需要移动 start 索引，而在数组尾部添加或删除元素时，只需要移动 end 索引。

当 start，end 移动超出数组边界（< 0 或 >= arr.length）时，我们可以通过求模运算 % 让它们转一圈到数组头部或尾部继续工作，这样就实现了 环形数组 的效果。

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
/**
 * 循环数组, 左开右闭
 */
class CycleArray {
  size = 1;
  array: any[] = [];
  start = 0;
  end = 0;
  count = 0;
  constructor(size = 1) {
    this.size = size;
    this.array = [];
    this.start = 0;
    this.end = 0;
    this.count = 0;
  }

  resize(newSize) {
    let newArray: any[] = [];
    for (let i = 0; i < newSize; i++) {
      newArray.push(this.array[(this.start + i) % this.size]);
    }
    this.array = newArray;
    this.start = 0;
    this.end = this.count;
    this.size = newSize;
  }

  isFull() {
    return this.count === this.size;
  }

  isEmpty() {
    return this.count === 0;
  }

  addFirst(val) {
    if (this.isFull()) {
      this.resize(this.size * 2);
    }
    this.start = (this.start - 1 + this.size) % this.size;
    this.array[this.start] = val;
    this.count++;
  }

  removeFirst() {
    if (this.isEmpty()) {
      return null;
    }
    this.array[this.start] = null;
    this.start = (this.start + 1) % this.size;
    this.count--
    if (this.count > 0 && this.count === this.size / 4) {
      this.resize(this.size / 2);
    }
  }

  addLast(val) {
    if (this.isFull()) {
      this.resize(this.size * 2);
    }
    this.array[this.end] = val;
    this.end = (this.end + 1) % this.size;
    this.count++;
  }

  removeLast(val) {
    if (this.isEmpty()) {
      return null;
    }
    this.end = (this.end - 1 + this.size) % this.size;
    this.array[this.end] = null;
    this.count--;
    if (this.count > 0 && this.count === this.size / 4) {
      this.resize(this.size / 2);
    }
  }

  getFirst() {
    if (this.isEmpty()) {
      return null;
    }
    return this.array[this.start];
  }

  getLast() {
    if (this.isEmpty()) {
      return null;
    }
    return this.array[(this.end - 1 + this.size) % this.size];
  }

  length() {
    return this.count;
  }
}

哈希表原理及应用

哈希表可以和数组、双链表进行结合，形成更强大的数据结构 LinkedHashMap 和 ArrayHashMap，它们可以给哈希表增加新的特性，需要了解其中的原理。

一个常见误区

哈希表和我们常说的 Map（键值映射）是不是同一个东西？不是。

Map 接口本身只定义了键值映射的一系列操作，HashMap 这种数据结构根据自身特点实现了这些操作。还有其他数据结构也实现了这个接口，比如 TreeMap、LinkedHashMap 等等。

换句话说，你可以说 HashMap 的 get、put、remove 方法的复杂度都是 O(1) 的，但你不能说 Map 接口的复杂度都是 O(1)。因为如果换成其他的实现类，比如底层用二叉树结构实现的 TreeMap，这些方法的复杂度就变成 O(logN) 了。

核心概念

  • key 唯一 value 可重复
  • 哈希函数的作用是把任意长度的输入（key）转化成固定长度的输出（索引）。哈希函数的效率就对应了哈希表的查找效率
  • 如果两个不同的 key 通过哈希函数得到了相同的索引，即产生了哈希冲突，可以通过两个方法解决哈希冲突
    • 拉链法，哈希表底层直接存 value，而是存链表，当出现相同索引时将 key->value 对存到链表里
    • 开放寻址法，出现冲突时直接查找 index+1 的位置观察是否为空，持续向后找，直到不为空时存入
  • 扩容和负载因子
    • 当哈希表内数据过多时，会更容易出现哈希冲突，此时扩容哈希表，降低负载因子，提高哈希表效率
    • 负载因子 = k-v对数 / table.length
  • 不建议遍历过程中增删哈希表
    • 遍历哈希表的 key，本质就是遍历哈希表底层的 table 数组，如果一边遍历一边增删元素，如果遍历到一半，插入/删除操作触发了扩缩容，整个 table 数组都变了，那么请问，接下来应该是什么行为？还有，在遍历过程中新插入/删除的元素，是否应该被遍历到？
  • key 必须不可变

LinkHashMap

现在希望在不改变 哈希表 增删查改复杂度的前提下，能够按照插入顺序来访问所有键，且不受扩缩容影响。

最直接的思路就是，我想办法把这些键值对都用类似 链表节点 的结构串联起来，持有一个头尾结点 head，tail 的引用，每次把新的键插入 table 数组时，同时把这个键插入 链表 的尾部。

这样一来，只要我从头结点 head 开始遍历 链表，就能按照插入顺序访问所有键了：

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
// 设计链表技巧，使用前置head和后置tail，实际链表的值在head和tail之间，这样在插入和删除时，不需要考虑边界情况

class Node {
  constructor(key, value) {
    this.key = key
    this.value = value
    this.prev = null
    this.next = null
  }
}

class LinkHashMap {
  constructor() {
    this.map = new Map()
    this.head = new Node(null)
    this.tail = new Node(null)
    this.head.next = this.tail
    this.tail.prev = this.head
  }

  containsKey(key) {
    return this.map.has(key)
  }

  get(key) {
    if (this.containsKey(key)) {
      return this.map.get(key).value
    }
  }

  addToTail(node) {
    const temp = this.tail.prev
    temp.next = node
    node.prev = temp
    node.next = this.tail
    this.tail.prev = node
  }

  put(key, value) {
    if (this.containsKey(key)) {
      const node = this.map.get(key)
      node.value = value
    } else {
      const node = new Node(key, value)
      this.map.set(key, node)
      this.addToTail(node)
    }
  }

  remove(key) {
    if (this.containsKey(key)) {
      const node = this.map.get(key)
      node.prev.next = node.next
      node.next.prev = node.prev
      this.map.delete(key)
    } else {
      return null
    }
  }

  keys() {
    const keysList = []
    let cur = this.head.next
    while (cur !== this.tail) {
      keysList.push(cur.key)
      cur = cur.next
    }
    return keysList
  }

  log() {
    let cur = this.head.next
    while (cur !== this.tail) {
      console.log(cur.key + ' -> ' + cur.value)
      cur = cur.next
    }
  }
}

const map = new LinkHashMap();
map.put("a", 1);
map.put("b", 2);
map.put("c", 3);
map.put("d", 4);
map.put("e", 5);

console.log(map.keys()); // ['a', 'b', 'c', 'd', 'e']

map.remove("c");

console.log(map.keys()); // ['a', 'b', 'd', 'e']

map.put("a", 9)
map.log()

ArrayHashMap

如果我们想要给 Hash表 增加一个 randomKey() API，即均匀随机返回随机键，并且保证在 O(1) 复杂度内做到，我们需要使用数组来存储 Node，这样可以通过数组的随机访问特性来实现。

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
class Node {
  constructor() {
    this.key = null;
    this.value = null;
    this.index = null;
  }
}

class ArrayHashMap {
  constructor() {
    this.map = new Map();
    this.array = [];
    this.count = 0;
  }

  put(key, value) {
    if (this.map.has(key)) {
      const node = this.map.get(key)
      node.value = value
    } else {
      const node = new Node()
      node.key = key
      node.value = value
      node.index = this.count
      this.map.set(key, node)
      this.array.push(node)
      this.count++
    }
  }

  get(key) {
    if (this.map.has(key)) {
      return this.map.get(key).value
    }
  }

  remove(key) {
    if (!this.map.has(key)) {
      return null
    }

    if (this.count < 1) {
      return
    }

    const curNode = this.map.get(key)
    const tailNode = this.array[this.count - 1]
    this.array[curNode.index] = tailNode
    this.array.pop()
    this.count--
    tailNode.index = curNode.index
  }

  randomKey() {
    let randomIndex = Math.floor(Math.random() * this.count)
    return this.array[randomIndex].key
  }

  size() {
    return this.map.size;
  }

  log(){
    for (let index = 0; index < this.array.length; index++) {
      const node = this.array[index];
      console.log(node.key + ' -> ' + node.value);
    }
  }
}

let map = new ArrayHashMap();
map.put(1, 1);
map.put(2, 2);
map.put(3, 3);
map.put(4, 4);
map.put(5, 5);

console.log(map.get(1)); // 1
console.log(map.randomKey());

map.remove(2);
map.log()
console.log(map.randomKey());
console.log(map.randomKey());

二叉树基础及遍历

几种常见的二叉树

  • 满二叉树：
    • 满二叉树就是每一层节点都是满的，整棵树像一个正三角形。
    • 满二叉树有个优势，就是它的节点个数很好算。假设深度为 h，那么总节点数就是 2^h - 1。
  • 完全二叉树：
    • 完全二叉树的每一层的节点都紧凑靠左排列，且除了最后一层，其他每层都必须是满的。
    • 由于它的节点紧凑排列，如果从左到右从上到下对它的每个节点编号，那么父子节点的索引存在明显的规律。
    • 完全二叉树的左右子树也是完全二叉树，至少有一棵是满二叉树。
  • 平衡二叉树：
    • 它的「每个节点」的左右子树的高度差不超过 1。
  • 二叉搜索树:
    • 对于树中的每个节点，其左子树的每个节点的值都要小于这个节点的值，右子树的每个节点的值都要大于这个节点的值。你可以简单记为「左小右大」。

算法题中常见实现示例

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
const TreeNode = function (x) {
  this.val = x;
  this.left = null;
  this.right = null;
}

// 可以这样构建一棵二叉树：
const root = new TreeNode(1);
root.left = new TreeNode(2);
root.right = new TreeNode(3);
root.left.left = new TreeNode(4);
root.right.left = new TreeNode(5);
root.right.right = new TreeNode(6);

// 构建出来的二叉树是这样的：
//     1
//    / \
//   2   3
//  /   / \
// 4   5   6

// 哈希表存储二叉树
// 1 -> [2, 3]
// 2 -> [4]
// 3 -> [5, 6]

let tree = new Map([
  [1, [2, 3]],
  [2, [4]],
  [3, [5, 6]]
]);

二叉树遍历

递归遍历（DFS）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
const TreeNode = function (x) {
  this.val = x;
  this.left = null;
  this.right = null;
}

// 二叉树的遍历框架
const traverse = function (root) {
  if (root === null) {
    return;
  }
  // 前序位置
  traverse(root.left);
  // 中序位置
  traverse(root.right);
  // 后序位置
}

前序位置的代码会在进入节点时执行；中序位置的代码会在左子树遍历完成后，遍历右子树之前执行；后序位置的代码会在左右子树遍历完成后执行

层序遍历（BFS）

二叉树的层序遍历，顾名思义，就是一层一层地遍历二叉树。这个遍历方式需要借助队列来实现，而且根据不同的需求，主要有三种不同的写法，下面一一列举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
// 每次把队头元素拿出来，然后把它的左右子节点加入队列，无法知道当前节点在第几层
const levelOrderTraverse1 = function (root) {
  if (root === null) {
    return
  }

  const q = []
  q.push(root)
  while (q.length !== 0) {
    const cur = q.shift()
    console.log(cur.val)

    if (cur.left) {
      q.push(cur.left)
    }

    if (cur.right) {
      q.push(cur.right)
    }
  }
}
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
const levelOrderTraverse = function (root) {
  if (root === null) {
    return
  }

  const q = []
  q.push(root)
  let depth = 1
  while (q.length !== 0) {
    const size = q.length
    for (let i = 0; i < size; i++) {
      const cur = q.shift()
      console.log('depth: ', depth, ',', cur.val)

      if (cur.left) {
        q.push(cur.left)
      }

      if (cur.right) {
        q.push(cur.right)
      }
    }
    depth++
  }
}

我们每向下遍历一层，就给 depth 加 1，可以理解为每条树枝的权重是 1，二叉树中每个节点的深度，其实就是从根节点到这个节点的路径权重和，且同一层的所有节点，路径权重和都是相同的。

如果每根树枝权重不同，我们则引入第三种写法，添加一个State类，让节点自行维护depth。

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
function State(node, depth) {
  this.node = node
  this.depth = depth
}

// 假设所有左子树支权重为1，右子树枝权重为2
const levelOrderTraverse = function (root) {
  if (root === null) {
    return
  }

  const q = []
  q.push(new State(root, 1))
  while (q.length !== 0) {
    const size = q.length
    for (let i = 0; i < size; i++) {
      const cur = q.shift()
      console.log('depth: ', cur.depth, ',', cur.node.val)

      if (cur.node.left) {
        q.push(new State(cur.node.left, cur.depth+1))
      }

      if (cur.node.right) {
        q.push(new State(cur.node.right, cur.depth+2))
      }
    }
  }
}
拓展例题

查找最短路径使用BFS算法，BFS是一层一层扫描，找到第一个叶子节点时就可结束遍历，查找所有路径使用DFS算法，DFS算法类似于从左到右遍历一颗颗子树，遍历到底才回溯，更加直观的查找所有路径。

多叉树基础及遍历

多叉树结构就是二叉树结构的延伸，二叉树是特殊的多叉树。森林是指多个多叉树的集合。多叉树的遍历就是二叉树遍历的延伸。

多叉树递归遍历（DFS）

1
2
3
4
5
6
7
8
9
10
const traverse = function(root){
  if(root === null){
    return
  }
  // 前序位置
  for(let i = 0; i < root.children.length; i++){
    traverse(root.children[i])
  }
  // 后序位置
}

多叉树层序遍历（BFS）

多叉树的层序遍历和二叉树的层序遍历一样，都是用队列来实现，无非就是把二叉树的左右子节点换成了多叉树的所有子节点。所以多叉树的层序遍历也有三种写法，下面一一列举。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
const levelOrderTraverse = function(root) {
  if (root === null) {
    return;
  }
  const q = [];
  q.push(root);
  while (q.length !== 0) {
    const cur = q.shift();
    console.log(cur.val);
    for (let i = 0; i < cur.children.length; i++) {
      q.push(cur.children[i]);
    }
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const levelOrderTraverse = function(root) {
  if (root === null) {
    return;
  }

  const q = [];
  let depth = 1;
  q.push(root);
  while (q.length !== 0) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const cur = q.shift();
      console.log(cur.val + ` depth: ${depth}`);
      for (let j = 0; j < cur.children.length; j++) {
        q.push(cur.children[j]);
      }
    }
    depth++;
  }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function State(node, depth) {
  this.node = node;
  this.depth = depth;
}

// 假设每个子树从左到右权重+1
const levelOrderTraverse = function(root) {
  if (root === null) {
    return;
  }
  const q = [];
  q.push(new State(root, 1));
  while (q.length !== 0) {
    const size = q.length;
    for (let i = 0; i < size; i++) {
      const cur = q.shift();
      console.log(cur.node.val + ` depth: ${cur.depth}`);
      for (let j = 0; j < cur.node.children.length; j++) {
        q.push(new State(cur.node.children[j], cur.depth + j));
      }
    }
  }
}

二叉搜索树

利用 BST 左小右大的特性，可以迅速定位到目标节点，理想的时间复杂度是树的高度 O(logN)，而普通的二叉树遍历函数则需要 O(N) 的时间遍历所有节点。

至于其他增、删、改的操作，你首先查到目标节点，才能进行增删改的操作对吧？增删改的操作无非就是改一改指针，所以增删改的时间复杂度也是 O(logN)。

TreeMap/TreeSet 实现原理

HashMap 底层把键值对存储在一个 table 数组里面，而 TreeMap 底层把键值对存储在一棵二叉搜索树的节点里面。

至于 TreeSet，它和 TreeMap 的关系正如哈希表 HashMap 和哈希集合 HashSet 的关系一样，就是 TreeMap 的简单封装。

下面只介绍 TreeMap 各方法和实现思路，具体实现代码后续补充。

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
class TreeMap {
  /**
   * 插入键值对。
   * @param {any} k - 键
   * @param {any} v - 值
   */
  put(k, v) { }

  /**
   * 根据键获取值。
   * @param {any} k - 键
   * @returns {any} 值
   */
  get(k) { }

  /**
   * 删除键值对。
   */
  remove() { }

  /**
   * 检查是否包含指定键。
   * @param {any} k - 键
   * @returns {boolean} 是否包含该键
   */
  containsKey(k) { }

  /**
   * 获取所有键。
   * @returns {Array<any>} 键的数组
   */
  keys() { }

  /**
   * 获取最小键。
   * @returns {any} 最小键。
   */
  firstKey() { }

  /**
   * 获取最大键。
   * @returns {any} 最大键
   */
  lastKey() { }

  /**
   * 获取小于或等于指定键的最大键。
   * @param {any} k - 键
   * @returns {any} 小于或等于指定键的最大键
   */
  floorKey(k) { }

  /**
   * 获取大于或等于指定键的最小键。
   * @param {any} k - 键
   * @returns {any} 大于或等于指定键的最小键
   */
  ceilingKey(k) { }

  /**
   * 获取排名为n的键。
   * @param {number} nth - 第n名
   * @returns {any} 为n的键
   */
  selectKey(nth) { }

  /**
   * 获取指定键的排名。
   * @param {any} k - 键
   * @returns {number} 排名
   */
  rank(k) { }

  /**
   * 获取键的范围。
   * @param {any} low - 范围的低端
   * @param {any} high - 范围的高端
   * @returns {Array<any>} 键的范围数组
   */
  rangeKeys(low, high) { }
}

  • put get remove containsKey

    • 直接通过二叉搜索树的特性搜索，复杂度为 O(logN)

  • floorKey ceilingKey

    • 类似于 get，通过二叉搜索树的特性搜索，复杂度为 O(logN)

  • firstKey lastKey

    • 从 BST 的根节点开始，一直往左走，最后遇到的非空节点就是最小的节点；同理，一直往右走，最后遇到的非空节点就是最大的节点。

  • keys

    • 直接中序遍历二叉搜索树，复杂度为 O(N)，得到的结果就是有序的

  • selectKey rank

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    class TreeNode {
      constructor(key, value) {
        this.key = key;
        this.value = value;
        this.left = null;
        this.right = null;
        
        // 给节点增加一个属性，表示以当前节点为根节点的树的节点数量
        this.size = size; 
      }
    }
    • 这样一来，selectKey 就可以利用这个 size 字段把时间复杂度降到 O(logN) 了。因为 size 维护的就是当前节点为根的整棵树上有多少个节点，加上 BST 左小右大的特性，那么一个节点的排名其实就是左子树的节点总数加上 1。

性能问题

上述搜索算法复杂度为 O(logN) 前提是二叉树要是平衡的如下：

1
2
3
4
5
    7
   / \
  4   9
 / \   \
1   5   10

如果二叉树像下面这样是这样的，那么搜索 10 的时间复杂度就是 O(N) 了，因为这棵树就是一个链表，搜索 10 就要遍历整个链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
1
 \
  2
   \
    3
     \
      4
       \
        5
         \
          6
           \
            7
             \
              8
               \
                9
                 \
                  10

二叉堆原理

二叉堆的关键应用是优先级队列。

要理解以下关键点：

  1. 优先级队列是一种能够自动排序的数据结构，增删元素的复杂度是 O(logN)，底层使用二叉堆实现。
  2. 二叉堆是一种拥有特殊性质的完全二叉树。
  3. 优先级队列（二叉堆）的核心方法是 swim 和 sink，用来维护二叉堆的性质。

二叉堆的主要应用有两个，首先是一种很有用的数据结构优先级队列（Priority Queue），第二是一种排序方法堆排序（Heap Sort）。

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
// 优先级队列
class PriorityQueue {
  // 在二叉堆堆顶插入一个元素，时间复杂度 O(logN)
  // N 为当前二叉堆中的元素个数
  push(x) {}

  // 返回堆顶元素，时间复杂度 O(1)
  // 该堆顶元素就是二叉堆中的最大值或最小值，取决于是最大堆还是最小堆
  peek() {}

  // 删除堆顶元素，时间复杂度 O(logN)
  pop() {}

  // 返回堆中元素的个数，时间复杂度 O(1)
  size() {}
}

// 堆排序
// 堆排序伪码，对 arr 原地排序
// 时间复杂度 O(NlogN)，空间复杂度 O(N)
const heapSort = function(arr) {
    const res = new Array(arr.length);
    const pq = new PriorityQueue();
    for (let x of arr)
        pq.push(x);
    // 元素出堆的顺序是有序的
    for (let i = 0; i < arr.length; i++)
        res[i] = pq.pop();
    return res;
}

线段树核心原理

1
2
3
4
5
6
7
8
9
10
11
12
13
// 核心API
class SegmentTree {
  // 构造函数，给定一个数组，初始化线段树，时间复杂度 O(N)
  // merge 是一个函数，用于定义 query 方法的行为
  // 通过修改这个函数，可以让 query 函数返回区间的元素和、最大值、最小值等
  constructor(nums, merge) { }

  // 查询闭区间 [i, j] 的元素和（也可能是最大最小值，取决于 merge 函数），时间复杂度 O(logN)
  query(i, j) { }

  // 更新 nums[i] = val，时间复杂度 O(logN)
  update(i, val) { }
}
  • 树高
    • 最简单的线段树构造方法，是递归地将 nums 数组从正中间切分，然后递归地将左右子数组构造成线段树，直到区间长度为 1。
    • 由于每次递归构造线段树都是从正中间切分的，左右子树的元素个数基本相同，所以整棵二叉树是平衡的，即树高是 O(logN)，其中 N 是 nums 数组的元素个数。
  • query
    • 树的高度为 O(logN)，query 方法的本质是从根节点开始遍历这棵二叉树，需要遍历的节点个数是 logN 的常数倍，所以 query 方法的时间复杂度是 O(logN)。
    • 如果恰好有一个非叶子节点记录着区间 [i, j] 的元素和，那么就可以直接返回；如果没有，[i, j] 区间会被分裂成两个子区间，递归查询左右子区间的元素和，然后合并结果。
  • update
    • 数组元素就是叶子节点，update 方法的本质是修改叶子节点的值，顺带会更新从根节点到该叶子节点的路径上的所有非叶子节点的值。因为树高为 O(logN)，所以 update 方法的时间复杂度也是 O(logN)。

图结构

一幅图是由节点（Vertex）和边（Edge）构成的，逻辑结构如下：

1
2
3
4
5
// 图节点的逻辑结构
const Vertex = function(id, neighbors) {
    this.id = id;
    this.neighbors = neighbors;
};
  • 度
    • 无向图中，度就是每个节点相连的边的条数。由于有向图的边有方向，所以有向图中每个节点的度被细分为入度（indegree）和出度（outdegree）。

邻接表和邻接矩阵实现图结构

用邻接表和邻接矩阵的存储方式分别如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
邻接表

- [ ] [4, 3, 1]
- [ ] [3, 2, 4]
- [ ] [3]
- [ ] [4]

邻接矩阵

   0  1  2  3  4
0     x     x  x
1        x  x  x
2           x
3              x
4

邻接表很直观，我把每个节点 x 的邻居都存到一个列表里，然后把 x 和这个列表映射起来，这样就可以通过一个节点 x 找到它的所有相邻节点。

邻接矩阵则是一个二维布尔数组，我们权且称为 matrix，如果节点 x 和 y 是相连的，那么就把 matrix[x][y] 设为 true。如果想找节点 x 的邻居，去扫一圈 matrix[x][...] 就行了。

1
2
3
4
5
6
7
// 邻接表
// graph[x] 存储 x 的所有邻居节点
const graph: number[][] = [];

// 邻接矩阵
// matrix[x][y] 记录 x 是否有一条指向 y 的边
const matrix: boolean[][] = [];

注意分析两种存储方式的空间复杂度，对于一幅有 V 个节点，E 条边的图，邻接表 的空间复杂度是 O(V+E)，而 邻接矩阵 的空间复杂度是 O(V^2)。

所以如果一幅图的 E 远小于 V^2（稀疏图），那么 邻接表 会比 邻接矩阵 节省空间，反之，如果 E 接近 V^2（稠密图），二者就差不多了。

在后面的图算法和习题中，大多都是稀疏图，所以你会看到 邻接表 的使用更多一些。

邻接矩阵 的最大优势在于，矩阵是一个强有力的数学工具，图的一些隐晦性质可以借助精妙的矩阵运算展现出来。

不同种类的图结构

  • 加权图
    • 图中的边有权重，这种图叫做加权图。邻接表形式可以不仅仅存储某个节点 x 的所有邻居节点，还存储 x 到每个邻居的权重。
    • 邻接矩阵，matrix[x][y] 不再是布尔值，而是一个 int 值，0 表示没有连接，其他值表示权重。
  • 无向图
    • 无向图的边是没有方向的，即边 (x, y) 和边 (y, x) 是等价的。
    • 实现时可以把无向图的边看成两个有向图的边，即 (x, y) 和 (y, x) 都存储。

图结构的通用代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Graph {
  // 添加一条边（带权重）
  addEdge(from, to, weight) {}

  // 删除一条边
  removeEdge(from, to) {}

  // 判断两个节点是否相邻
  hasEdge(from, to) {}

  // 返回一条边的权重
  weight(from, to) {}

  // 返回某个节点的所有邻居节点和对应权重
  neighbors(v) {}

  // 返回节点总数
  size() {}
}
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
// 加权有向图的通用实现（邻接表）
class WeightedDigraph {
  constructor(n) {
    this.graph = Array.from({ length: n }, () => [])
  }

  addEdge(from, to, weight) {
    this.graph[from].push({ to, weight })
  }

  removeEdge(from, to) {
    this.graph[from] = this.graph[from].filter(node => node.to !== to)
  }

  hasEdge(from, to) {
    return this.graph[from].some(node => node.to === to)
  }

  weight(from, to) {
    const edge = this.graph[from].find(node => node.to === to);
    return edge ? edge.weight : 'no such edge';
  }

  neighbors(from) {
    return this.graph[from]
  }
}

//加权有向图的通用实现（邻接矩阵）
class WeightedDigraphMatrix {
  constructor(n) {
    this.graph = Array.from({ length: n }, () => Array(n).fill(0))
  }

  addEdge(from, to, weight) {
    this.graph[from][to] = weight
  }

  removeEdge(from, to) {
    this.graph[from][to] = 0
  }

  hasEdge(from, to) {
    return this.graph[from][to] !== 0
  }

  weight(from, to) {
    return this.graph[from][to] ? this.graph[from][to] : 'no such edge'
  }

  neighbors(from) {
    const res = []
    for (let to = 0; to < this.graph[from].length; to++) {
      if (this.graph[from][to] !== 0) {
        res.push({ to, weight: this.graph[from][to] })
      }
    }
    return res
  }
}

// 测试代码
const graph = new WeightedDigraph(3);
graph.addEdge(0, 1, 1);
graph.addEdge(1, 2, 2);
graph.addEdge(2, 0, 3);
graph.addEdge(2, 1, 4);

console.log(graph.hasEdge(0, 1)); // true
console.log(graph.hasEdge(1, 0)); // false

graph.neighbors(2).forEach(function(edge) {
    console.log(2 + " -> " + edge.to + ", weight: " + edge.weight);
});
// 2 -> 0, weight: 3
// 2 -> 1, weight: 4

graph.removeEdge(0, 1);
console.log(graph.hasEdge(0, 1)); // false
  • 有向无权图
    • 将权重设置为默认值 1 即可。
  • 无向加权图
    • addEdge 时，同时添加两条边，(from, to) 和 (to, from)，权重相同。
  • 无向无权图
    • addEdge 时，同时添加两条边，(from, to) 和 (to, from)，权重都为 1。

图的遍历

图的遍历和树的遍历很像，都是从一个节点出发，访问它的邻居节点，然后递归地访问邻居的邻居。所以直接给出相关的模板代码，根据算法题的具体要求，稍作修改即可。

DFS
遍历所有节点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 图的遍历框架
// 需要一个 visited 数组记录被遍历过的节点
// 避免走回头路陷入死循环
const traverseGraph = function(s, visited) {
    // base case
    if (s === null) {
        return;
    }
    if (visited[s.id]) {
        // 防止死循环
        return;
    }
    // 前序位置
    visited[s.id] = true;
    console.log("visit " + s.id);
    for (let i = 0; i < s.neighbors.length; i++) {
        traverseGraph(s.neighbors[i]);
    }
    // 后序位置
};
遍历所有路径
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
// 下面的算法代码可以遍历图的所有路径，寻找从 src 到 dest 的所有路径

// onPath 和 path 记录当前递归路径上的节点
const onPath = new Array(graph.size()).fill(false);
const path = [];
const traverse = function(graph, src, dest) {
    // base case
    if (src < 0 || src >= graph.size()) {
        return;
    }
    if (onPath[src]) {
        // 防止死循环（成环）
        return;
    }
    // 前序位置
    onPath[src] = true;
    path.push(src);
    if (src === dest) {
        console.log("find path: " + path);
    }
    for (let e of graph.neighbors(src)) {
        traverse(graph, e.to, dest);
    }
    // 后序位置
    path.pop();
    onPath[src] = false;
}
BFS
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
// 图结构的 BFS 遍历，从节点 s 开始进行 BFS
const bfs = (graph, s) => {
  const visited = []
  const q = []
  q.push(s)
  visited[s] = true

  while (q.length) {
    const cur = q.shift()
    console.log("visit " + cur);
    const neighbors = graph.neighbors(cur)
    for (let i = 0; i < neighbors.length; i++) {
      const e = neighbors[i]
      if (!visited[e.to]) {
        q.push(e.to)
        visited[e.to] = true
      }
    }
  }
}

// 从 s 开始 BFS 遍历图的所有节点，且记录遍历的步数
const bfsWithStep = (graph, s) => {
  const visited = []
  const q = []
  q.push(s)
  visited[s] = true
  let step = 0

  while (q.length) {
    const size = q.length
    for (let i = 0; i < size; i++) {
      const cur = q.shift()
      console.log("visit " + cur, "step " + step);
      const neighbors = graph.neighbors(cur)
      for (let i = 0; i < neighbors.length; i++) {
        const e = neighbors[i]
        if (!visited[e.to]) {
          q.push(e.to)
          visited[e.to] = true
        }
      }
    }
    step++
  }
}

// 从 s 开始 BFS 遍历图的所有节点，且记录权重
class State {
  constructor(node, weight) {
    this.node = node;
    this.weight = weight;
  }
}

const bfsWithWeight = (graph, s) => {
  const visited = []
  const q = []
  q.push(new State(s, 0))
  visited[s] = true

  while (q.length) {
    const size = q.length
    for (let i = 0; i < size; i++) {
      const cur = q.shift()
      console.log("visit " + cur, "step " + step);
      const neighbors = graph.neighbors(cur.node)
      for (let i = 0; i < neighbors.length; i++) {
        const e = neighbors[i]
        if (!visited[e.to]) {
          q.push(new State(e.to, cur.weight + e.weight))
          visited[e.to] = true
        }
      }
    }
  }
}

刷题

链表

双指针链表题目：

单链表的一个进阶技巧是递归操作单链表(将单链表抽象成一个只有一个子树的树，即可使用二叉树的前序后序遍历思维来递归反转链表)，不过这种思路一般用于面试时说一下就行，笔试时就用标准的指针操作即可

递归的思想相对迭代思想，稍微有点难以理解，处理的技巧是：不要跳进递归，而是利用明确的定义来实现算法逻辑。处理看起来比较困难的问题，可以尝试化整为零，把一些简单的解法进行修改，解决困难的问题。

数组

滑动窗口题目

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
// 滑动窗口框架
// 滑动窗口算法伪码框架
const slidingWindow = function(s) {
    // 用合适的数据结构记录窗口中的数据，根据具体场景变通
    // 比如说，我想记录窗口中元素出现的次数，就用 map
    // 如果我想记录窗口中的元素和，就可以只用一个 int
  const window = ...;

  let left = 0, right = 0;
  while (right < s.length) {
    // c 是将移入窗口的字符
    const c = s[right];
    window.add(c);
    // 增大窗口
    right++;
    // 进行窗口内数据的一系列更新
    ...

    // *** debug 输出的位置 ***
    // 注意在最终的解法代码中不要 print
    // 因为 IO 操作很耗时，可能导致超时
    console.log("window: [%d, %d)\n", left, right);
    // *********************

    // 判断左侧窗口是否要收缩
    while (window needs shrink) {
      // d 是将移出窗口的字符
      const d = s[left];
      window.remove(d);
      // 缩小窗口
      left++;
      // 进行窗口内数据的一系列更新
      ...
    }
  }
};

滑动窗口记住

  1. 什么时候应该扩大窗口？

  2. 什么时候应该缩小窗口？

  3. 什么时候应该更新答案？

强化练习：

二分搜索

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
var binary_search = function (nums, target) {
  var left = 0, right = nums.length - 1;
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 直接返回
      return mid;
    }
  }
  // 直接返回
  return -1;
}

var left_bound = function (nums, target) {
  var left = 0, right = nums.length - 1;
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 别返回，锁定左侧边界
      right = mid - 1;
    }
  }
  // 判断 target 是否存在于 nums 中
  if (left < 0 || left >= nums.length) {
    return -1;
  }
  // 判断一下 nums[left] 是不是 target
  return nums[left] == target ? left : -1;
}

var right_bound = function (nums, target) {
  var left = 0, right = nums.length - 1;
  while (left <= right) {
    var mid = left + Math.floor((right - left) / 2);
    if (nums[mid] < target) {
      left = mid + 1;
    } else if (nums[mid] > target) {
      right = mid - 1;
    } else if (nums[mid] == target) {
      // 别返回，锁定右侧边界
      left = mid + 1;
    }
  }
  // 由于 while 的结束条件是 right == left - 1，且现在在求右边界
  // 所以用 right 替代 left - 1 更好记
  if (right < 0 || right >= nums.length) {
    return -1;
  }
  return nums[right] == target ? right : -1;
}

想要用二分搜索算法解决问题，分为以下几步：

  1. 确定 x, f(x), target 分别是什么，并写出函数 f 的代码。
  2. 找到 x 的取值范围作为二分搜索的搜索区间，初始化 left 和 right 变量。
  3. 根据题目的要求，确定应该使用搜索左侧还是搜索右侧的二分搜索算法，写出解法代码。

前缀和数组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
const NumArray = function(nums) {
  // 前缀和数组
  let preSum = new Array(nums.length + 1).fill(0);

  // preSum[0] = 0，便于计算累加和
  preSum[0] = 0;

  // 输入一个数组，构造前缀和
  for (let i = 1; i < preSum.length; i++) {
    // 计算 nums 的累加和
    preSum[i] = preSum[i - 1] + nums[i - 1];
  }

  this.preSum = preSum;
};

// 查询闭区间 [left, right] 的累加和
NumArray.prototype.sumRange = function(left, right) {
  return this.preSum[right + 1] - this.preSum[left];
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const NumMatrix = function(matrix) {
  let m = matrix.length, n = matrix[0].length;
  // preSum[i][j] 记录矩阵 [0, 0, i-1, j-1] 的元素和
  this.preSum = Array.from({length: m + 1}, () => Array(n + 1).fill(0));
  if (m == 0 || n == 0) return;
  // 构造前缀和矩阵
  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      // 计算每个矩阵 [0, 0, i, j] 的元素和
      this.preSum[i][j] = this.preSum[i-1][j] + this.preSum[i][j-1] + matrix[i - 1][j - 1] - this.preSum[i-1][j-1];
    }
  }
};

NumMatrix.prototype.sumRegion = function(x1, y1, x2, y2) {
  // 计算子矩阵 [x1, y1, x2, y2] 的元素和
  // 目标矩阵之和由四个相邻矩阵运算获得
  return this.preSum[x2+1][y2+1] - this.preSum[x1][y2+1] - this.preSum[x2+1][y1] + this.preSum[x1][y1];
};

差分数组

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
class Difference {
  constructor(nums) {
    // 差分数组
    this.diff = new Array(nums.length);
    // 根据初始数组构造差分数组
    this.diff[0] = nums[0];
    for (let i = 1; i < nums.length; i++) {
        this.diff[i] = nums[i] - nums[i - 1];
    }
  }

  // 给闭区间 [i, j] 增加 val（可以是负数）
  increment(i, j, val) {
    this.diff[i] += val;
    if (j + 1 < this.diff.length) {
      this.diff[j + 1] -= val;
    }
  }

  // 返回结果数组
  result() {
    let res = new Array(this.diff.length);
    // 根据差分数组构造结果数组
    res[0] = this.diff[0];
    for (let i = 1; i < this.diff.length; i++) {
      res[i] = res[i - 1] + this.diff[i];
    }
    return res;
  }
}

队列/栈

栈习题

队列习题

单调栈

单调队列

二叉树 & 递归思想

递归思维模式

  1. 首先，这个问题是否可以抽象成一棵树结构？如果可以，那么就要用递归算法了。

  2. 如果要用递归算法，那么就思考「遍历」和「分解问题」这两种思维模式，看看哪种更适合这个问题。

  3. 如果用「分解问题」的思维模式，那么一定要写清楚这个递归函数的定义是什么，然后利用这个定义来分解问题，利用子问题的答案推导原问题的答案；如果用「遍历」的思维模式，那么要用一个无返回值的递归函数，单纯起到遍历递归树，收集目标结果的作用。

二叉树解题思维模式

  1. 是否可以通过遍历一颗二叉树解答？如果可以，用一个 traverse 函数配合外部变量来实现，这叫「遍历」的思维模式。
  2. 是否可以通过定义一个递归函数，通过子问题（子树）答案推导出原问题答案？如果可以，写出这个递归函数的定义，并充分利用这个函数的返回值，这叫「分解问题」的思维模式。
  3. 如果单独抽出一个二叉树节点，它需要做什么事情？需要在什么时候（前/中/后序位置）做？
  4. 只有后序位置才能通过返回值获取子树的信息。一旦你发现题目和子树有关，那大概率要给函数设置合理的定义和返回值，在后序位置写代码了。
2025-02-05 该篇文章被 半见 打上标签: 算法 归为分类: 程序员

下一篇：oh-my-zsh 配置
以上
© 2018-2025 China
🌑梦里不觉秋已深，余情岂是为他人 本站由Hexo驱动｜使用Hexo-theme-A4主题