Trie树

也叫“字典树”。它是一个树形结构。它是一种专门处理字符串匹配的数据结构，用来解决在一组字符串集合中快速查找某个字符串的问题。

Trie 树的本质，就是利用字符串之间的公共前缀，将重复的前缀合并在一起

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

class Trie {
public:
    char data{};
    Trie* node[26]{};
public:
    explicit Trie(char value) : data(value) {
        for (auto & i : node) {
            i = nullptr;
        }
    }
};

void printTrie(Trie* trie) {
    for (int i = 0; i < 26; i++) {
        if (trie->node[i] != nullptr) {
            std::cout << char(i+'a') << " ";
        }
    }
    std::cout << std::endl;
}

void insertTrie(Trie* trie, const std::string& str) {
    for (auto& x : str) {
        int pos = x-'a';
        if (trie->node[pos] == nullptr) {
            trie->node[pos] = new Trie(x);
        }
        trie = trie->node[pos];
    }
}

bool findStr(Trie* trie, const std::string& str) {
    for (auto& x : str) {
        int pos = x-'a';
        if (trie->node[pos] == nullptr) {
            return false;
        }
        trie = trie->node[pos];
    }
    return true;
}

构建 Trie 树的过程，需要扫描所有的字符串，时间复杂度是 O(n)（n 表示所有字符串的长度和）

堆

1. 堆是一个完全二叉树
2. 堆中每个节点的值都必须大于等于（或者小于等于）其子树中每个节点的值

哈希表

一、哈希冲突

1. 开放寻址法

   • 线性探测

字典树

Trie树，又称单词查找树或键树，是一种树形结构。典型应用是用于统计和排序大量的字符串(但不仅限于字符串)，所以经常被搜索引擎系统用于文本词频统计。

他的优点是：最大限度的减少无谓的字符串比较，查询效率比哈希表高。

基本性质：

1. 节点本身不存完整单词

字符串算法

一、BF算法

Brute Force 的缩写，中文叫作暴力匹配算法，也叫朴素匹配算法。

我们在字符串 A 中查找字符串 B，那字符串 A 就是主串，字符串 B 就是模式串。我们把主串的长度记作 n，模式串的长度记作 m。因为我们是在主串中查找模式串，所以 n>m。

算法思想：在主串中，检查起始位置分别是 0、1、2….n-m 且长度为 m 的 n-m+1 个子串，看有没有跟模式串匹配的。

时间复杂度：最坏情况时间复杂度是 O(n*m)。

二、RK算法

Rabin-Karp 算法，是由它的两位发明者 Rabin 和 Karp 的名字来命名的

排序

常见的排序算法：冒泡排序、插入排序、选择排序、归并排序、快速排序、计数排序、基数排序、桶排序

1
2
3
4
5
6
7
8
9
10
11

def dfs(node):
    if node in visited:
        # already visited
        return 

    visited.add(node)

    # process current node
    # ... # logic here
    dfs(node.left)
    dfs(node.right) 

1
2
3
4
5
6
7
8
9

visited = set()

def dfs(node, visited):
    visited.add(node)
    # process current node here
    ...
    for next_node in node.children():
        if not next_node in visited:
            dfs(next node, visited)

非递归的写法
模拟了一个栈作为递归的栈

排序算法

1. 比较类排序

通过比较来决定元素间的相对次序，由于其时间复杂度不能突破 O(nlogn)，因此也称为非线形时间比较类排序

2. 非比较类排序

不通过比较来决定元素间的相对次序，他可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序

比较类排序
交换排序：冒泡排序、快速排序
插入排序：简单插入排序、希尔排序
选择排序：简单选择排序、堆排序
归并排序：二路归并排序、多路归并排序

非比较类排序：计数排序、桶排序、基数排序

选择排序：
每次找最小值，然后放到待排序数组的起始位置

思想

最大误区：做题只做一遍，至少做5遍

思想：

1. 空间换时间
2. 升维

二叉树

想要存储一颗二叉树，一种是基于指针或者引用的二叉链式存储法；一种是基于数组的顺序存储法

• 顺序存储法：把根节点存储在下标 i=1 的位置，那左子节点存储在下表 2*i=2 的位置，右子节点存储在 2*i+1=3的位置，依次类推。

如果二叉树是完全二叉树，用数组存储无疑是最节省内存的一种方式