2024-12-12 日报 Day14

2024-12-12 日报 Day14

Yuyang 前端小白🥬
  2024-12-12 2024-12-12 创建   2024-12-12 08:21:13 2024-12-12 08:21:13 更新      

今日的鸡汤

莫道春光难揽取，浮云过后艳阳天。

今日学习内容

1、《JavaScript数据结构与算法》 P113-160

今日笔记

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
this.union = function(otherSet){
    let unionSet = new Set();

    let values = this.values();
    for(let i = 0; i < values.length; i++){
        unionSet.add(values[i]);
    }

    values = otherSet.values();
    for(let i = 0; i < values.length; i++){
        unionSet.add(values[i]);
    }
    return unionSet;
}


let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(3);
setB.add(4);
setB.add(5);
setB.add(6);

let unionAB = setA.union(setB);
console.log(unionAB.values());

2、集合交集

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
this.intersection = function(otherSet){
    let intersectionSet = new Set();

    let values = this.values();
    for(let i = 0; i < values.length; i++){
        if(otherSet.has(values[i])){
            intersectionSet.add(values[i]);
        }
    }
    return intersectionSet;
}

let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

let intersectionAB = setA.intersection(setB);
console.log(intersectionAB.values());

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
this.difference = function(otherSet){
    let differenceSet = new Set();

    let values = this.values();
    for(let i = 0; i < values.length; i++){
        if(!otherSet.has(values[i])){
            differenceSet.add(values[i]);
        }
    }
    return differenceSet;
}

let setA = new Set();
setA.add(1);
setA.add(2);
setA.add(3);

let setB = new Set();
setB.add(2);
setB.add(3);
setB.add(4);

let differenceAB = setA.difference(setB);
console.log(differenceAB.values());

4、集合子集

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
this.subset = function(otherSet){
    if(this.size() > otherSet.size()){
        return false;
    } else {
        let values = this.values();
        for(let i = 0; i < values.length; i++){
            if(!otherSet.has(values[i])){
                return false;
            }
        }
        return true;
    }
}

let setA = new Set();
setA.add(1);
setA.add(2);

let setB = new Set();
setB.add(1);
setB.add(2);
setB.add(3);

let setC = new Set();
setC.add(2);
setC.add(3);
setC.add(4);

console.log(setA.subset(setB));
console.log(setA.subset(setC));

5、ES6中的集合。ES6的Set的values方法返回的是Iterator对象，可以使用for…of循环遍历。

1
2
3
4
5
6
7
let set = new Set();
set.add(1);
set.add(2);
set.add(3);
for(let item of set.values()){
    console.log(item);
}

6、使用ES6的Set实现数组去重

1
2
3
let arr = [1, 2, 3, 4, 4, 3, 2, 1];
let set = new Set(arr);
console.log([...set]);

7、字典和散列表
ES6中字典为Map,散列表为HashMap。
一般字典需要包含的方法：

  • set(key, value)：向字典中添加新元素。
  • delete(key)：通过使用键值来从字典中移除键值对应的数据值。
  • has(key)：如果某个键值存在于这个字典中，则返回true，反之则返回false。
  • get(key)：通过键值查找特定的数值并返回。
  • clear()：将这个字典中的所有元素全部删除。
  • size()：返回字典所包含元素的数量。与数组的length属性类似。
  • keys()：将字典所包含的所有键名以数组形式返回。
  • values()：将字典所包含的所有数值以数组形式返回。
    8、方法实现
    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
    function Dictionary(){
        var items = {};

        this.has = function(key){
            return key in items;
        };

        this.set = function(key, value){
            items[key] = value;
        };

        this.delete = function(key){
            if(this.has(key)){
                delete items[key];
                return true;
            }
            return false;
        };

        this.get = function(key){
            return this.has(key) ? items[key] : undefined;
        };

        this.values = function(){
            var values = [];
            for(var k in items){
                if(this.has(k)){
                    values.push(items[k]);
                }
            }
            return values;
        };

        this.clear = function(){
            items = {};
        };

        this.size = function(){
            return Object.keys(items).length;
        };

        this.keys = function(){
            return Object.keys(items);
        };

        this.getItems = function(){
            return items;
        };
    }

    var dictionary = new Dictionary();
    dictionary.set('Gandalf', 'gandalf@email.com');
    dictionary.set('John', 'johnsnow@email.com');
    console.log(dictionary.has('Gandalf'));
    console.log(dictionary.size());
    console.log(dictionary.keys());
    console.log(dictionary.values());
    console.log(dictionary.get('John'));
    9、散列表
    散列算法的作用是尽可能快地在数据结构中找到一个值。在散列表中插入、删除和取用数据都非常快，但是对于查找操作来说却效率低下。最简单的散列方法是简单地将每个键值中的每个字母的ASCII值相加。
    三个基本的方法:
  • put(key, value)：向散列表增加一个新的项（也能更新散列表）。
  • remove(key)：根据键值从散列表中移除值。
  • get(key)：返回根据键值检索到的特定的值。
    1
    2
    3
    function HashTable(){
        var table = [];
    }
    10、散列函数
    1
    2
    3
    4
    5
    6
    7
    this.loseloseHashCode = function(key){
        var hash = 0;
        for(var i = 0; i < key.length; i++){
            hash += key.charCodeAt(i);
        }
        return hash % 37;
    };
    11、基本方法实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        console.log(position + ' - ' + key);
        table[position] = value;
    };
    this.get = function(key){
        return table[loseloseHashCode(key)];
    };
    this.remove = function(key){
        table[loseloseHashCode(key)] = undefined;
    };
    12、测试
    1
    2
    3
    4
    var hash = new HashTable();
    hash.put('Gandalf', 'gandalf@email.com');
    hash.put('John', 'johnsnow@email.com');
    console.log(hash.get('Gandalf'));
    13、散列冲突
    一些键会有相同的散列值,不同的值在散列表中对应相同的位置，这种现象称为散列冲突。解决冲突的方法有两种：分离链接、线性探查和双散列法。
  • 分离链接: 散列表的每一个位置创建一个链表并将元素存储在里面。但是其在HashTable实例之外还需要额外的存储空间。
    其需要重写三个方法: put、get、remove。
    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
    this.put = function(key, value){
        var position = loseloseHashCode(key);
        if(table[position] == undefined){
            table[position] = new LinkedList();
        }
        table[position].append(new ValuePair(key, value));
    };
    this.get = function(key){
        var position = loseloseHashCode(key);
        if(table[position] !== undefined){
            var current = table[position].getHead();
            while(current.next){
                if(current.element.key === key){
                    return current.element.value;
                }
                current = current.next;
            }
            if(current.element.key === key){
                return current.element.value;
            }
        }
        return undefined;
    };
    this.remove = function(key){
        var position = loseloseHashCode(key);
        if(table[position] !== undefined){
            var current = table[position].getHead();
            while(current.next){
                if(current.element.key === key){
                    table[position].remove(current.element);
                    if(table[position].isEmpty()){
                        table[position] = undefined;
                    }
                    return true;
                }
                current = current.next;
            }
            if(current.element.key === key){
                table[position].remove(current.element);
                if(table[position].isEmpty()){
                    table[position] = undefined;
                }
                return true;
            }
        }
        return false;
    };
    14、线性探查
    当发生冲突时，线性探查会检查散列表中的下一个位置是否为空。如果为空，就将数据存入。如果不为空，就继续检查下一个位置。直到找到一个空的位置。
    统一需要重写put、get、remove方法
    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
    this.put = function(key, value){
        var position = loseloseHashCode(key);

        if(table[position] == undefined){
            table[position] = new ValuePair(key, value);
        } else {
            var index = ++position;
            while(table[index] != undefined){
                index++;
            }
            table[index] = new ValuePair(key, value);
        }
    };
    this.get = function(key){
        var position = loseloseHashCode(key);

        if(table[position] !== undefined){
            if(table[position].key === key){
                return table[position].value;
            } else {
                var index = ++position;
                while(table[index] === undefined || table[index].key !== key){
                    index++;
                }
                if(table[index].key === key){
                    return table[index].value;
                }
            }
        }
        return undefined;
    };
    this.remove = function(key){
        var position = loseloseHashCode(key);

        if(table[position] !== undefined){
            if(table[position].key === key){
                table[position] = undefined;
            } else {
                var index = ++position;
                while(table[index] === undefined || table[index].key !== key){
                    index++;
                }
                if(table[index].key === key){
                    table[index] = undefined;
                }
            }
        }
        return undefined;
    };
    15、树
    非顺序数据结构–树。树是一种非线性数据结构，以分层的方式存储数据。树的第一个节点叫做根节点。树的最大层级叫做树的深度。
    二叉树和二叉搜索树(BST, Binary Search Tree):二叉树的每个节点最多只能有两个子节点：左侧子节点和右侧子节点;二叉搜索树是二叉树的一种，但是它只允许你在左侧节点存储（比父节点）小的值，在右侧节点存储（比父节点）大（或者等于）的值。
    1
    2
    3
    4
    5
    6
    7
    8
    9
    function BinarySearchTree(){
        var Node = function(key){
            this.key = key;
            this.left = null;
            this.right = null;
        };

        var root = null;
    }
    树类中需要实现的方法有：
  • insert(key)：向树中插入一个新的键。
  • search(key)：在树中查找一个键。如果节点存在，则返回true；如果不存在，则返回false。
  • inOrderTraverse()：通过中序遍历方式遍历所有节点。
  • preOrderTraverse()：通过先序遍历方式遍历所有节点。
  • postOrderTraverse()：通过后序遍历方式遍历所有节点。
  • min()：返回树中最小的值/键。
  • max()：返回树中最大的值/键。
  • remove(key)：从树中移除某个键。
    16、方法实现
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    this.insert = function(key){
        var newNode = new Node(key);
        
        if(root === null){
            root = newNode;
        } else {
            insertNode(root, newNode);
        }
    }
    var insertNode = function(node, newNode){
        if(newNode.key < node.key){
            if(node.left === null){
                node.left = newNode;
            } else {
                insertNode(node.left, newNode);
            }
        } else {
            if(node.right === null){
                node.right = newNode;
            } else {
                insertNode(node.right, newNode);
            }
        }
    }
    17、树的遍历: 中序、先序、后序
    采用访问者模式，将回调函数作为参数传入遍历方法中。
    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
    // 中序遍历
    this.inOrderTraverse = function(callback){
        inOrderTraverseNode(root, callback);
    }
    var inOrderTraverseNode = function(node, callback){
        if(node !== null){
            inOrderTraverseNode(node.left, callback);
            callback(node.key);
            inOrderTraverseNode(node.right, callback);
        }
    }
    // 先序遍历
    this.preOrderTraverse = function(callback){
        preOrderTraverseNode(root, callback);
    }
    var preOrderTraverseNode = function(node, callback){
        if(node !== null){
            callback(node.key);
            preOrderTraverseNode(node.left, callback);
            preOrderTraverseNode(node.right, callback);
        }
    }
    // 后序遍历
    this.postOrderTraverse = function(callback){
        postOrderTraverseNode(root, callback);
    }
    var postOrderTraverseNode = function(node, callback){
        if(node !== null){
            postOrderTraverseNode(node.left, callback);
            postOrderTraverseNode(node.right, callback);
            callback(node.key);
        }
    }
    18、自平衡树(Adelson-Velskii-Landi, AVL)
    AVL树是最先发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1。AVL树是一种自平衡二叉查找树，任一节点对应的两棵子树的最大高度差为1。
    19、红黑树: 红黑树是一种自平衡二叉查找树，它在每个节点上增加了存储位来表示节点的颜色，可以是红色或黑色。通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，红黑树确保没有一条路径会比其他路径长出两倍，因此是接近平衡的。
此页目录
2024-12-12 日报 Day14
  1. 今日学习内容
  2. 今日笔记