data-structure.md

Table of Contents generated with DocToc

• JavaScript 数据结构
  • 堆，栈，队列
    • 堆，heap
    • 栈，stack
    • 队列，queue
  • 链表
  • 集合与字典（映射）
    • 集合
    • 字典（映射）
  • 散列
  • 二叉树
    • 二叉搜索树（BST）
    • 前驱和后继
    • BST 的遍历
      • 前序遍历（preorder）
      • 中序遍历（inorder）
      • 后序遍历（postorder）
      • 层序遍历（level-order）
  • 图
    • 图的遍历
  • 并查集 Union Find
  • 深度优先搜索 DFS/Depth-First-Search
  • 广度优先搜索 BFS/Breadth-First-Search
  • 算法基本概念
    • 复杂度 - 大 O 表示法
    • 动态规划
    • 字符串问题

JavaScript 数据结构

堆，栈，队列

堆和栈：https://blog.csdn.net/K346K346/article/details/80849966

堆，heap

堆是满足一定限制的树型结构。关于二叉堆的更多实现细节，查看优先队列

LeetCode 上相关题目：

1. No.23 Merge k Sorted Lists
2. No.179 Largest Number
3. No.215 Kth Largest Element in an Array
4. No.264 Ugly Number II
5. No.347 Top K Frequent Elements
6. No.451 Sort Characters By Frequency

栈，stack

栈又称堆栈，是一种先进后出（FILO - First in Lirst out，也可以是后进先出 LIFO - Last in First out）的有序集合

LeetCode 上相关题目：

1. No.20 Valid Parentheses
2. No.42 Trapping Rain Water
3. No.71 Simplify Path
4. No.84 Largest Rectangle in Histogram
5. No.85 Maximal Rectangle
6. No.94 Binary Tree Inorder Traversal
7. No.103 Binary Tree Zigzag Level Order Traversal
8. No.144 Binary Tree Preorder Traversal
9. No.145 Binary Tree Postorder Traversal
10. No.150 Evaluate Reverse Polish Notation
11. No.155 Min Stack
12. No.173 Binary Search Tree Iterator
13. No.225 Implement Stack using Queues
14. No.232 Implement Queue using Stacks

队列，queue

队列是一种先进先出（FIFO, First in first out）的有序集合

LeetCode 上相关题目：

1. No.621 Task Scheduler
2. No.622 Design Circular Queue
3. No.641 Design Circular Deque
4. 面试题 09. 用两个栈实现队列

链表

链表储存有序的元素集合，其中的元素在内存中不是连续放置的。对于单向链表，每个元素由一个储存元素本身的节点和一个指向下一个元素的引用组成；而双向链表中的各元素则多了一个指向上一个元素的引用

链表的存在有什么意义呢？

对于传统的数组而言，我们增加或删除一个元素时，需要移动其之后的元素。比如删除了 index 为 10 的元素，那么之前 index 为 11 的元素需要向前挪动一位；同理，后面的每一个元素都要向前挪动一位。

除此以外，链表和数组的又一个差别是，数组可以直接通过 array[index] 访问到 index 位上的元素；而对于链表而言，需要从头开始遍历到目标元素。

由此可知，当我们在单向链表中某个位置上插入一个元素 node 时：

1. 遍历查找到位于 index 的元素 current，以及它的上一位元素 previous
2. 将 previous 的 next 指向 node
3. 将 node 的 next 指向 current

同理，删除某个位置上的元素，即是将该位置的上一个元素的 next 指向了该位置的下一位元素。

对于双向链表而言，则多了设置 pre 指向上一个元素的一步。

LeetCode 上相关题目：

1. No.2 Add Two Numbers
2. No.19 Remove Nth Node From End of List - Two pointers
3. No.21 Merge Two Sorted Lists
4. No.23 Merge k Sorted Lists
5. No.24 Swap Nodes in Pairs
6. No.25 Reverse Nodes in k-Group
7. No.61 Rotate List
8. No.82 Remove Duplicates from Sorted List II
9. No.83 Remove Duplicates from Sorted List
10. No.86 Partition List
11. No.92 Reverse Linked List II
12. No.109 Convert Sorted List to Binary Search Tree
13. No.138 Copy List with Random Pointer
14. No.141 Linked List Cycle
15. No.142 Linked List Cycle II
16. No.143 Reorder List
17. No.147 Insertion Sort List
18. No.148 Sort List
19. No.160 Intersection of Two Linked Lists
20. No.206 Reverse Linked List
21. No.445 Add Two Numbers II

集合与字典（映射）

LeetCode 上相关题目：

1. No.560 Subarray Sum Equals K

集合

集合中的元素无序且唯一。可以按照插入元素的顺序来迭代集合中的各元素。

在 ES6 原生 API 中，支持了 Set 和 WeakSet。但要注意的一点是，尽管 Set 中的值是唯一的，且 JS 中 NaN !== NaN ，但在 Set 里 NaN 仍被认为是相同的值。除此以外，集合中以 value, value 的形式储存数据，即保存的 value 也会作为它本身的 key 便于索引查找。

字典（映射）

与 Set 中 value 做 key 不同，字典 Map 需要给 value 制定一个 key 。它也用来储存不重复的数据。

在 ES6 原生 API 中，有 Map 以及 WeakMap 两种字典。

---

Set、 Map 相对于列表的优点在于，当需要储存较多数据时，不会因为其中某个元素的增删而影响到后面其他元素的索引（这一点优势链表也具有），同时，如果需要查找是否存在某个元素，则 Set、 Map 可以很快的进行判断，而列表则需要对元素进行遍历。

在 lodash 中，有 SetCache 对象。当数据元素个数大于设定的一定值时，会将数组转化到 SetCache 中，在底层其实就是将数组转换为了 key: value 的键值对，可以大大增快其索引速度。

WeakMap 和 WeakSet 相比较于 Map 和 Set 而言：

• WeakMap 和 WeakSet 对象中只能存放对象值, 不能存放原始值, 而 Map 和 Set 都可以
• WeakMap 和 WeakSet 对象中存储的对象值都是被弱引用的, 如果没有其他的变量或属性引用这个对象值, 则这个对象值会被当成垃圾回收掉。
• 因此，WeakMap 和 WeakSet 对象是无法被枚举的, 没有办法拿到它包含的所有元素

散列

LeetCode 上相关题目：

1. No.1 Two Sum
2. No.3 Longest Substring Without Repeating Characters
3. No.18 4Sum
4. No.30 Substring with Concatenation of All Words
5. No.36 Valid Sudoku
6. No.37 Sudoku Solver
7. No.49 Group Anagrams
8. No.76 Minimum Window Substring
9. No.85 Maximal Rectangle
10. No.94 Binary Tree Inorder Traversal
11. No.136 Single Number
12. No.138 Copy List with Random Pointer
13. No.166 Fraction to Recurring Decimal
14. No.204 Count Primes
15. No.217 Contains Duplicate
16. No.219 Contains Duplicate II
17. No.389 Find the Difference
18. No.599 Minimum Index Sum of Two Lists

HashTable（或 HashMap ）。对散列中的元素而言，拥有一个特殊的键值（通常通过元素的 ASCII 码获取到），以此来增加索引的速度。除此以外，在删除某个元素以后，散列对该键的索引值将指向 undefined ，也就因此避免了改变其他元素的位置。

但其实有时候，不同元素计算得到的 key 依旧会有重复。如果是不加处理的普通散列，则当 key 重复时，后加入的元素会覆盖原有的元素。但我们可以通过分离链接 或者 线性探索 的方法解决这个问题。

• 分离链接

散列中的每一个 key 都指向一个链表；对于每个新增的元素，都会 push 到相对应的引用中去。这也就避免了元素 key 重复的问题，但很显然：占用了多余的储存空间。

• 线性探索

当想向表中某位置加入一个新元素时，如果索引为 index 的位置已经被其他元素占据了，则尝试 index + 1 的位置。如果仍然被占据，则继续尝试 index + 2 的位置；以此类推。

二叉树

如其名，是一个树状的数据结构，由很多节点组成，各节点可以有祖先节点（父节点等）和后代节点（子节点等）。节点的深度取决于它祖先节点的数量；树的深度则取决于所有节点深度的最大值。

二叉搜索树（BST）

二叉树的一种。只允许在节点的左侧储存比父节点小的值，在右侧储存比父节点大的值。由此可知：

• 遍历 BST，每个节点只取其左侧的子节点进行递归，直至没有子节点。最终所得的数是树中的最小值。
• 遍历 BST，每个节点只取其右侧的子节点进行递归，直至没有子节点。最终所得的数是树中的最大值。

前驱和后继

• 某节点 A 的前驱节点：节点值小于当前节点值 A，且值最大的节点。即左子树的最右节点
• 某节点 B 的后继节点：节点值大于当前节点值 B，且值最小的节点。即右子树的最左节点

前驱和后继要结合遍历顺序来谈，某个节点在特定遍历顺序下，序列中的前后两个节点就是它的前驱和后继。如二叉树：

      1
  2       3
4  5    6   7

以结点 2 为例，

• 前序遍历下，遍历序列为 1 2 4 5 3 6 7，故前驱和后继为 1、4
• 中序遍历下，遍历序列为 4 2 5 1 6 3 7，故前驱和后继为 4、5
• 后序遍历下，遍历序列为 4 5 2 6 7 3 1，故前驱和后继为 5、6

BST 的遍历

前序遍历（preorder）

先访问父节点，再访问其所有子节点。即中左右顺序。LeetCode 中相关题目：

1. No.144 Binary Tree Preorder Traversal
2. No.105 Construct Binary Tree from Preorder and Inorder Traversal

中序遍历（inorder）

按照从最小到最大的顺序访问二叉树中的各节点。即对于每个节点，先遍历左子节点，然后根节点，最后右子节点。LeetCode 中相关题目：

1. No.94 Binary Tree Inorder Traversal
2. No.99 Recover Binary Search Tree
3. No.173 Binary Search Tree Iterator
4. No.105 Construct Binary Tree from Preorder and Inorder Traversal
5. No.106 Construct Binary Tree from Inorder and Postorder Traversal.js
6. No285. Inorder Successor in BST.js

后序遍历（postorder）

先访问所有子节点，再访问父节点。即左右中。LeetCode 中相关题目：

1. No.145 Binary Tree Postorder Traversal
2. No.106 Construct Binary Tree from Inorder and Postorder Traversal.js

对于前/中/后序三种遍历，都可以通过三种形式实现：

1. 递归：实现方式最简单，O(n) 空间复杂度
2. 循环：实现方式较递归稍复杂，利用堆/队列，O(n) 空间复杂度
3. Morris 算法：最优，O(1) 空间复杂度：Morris Traversal方法遍历二叉树（非递归，不用栈，O(1)空间）

查看

• 前序遍历的递归/循环/Morris Traversal 实现
• 中序遍历的递归/循环/Morris Traversal 实现
• 后序遍历的递归/循环/Morris Traversal 实现

二叉树复原：

• No105. 从前序与中序遍历序列构造二叉树
• No106. 从中序与后序遍历序列构造二叉树
• No889. 根据前序和后序遍历构造二叉树
• No1008. 先序遍历构造二叉树
• No1028. 从先序遍历还原二叉树

层序遍历（level-order）

每次遍历二叉树的一层，遍历完当前层后再进行下一层的遍历 -> 广度优先算法

1. No.102 Binary Tree Level-Order Traversal
2. No.107 Binary Tree Level-Order Traversal II.js
3. No.103 Binary Tree Zigzag Level-Order Traversal.js

LeetCode 上相关题目：

1. No208 Implement Trie Prefix Tree
2. No212 Word Search II
3. No676 Implement Magic Dictionary

图

图是一种由边连接的节点（或顶点）。

• 相邻顶点：由一条边连接在一起的两个顶点
• 顶点的度：该顶点相邻顶点的数量
• 简单路径：不包含重复顶点的路径
• 环：简单路径的一种，表示从某顶点起始，不经过重复顶点，仍能回到初始顶点
• 无环：图中不存在环
• 连通：图中每两个顶点间都存在路径
• 强连通：图中每两个顶点间在双向上都存在路径

图可以通过邻接表这样的数据结构来表示。在邻接表中，用列表、链表或者散列来储存所有的顶点，并可以使用字典来储存顶点: [顶点所有的邻接顶点]

图的遍历

图的遍历思想是，追踪每一个第一次访问的节点，并且追踪有哪些节点还没被完全探索过（该顶点的每条边都被查看过则算完全探索）。

1. 一开始，所有顶点被储存至待访问顶点列表中，并被标记为未查看。
2. 每经过一个顶点，将其标记为已查看，未完全探索。
3. 待与该顶点相连的所有变都经过以后，将该顶点标记为已完全探索。
4. 每个顶点至多访问两次（未查看 -> 已查看，已查看 -> 已完全探索）

LeetCode 上相关题目：

1. No.133 Clone Graph

并查集 Union Find

深度优先搜索 DFS/Depth-First-Search

深度优先搜索：栈的形式储存待访问顶点，元素后入先出。

从指定的第一个顶点开始遍历图，沿着某路径直到最后一个顶点；然后原路退回后搜索下一个路径。即先深入访问，再增加广度。

基本搜索过程：

1. 从某顶点（V）开始搜索，并标注为已查看，未完全探索

2. 获取其所有未访问邻节点，放入栈中

   2.1. 依次访问邻节点，后入的邻节点先被取出

   2.2. 对每个邻节点重复 1 的操作（递归）

3. 邻节点访问完毕之后，标注 V 为已完全探索

// 常见遍历式 DFS
const data = {} // something..
const queue = [data]

while (queue.length) {
  const item = queue.pop()

  // 针对某节点遍历到最底部
  for (const something of item.next()) {
    queue.push(something)
  }
}

LeetCode 上 DFS 相关题目：

1. No.98 Validate Binary Search Tree
2. No.100 Same Tree
3. No.101 Symmetric Tree
4. No.104 Maximum Depth of Binary Tree
5. No.105 Construct Binary Tree from Preorder and Inorder Traversal
6. No.106 Construct Binary Tree from Inorder and Postorder Traversal
7. No.108 Convert Sorted Array to Binary Search Tree
8. No.109 Convert Sorted List to Binary Search Tree
9. No.110 Balanced Binary Tree
10. No.111 Minimum Depth of Binary Tree
11. No.112 Path Sum
12. No.113 Path Sum II
13. No.114 Flatten Binary Tree to Linked List
14. No.116 Populating Next Right Pointers in Each Node
15. No.117 Populating Next Right Pointers in Each Node II
16. No.124 Binary Tree Maximum Path Sum
17. No.129 Sum Root to Leaf Numbers
18. No.130 Surrounded Regions
19. No.133 Clone Graph

广度优先搜索 BFS/Breadth-First-Search

广度优先搜索：队列的形式储存待访问顶点，元素先入先出。

从指定的第一个顶点开始遍历图，先访问所有的相邻点，即访问图的一层，然后深入到下一层进行递归。

基本搜索过程：

1. 创建队列 Queue

2. 将某节点（V）放入队列

   2.1. 按照先入先出的顺序，取出节点 V

   2.2. 将节点 V 标注为已查看，未完全探索

   2.3. 取出 V 的所有未访问邻节点，放入队列

   2.4. 将 V 标注为已完全探索

// 常见遍历式 BFS
const data = {} // something..
const queue = [data]

while (queue.length) {
  let len = queue.length
  // 每次处理一层
  while (len) {
    const item = queue.shift()

    for (const something of item.next()) {
      queue.push(something)
    }

    len -= 1
  }
}

LeetCode 上 BFS 相关题目：

1. No.101 Symmetric Tree
2. No.102 Binary Tree Level Order Traversal
3. No.103 Binary Tree Zigzag Level Order Traversal
4. No.107 Binary Tree Level Order Traversal II
5. No.111 Minimum Depth of Binary Tree
6. No.126 Word Ladder II
7. No.127 Word Ladder
8. No.130 Surrounded Regions
9. No.133 Clone Graph
10. No.279 Perfect Squares

算法基本概念

复杂度 - 大 O 表示法

通常，我们会综合考虑 CPU 占用、内存占用、硬盘占用、网络占用等多种情况来判断一个算法的好坏。综合起来后，使用时间复杂度这个概念来代表算法执行速度，以此进行衡量。

但一个算法的执行时间并不是固定的。总会有最佳、平均、最坏情况出现。而时间复杂度则代表其最坏情况下的运行时间。理由呢？参考微积分的一条基本概念就知道了：对于一个多项式，随着 x 变量的无限增大，其极限趋近于首项的值。例如，Y(x) = x^3 + x^2 + x 的值会在 x 趋向于无穷大时近似于 x^3。

在算法中，常见的时间复杂度的表示有（C 为常量）：

• O(b): 复杂度为 Cb，其中 b 是常量
• O(n)：当 n 很大时复杂度趋向于 Cn
• O(n^2)：当 n 很大时复杂度趋向于 Cn^2
• ...依次类推

具体什么意思呢？

假设有一个函数：

const add = (a, b) => a + b;

不管执行时 a, b 参数是多少，它的执行时间是恒定可预测的，即时间与参数无关。我们就可以说它的时间复杂度是 O(1)。

同样是一个求和函数，扩展一下其可接受的参数：

const add = (...args) => args.reduce((p, c) => p + c, 0);

让其接受的参数不限，利用 reduce 遍历求和。此时，该函数的时间复杂度变为 O(n)，其中 n 代表参数个数。

再来一个更复杂一点的，假设我们会接受一个嵌套的数组，需要依次取出里面的每一个元素，通过某种方法 format 以后，将其扁平化到一个数组中返回：

/*
 * 接受形如 [[1, 2, 3], [4, 5, 6]] 的嵌套数组，返回
 * [format(1), ..., format(6)]
 * 其中 format 代表对每个参数都进行了特殊处理
 */
const flatArray = (arg) => {
  const result = [];
  const format = (item) => {
    // do something special
  };
  arg.forEach((array) => {
    array.forEach(item => result.push(format(item)));
  });
  return result;
};

在这个函数里，我们有两层嵌套循环，因此，算法的时间复杂度为 O(n^2)。

同理，当函数有三层嵌套循环时，我们可以认为其时间复杂度为 O(n^3)，以此类推。

附一些可以参考的资料：

• What is a plain English explanation of “Big O” notation?
• 算法复杂度分析
• 算法时间复杂度的表示法O(n²)、O(n)、O(1)、O(nlogn)等是什么意思？

动态规划

字符串问题