基本数据结构
回顾一波基本数据结构，做个整理。
目录
[队列](# 队列(queue))
[栈](# 栈(Stack))
[链表](# 链表(List))
[堆](# 堆(Heap))
队列(queue)
定义
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端(front)进行删除操作，而在表的后端(rear)进行插入操作。
先进先出
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function Queue() {
this.data = new Array();
this.clear = function(){
this.data = new Array();
}
this.shift = function () {
return this.data.shift();
}
this.push = function (d) {
this.data.push(d);
}
this.getItem = function(){
return this.data[0];
}
}
|
应用
108.将有序数组转换为二叉搜索树
将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。
本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
1
2
3
4
5
6
7
8
9
| 给定有序数组: [-10,-3,0,5,9],
一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树：
0
/ \
-3 9
/ /
-10 5
|
实现
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
|
var sortedArrayToBST = function (nums) {
if (nums.length === 0) {
return null;
}
function Node(start, end) {
this.start = start;
this.end = end;
}
function TreeNode(val) {
this.val = val;
this.left = this.right = null;
}
function setTreeNode(val, tree) {
if (tree.left === null && tree.val > val) {
tree.left = new TreeNode(val);
}
else if (tree.right === null && tree.val < val) {
tree.right = new TreeNode(val);
}
else if (tree.left !== null && tree.val > val) {
setTreeNode(val, tree.left);
}
else if (tree.right !== null && tree.val < val) {
setTreeNode(val, tree.right);
}
}
const len = nums.length;
let lenList = [];
let lenQueue = [new Node(0, len - 1)];
while (lenQueue.length) {
let node = lenQueue.shift();
if (node.end - node.start > 1) {
lenQueue.push(new Node(node.start, Math.round((node.end + node.start) / 2) - 1));
lenQueue.push(new Node(Math.round((node.end + node.start) / 2) + 1, node.end));
} else if (node.end - node.start === 1) {
lenQueue.push(new Node(node.start, Math.round((node.end + node.start) / 2) - 1));
}
lenList.push(Math.round((node.end + node.start) / 2));
}
let tree = new TreeNode(nums[lenList[0]]);
for (let i = 1; i < lenList.length; i++) {
setTreeNode(nums[lenList[i]], tree);
}
return tree;
};
|
栈(Stack)
定义
栈是一种特殊的线性表，特殊之处在于它只允许在表的一端进行添加和删除操作。
先进后出
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| function Stack() {
this.data = new Array();
this.clear = function(){
this.data = new Array();
}
this.pop = function () {
return this.data.pop();
}
this.push = function (d) {
this.data.push(d);
}
this.getItem = function(){
return this.data[this.data.length-1];
}
}
|
应用
107.二叉树的层次遍历 II
给定一个二叉树，返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历)
例如：
给定二叉树 [3,9,20,null,null,15,7],
返回其自底向上的层次遍历为：
1
2
3
4
5
| [
[15,7],
[9,20],
[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
|
var levelOrderBottom = function (root) {
let DepthNode = function (node, depth) {
this.node = node;
this.depth = depth
}
let stack = [];
let answer = [];
if (root !== null) {
let node = stack.push(new DepthNode(root, 0));
while (stack.length) {
let node = stack.pop();
if (!Array.isArray(answer[node.depth])) {
answer[node.depth] = new Array();
}
answer[node.depth].push(node.node.val);
if (node.node.right) {
stack.push(new DepthNode(node.node.right, node.depth + 1));
}
if (node.node.left) {
stack.push(new DepthNode(node.node.left, node.depth + 1));
}
}
return answer.reverse();
} else {
return [];
}
};
|
链表(List)
定义
链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点(链表中每一个元素称为结点)组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。
实现
1
2
3
4
| function ListNode(value) {
this.value = value;
this.nextNode = null;
}
|
应用
236.二叉树的最近公共祖先
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大(一个节点也可以是它自己的祖先)。”
例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]
1
2
3
4
5
6
7
| 3
/ \
5 1
/ \ / \
6 2 0 8
/ \
7 4
|
示例 1:
1
2
3
| 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。
|
示例 2:
1
2
3
| 输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。
|
实现
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
|
var lowestCommonAncestor = function (root, p, q) {
function setNodeList(node) {
let list = [node];
while (node && node.father) {
list.unshift(node.father);
node = node.father;
}
return list
}
let nodeStack = [root];
let nodeListP = undefined;
let nodeListQ = undefined;
while (nodeStack.length) {
let node = nodeStack.pop();
if (node.right) {
nodeStack.push(node.right);
node.right.father = node;
}
if (node.left) {
nodeStack.push(node.left);
node.left.father = node;
}
if (node.val === q.val) {
nodeListQ = setNodeList(node);
}
if (node.val === p.val) {
nodeListP = setNodeList(node);
}
if (nodeListP && nodeListQ) {
break;
}
}
for (let i = 0; i < Math.min(nodeListP.length, nodeListQ.length); i++) {
if (!nodeListP[i + 1] || !nodeListQ[i + 1] || nodeListP[i + 1].val !== nodeListQ[i + 1].val) {
return nodeListP[i];
}
}
return null;
};
|
堆(Heap)
定义
堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质：
- 堆中某个节点的值总是不大于或不小于其父节点的值；
- 堆总是一棵完全二叉树。
堆的常用方法：
构建优先队列
支持堆排序
快速找出一个集合中的最小值（或者最大值）
将根节点最大的堆叫做最大堆或大根堆，根节点最小的堆叫做最小堆或小根堆。常见的堆有二叉堆、斐波那契堆等。
堆的定义如下：n个元素的序列{k1,k2,ki,…,kn}当且仅当满足下关系时，称之为堆。
(ki <= k2i,ki <= k2i+1)或者(ki >= k2i,ki >= k2i+1), (i = 1,2,3,4...n/2)
若将和此次序列对应的一维数组（即以一维数组作此序列的存储结构）看成是一个完全二叉树，则堆的含义表明，完全二叉树中所有非终端结点的值均不大于（或不小于）其左、右孩子结点的值。由此，若序列{k1,k2,…,kn}是堆，则堆顶元素（或完全二叉树的根）必为序列中n个元素的最小值（或最大值）。
堆和普通树的区别
堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：
节点的顺序。在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
内存占用。普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配额为是我内存。堆仅仅使用一个数据来村塾数组，且不使用指针。
平衡。二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n)。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足对属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。
搜索。在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
来自数组的树
用数组来实现树相关的数据结构也许看起来有点古怪，但是它在时间和空间山都是很高效的。
我们准备将上面的例子中的树这样存储：
就这样！我们除了一个简单的数组以外，不需要任何额外的空间。
可以用堆做什么？
有两个原始操作用于保证插入或删除节点以后堆是一个有效的最大堆或者最小堆：
shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这样是这个节点在数组的位置上升。shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这个操作也称作“堆化（heapify）”。
shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 **O(log n)**。
基于这两个原始操作还有一些其他的操作：
insert(value): 在堆的尾部添加一个新的元素，然后使用 shiftUp 来修复对。remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用 shiftDown 方法来修复堆。removeAtIndex(index): 和 remove() 一样，差别在于可以移除堆中任意节点，而不仅仅是根节点。当它与子节点比较位置不时无序时使用 shiftDown()，如果与父节点比较发现无序则使用 shiftUp()。replace(index, value)：将一个更小的值（最小堆）或者更大的值（最大堆）赋值给一个节点。由于这个操作破坏了堆属性，所以需要使用 shiftUp() 来修复堆属性。
上面所有的操作的时间复杂度都是 **O(log n)**，因为 shiftUp 和 shiftDown 都很费时。还有少数一些操作需要更多的时间：
search(value):堆不是为快速搜索而建立的，但是 replace() 和 removeAtIndex() 操作需要找到节点在数组中的index，所以你需要先找到这个index。时间复杂度：**O(n)**。buildHeap(array):通过反复调用 insert() 方法将一个（无序）数组转换成一个堆。如果你足够聪明，你可以在 O(n) 时间内完成。- 堆排序：由于堆就是一个数组，我们可以使用它独特的属性将数组从低到高排序。时间复杂度：**O(n lg n)**。
堆还有一个 peek() 方法，不用删除节点就返回最大值（最大堆）或者最小值（最小堆）。时间复杂度 O(1) 。
注意：到目前为止，堆的常用操作还是使用 insert() 插入一个新的元素，和通过 remove()移除最大或者最小值。两者的时间复杂度都是**O(log n)**。其其他的操作是用于支持更高级的应用，比如说建立一个优先队列。
实现
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
99
100
101
102
103
104
105
106
107
| const swapData = function (array, index_a, index_b) {
let temp = array[index_a];
array[index_a] = array[index_b];
array[index_b] = temp;
}
const isNumber = function (obj) {
return typeof obj === 'number' && !isNaN(obj)
}
function Heap(heapArray) {
this.data = [];
this.build(heapArray);
}
Heap.prototype.insetValue = function (value) {
if (isNumber(value)) {
this.data.push(value);
this.shiftUp(this.data.length - 1);
}
}
Heap.prototype.size = function () {
return this.data.length;
}
Heap.prototype.isEmpty = function () {
if (this.data.length === 0) {
return true
}
return false;
}
Heap.prototype.getTop = function () {
return this.data[0] === undefined ? null : this.data[0];
}
Heap.prototype.removeTop = function () {
let value = undefined;
if (this.data.length > 1) {
let value = this.data[0];
this.data[0] = this.data[this.data.length - 1];
this.data.pop();
this.shiftDown(0);
return value;
} else if (this.data.length === 1) {
return this.data.pop();
} else {
return null;
}
}
Heap.prototype.removeAtIndex = function (index) {
let value = this.data[index];
this.data[index] = this.data[this.data.length - 1];
this.data.pop();
if (this.data[index] > this.data[Math.floor((index - 1) / 2)]) {
this.shiftUp(index);
} else if (this.data[index] < this.data[index * 2 + 1]
|| this.data[index] < this.data[index * 2 + 2]) {
this.shiftDown(index);
}
return value;
}
Heap.prototype.shiftUp = function (index) {
let fatherIndex = Math.floor((index - 1) / 2);
while (index >= 0) {
if (this.data[fatherIndex] < this.data[index]) {
swapData(this.data, fatherIndex, index);
index = fatherIndex;
fatherIndex = Math.floor((index - 1) / 2);
}
else {
break;
}
}
}
Heap.prototype.shiftDown = function (index) {
const len = this.data.length;
let fatherIndex_1 = index * 2 + 1;
let fatherIndex_2 = index * 2 + 2;
while (fatherIndex_1 < len || fatherIndex_2 < len) {
let swapFather = undefined;
if (this.data[fatherIndex_2] === undefined
|| this.data[fatherIndex_1] > this.data[fatherIndex_2]) {
swapFather = fatherIndex_1;
} else {
swapFather = fatherIndex_2;
}
if (this.data[index] < this.data[swapFather]) {
swapData(this.data, swapFather, index);
index = swapFather;
fatherIndex_1 = index * 2 + 1;
fatherIndex_2 = index * 2 + 2;
} else {
break;
}
}
}
Heap.prototype.build = function (heapArray) {
for (let i = 0; i < heapArray.length; i++) {
this.insetValue(heapArray[i])
}
}
Heap.isHeap = function (heapArray) {
const len = heapArray.length;
for (let i = 0; (2 * i + 2) < len; i++) {
if (heapArray[i] < heapArray[2 * i + 1] || heapArray[i] < heapArray[2 * i + 2]) {
return false
}
}
return true;
}
|
应用
1046. 最后一块石头的重量
有一堆石头，每块石头的重量都是正整数。
每一回合，从中选出两块最重的石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：
- 如果 x == y，那么两块石头都会被完全粉碎；
- 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。
最后，最多只会剩下一块石头。返回此石头的重量。如果没有石头剩下，就返回 0。
示例 ：
1
2
3
| 输入:[2,7,4,1,8,1]
输出：1
解释: 最终剩下的石头重量是 1
|
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
|
var lastStoneWeight = function (stones) {
let stoneHeap = new Heap(stones);
while (true) {
let stoneFirst = stoneHeap.removeTop();
if (stoneHeap.isEmpty()) {
return stoneFirst;
break;
}
let stoneSecond = stoneHeap.removeTop();
let smallStone = stoneFirst - stoneSecond;
if (smallStone !== 0) {
stoneHeap.insetValue(smallStone);
}
}
};
|