JavaScript数据结构

栈

封装栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Stack {
    // 使用ES5-function构造的话，方法最好放在原型上。
    constructor() {
        this.items = [];
    }
    push(element) {
        this.items.push(element);
    }
    pop() {
        return this.items.pop();
    }
    peek() {
        return this.items[this.items.length - 1];
    }
    isEmpty() {
        return this.items.length == 0;
    }
    clear() {
        this.items = [];
    }
    size() {
        return this.items.length;
    }
}

题目

十进制转二进制

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function ten2two(ten_num) {
    let stack = [];

    while (ten_num > 0) {
        stack.push(ten_num % 2);
        ten_num = Math.floor(ten_num / 2);
    }
    let binaryString = '';
    while (stack.length > 0) {
        binaryString += stack.pop();
    }
    return binaryString;
}
let res = ten2two(100);
console.log(res);

二进制转字符串

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
var printBin = function (num) {
    if (num < 0 || num >= 1) return 'ERROR';
    let stack = [];
    let length = 30;
    while (length > 0) {
        if (num <= 0) break;
        num *= 2;
        if (num >= 1) {
            num--;
            stack.push(1);
        } else {
            stack.push(0);
        }
        length--;
    }

    /* 打印 */
    if (num === 0) {
        let res = "0."
        while (stack.length > 0) {
            res += stack.shift()
        }
        return res
    } else {
        return "ERROR"
    }
};

let a = printBin(0.8);
console.log(a)

任意进制转换

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 /* 将十进制数转换为2-36进制中任意进制的数 */
let ten2random = function (dealNum, base) {
    const digits = '0123456789ABCDEFGHJKLMNPQRSTUVWXYZ';
    let stack = [];
    while (dealNum > 0) {
        stack.push(dealNum % base);
        dealNum = Math.floor(dealNum / base);
    }
    let res = '';
    while (stack.length > 0) {
        res += digits[stack.pop()];
    };
    return res;
}
let res = ten2random(12222, 16);
console.log(res);

队列

创建队列

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
        /* 
            使用ES6对象语法创建
        */
class Queue {
    constructor() {
        this.count = 0; // 元素数量
        this.lowstCount = 0; // 队列顶部追踪器
        this.items = {}; // 存储器
    }
    // 向队尾添加一个元素
    enqueue(element) {
        this.items[this.count++] = element;
    }
    // 从队尾删除元素
    dequeue() {
        if (this.isEmpty()) return undefined;
        const res = this.items[this.lowstCount];
        delete this.items[this.lowstCount++];
        return res;
    }
    // 查看队首元素
    peek() {
        if (this.isEmpty()) return undefined;
        return this.items[this.lowstCount];
    }
    // 判断队列是否为空
    isEmpty() {
        return this.size() === 0;
    }
    // 返回长度大小
    size() {
        return this.count - this.lowstCount;
    }
    // 清空队列
    clear() {
        this.lowstCount = 0;
        this.count = 0;
        this.items = {};
    }
    // toString方法
    toString() {
        if (this.isEmpty()) return "";
        let res = "";
        for (let i = this.lowstCount; i < this.count; i++) {
            res += this.items[i];
        }
        return res;
    }
}

双端队列

一种允许我们同时从前端，后端添加和删除元素的特殊队列。

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
        /* 
    使用ES6对象语法创建
*/
class Deque {
    constructor() {
        this.count = 0; // 元素数量
        this.lowstCount = 0; // 队列顶部追踪器
        this.items = {}; // 存储器
    }
    // 向队首添加一个元素
    addFront(element) {
        if (this.isEmpty()) {
            this.addBack(element);
        } else if (this.lowstCount > 0) {
            this.items[--this.lowstCount] = element;
        } else {
            for (let i = this.count; i > 0; i--) {
                this.items[i] = this.count[i - 1];
            }
            this.count++;
            this.lowstCount = 0;
            this.items[0] = element;
        }

    }

    // 向队尾添加一个元素
    addBack(element) {
        this.items[this.count++] = element;
    }

    // 从队尾删除元素
    removeBack() {
        if (this.isEmpty()) return undefined;
        const res = this.items[this.lowstCount];
        delete this.items[this.lowstCount++];
        return res;
    }

    // 从队首删除元素
    removeFront(){
        if (this.isEmpty()){
            return undefined;
        } else{
            let res = this.items[this.lowstCount];
            this.count--;
            for(let i = this.count;i>0;i--){
                this.items[this.count-1] = this.items[this.count];
            }
            delete this.items[this.lowstCount];
            return res;
        }
    }

    // 查看队首元素
    peekFront() {
        if (this.isEmpty()) return undefined;
        return this.items[this.lowstCount];
    }

    // 查看队尾元素
    peekBack() {
        if (this.isEmpty()) return undefined;
        return this.items[this.count];
    }

    // 判断队列是否为空
    isEmpty() {
        return this.size() === 0;
    }

    // 返回长度大小
    size() {
        return this.count - this.lowstCount;
    }

    // 清空队列
    clear() {
        this.lowstCount = 0;
        this.count = 0;
        this.items = {};
    }

    // toString方法
    toString() {
        if (this.isEmpty()) return "";
        let res = "";
        for (let i = this.lowstCount; i < this.count; i++) {
            res += this.items[i];
        }
        return res;
    }
}

题目

击鼓传花

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/* 
	队列思维
*/
let hotPotato = function (elementList, num) {
    if (elementList.length === 0) return "ERROR";
    let eliminatedList = []; // 淘汰顺序
    while (elementList.length > 1) {
        for (let i = 0; i < num; i++) {
            let temp = elementList.shift();
            elementList.push(temp);
        }
        eliminatedList.push(elementList.shift());
    }
    let winner = elementList[0];
    return [winner, eliminatedList];
    /* 
    	千万注意，js不能直接返回两个返回值。
	*/
}
let elementList = ['zjl', 'ls', 'ljl', 'zl', 'zj', 'ycy', 'nym', 'zj'];
let res = hotPotato(elementList, 5);
console.log(res);

回文检测器

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 /* 
            使用双向队列思维实现
        */
let palindromeCheck = function (word) {
    let word_arr = Array.from(String(a).split(""));
    while (word_arr.length > 1) {
        if (word_arr.pop() === word_arr.shift()) {
            continue;
        } else {
            return false;
        }
    }
    return true;
}
console.log(palindromeCheck("abjcajaajacjba"));

时间复杂度

image-20211228155318098

常数操作：操作时间与数据量无关。

加减乘除、位运算、读取数组某一项、读取对象某一属性……

选择排序时间复杂度：O(n^2^)，额外空间复杂度O(1)

选择排序原理

img

对第一个数：N(遍历) + N(比较) + 1(交换)

对第二个数：N-1(遍历) + N-1(比较) + 1(交换)

……

常数操作次数：aN^2^+bN+c

可以得出O(N2)，估计的是瓶颈上限。

冒泡排序

img

时间复杂度:O(N^2^)，额外空间复杂度O(1)

  • 异或运算：无进位相加。
    • 性质：
      • 0^N = N
      • N^N=0
      • 满足交换律结合律
image-20211228165716351

所以：交换两个数的值可以写成：省去额外变量。

1
2
3
a=a^b;
b=a^b;
a=a^b;

必须满足：内存中的位置是不同的。内存相同会把a、b清零。

image-20211228170526619

异或运算

面试题：一个数组中，已知只有一种数出现了奇数次，其他所有数都出现了偶数次，怎么找到出现奇数次的数。

解法：全部一起异或。

改成：有两种数（不相等）出现了奇数次，其他所有数都出现了偶数次，求这两个出现奇数次的数。

解法：全部一起异或。解法：全部一起异或，因为两个数不相等，那么异或结果一定不为0，那么必有一个二进制位为1，那么该位上，这两个数的二进制位上不相等，必定是一个为1，一个为0。创建一个新变量为0，继续异或这个数组，但是只异或该二进制位上不为1的(因为有一点：其他数该位为1的都是偶数个，只有出现奇数次的数该位为1的次数为奇数个，自然返回两个中的一个)；在只异或该位上为0的数即可。

要求：时复O(N) 额外空间复杂度O(1)。

插入排序

img

时间复杂度：O(N^2^) 额外空间复杂度：O(1)

二分法

  • 在有序数组中查找是否有某个值。 时间复杂度：O(log2N)，因为最差：2^n^=N
  • 在一个有序数组中，找一个>=某个数最左侧的位置。（二分到结束）
  • 任意相邻两数不相等，求局部最小值问题。

对数器

image-20211228191402596

Nlog(N)的排序算法

tips: 数组二分的时候，使用(L+R) / 2可能会溢出，所以，我们最好用(R + (L-R)/2) 或者(L + (R-L)/2)实现，或者使用移位运算符(R + (L-R)>>1) / (L + (R-L)>>1)。

递归实现案例：找一组数中的最小值，使用递归完成。

img

时间复杂度：O(Nlog2N)，额外空间复杂度O(N)。

比较没有被单纯浪费，而是被保存。

小和问题

快速排序

image-20211230195828096

保存的是值，如果是对象，保存的是内存地址，千万要分清楚。

时间复杂度：O(NlogN) 额外空间复杂度：O(logN)

堆排序

大顶堆和小顶堆

对于索引i位置，其父节点为，(i / 2)，子节点为（i * 2 + 1）和(i * 2 + 2)

增删改查

heapify

heapsize

改后，大于原值，向上调整；小于原值，向下调整

删和改的代价都是O(logN)

堆排序的原理就是：先把数组大顶堆化，然后将堆顶元素删除，用最后一个元素代替该位置的元素；然后继续堆化，继续删除堆顶元素，插入原数组的最前面……。

时间复杂度O(NlogN)，额外空间复杂度O(1)

image-20220106172943353

继续改进：递归构建大顶堆。

优先级队列底层也是堆结构

image-20220106173023906

插入排序或者堆排序（前提是k是给出的，复杂度为O(NlogN)）

扩容代价O(NlogN)

image-20220106174709632

基数排序

基于比较的排序和不基于比较的排序。

image-20220106214517446 image-20220106220135761

排序算法稳定性

稳定性对于关注相对次序的场景很重要，比如：对商品，先按价格排序，再按评分排序。

选择排序：不稳定

image-20220106220730997

冒泡：稳定

image-20220106220803701

插入：稳定

3 2 2

归并排序：稳定

image-20220106221412311

merge时，先拷贝左边，在拷贝右边时稳定

快速排序：不稳定

image-20220106221529139

partition过程决定了不稳定

堆排序：不稳定

5 4 4 6形成二叉树就破坏了稳定性

桶排序：稳定，因为先入桶的先出桶

image-20220106221833833

一般考察快排。

问题：基于比较的排序算法，时间复杂度没有低于O(NlogN)的，同时满足空间复杂度低于O(N)还稳定的排序算法，目前是没有的。

image-20220106222247462 image-20220106222711591

不同样本量使用不同排序算法，以便利用各自优势！