写一些刷题常用数据结构

Some common data structures used in problem solving

单链表节点

Singly Linked List Node

1
2
3
4
5
6
struct ListNode{
	int val;
    struct ListNode* next;
    ListNode():val(-1),next(nullptr){}
    ListNode(int x):val(x),next(nullptr){}
};

二叉树节点

Binary Tree Node

1
2
3
4
5
6
7
struct TreeNode{
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
    TreeNode(int x):val(x),left(nullptr),right(nullptr){}
    TreeNode():val(-1),left(nullptr),right(nullptr){}
};

并查集

Union-Find (Disjoint Set)

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
class UF{
public:
    int cap_;
    int cnt_;
    vector<int> parent;
    
    UF(int cap){
        cap_ = cap;
        cnt_ = cap;
        parent = vector<int>(cap);
        for(int i = 0; i < cap;i++){
            parent[i] = i;
        }
    }
    
    int find(int x){
        while(x != parent[x]){
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }
    
    void connect(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        if( root_x != root_y ){
            parent[root_x] = root_y;
            cnt_--;
        }
    }
    
    bool is_connected(int x,int y){
        int root_x = find(x);
        int root_y = find(y);
        return root_y == root_x;
	}
    
    int get_count(){
        return cnt_;
    }
};

可以求无向图中连通分量的个数

Kruskal 最小生成树算法

有一些 DFS 的算法也可以用并查集解决

Can count the number of connected components in an undirected graph

Kruskal’s minimum spanning tree algorithm

Some DFS algorithms can also be solved with union-find

LRUCache

LRUCache

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
struct Node{
    int key,val;
    struct Node *next,*prev;
    Node():key(-1),val(-1),next(nullptr),prev(nullptr){}
    Node(int k,int v):key(k),val(v),next(nullptr),prev(nullptr){}
};

class LRUCache{
public:
    unordered_map<int,Node*> k_to_n;
    Node* head;
    Node* tail;
    int size;
    int cap;
    LRUCache(int n){
        cap = n;
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
        size = 0;
        k_to_n = unordered_map<int,Node*>();
    }
    
    void remove(Node* p){
        if( p == nullptr) return;
        p->next->prev = p->prev;
        p->prev->next = p->next;
        return;
    }
    
    void insert(Node* p){
        if(p == nullptr) return;
        p->next = head->next;
        p->prev = head;
        head->next->prev = p;
        head->next = p;
        return;
    }
    
    int get(int k){
        if(k_to_n.count(k)){
            Node* p = k_to_n[k];
            remove(p);
            insert(p);
            return p->val;
        }
        else{
            return -1;
        }
    }
    
    void put(int k,int v){
        if(k_to_n.count(k)){
            Node* p = k_to_n[k];
            remove(p);
            insert(p);
            p->val = v;
        }
        else{
            if(size == cap){
                Node* p = new Node(k,v);
                Node* q = tail->prev;
                k_to_n.erase(q->key);
                remove(q);
                insert(p);
            }
            else{
                size++;
                Node* p = new Node(k,v);
                insert(p);
                k_to_n.insert({k,p});
            }
        }
    }    
};

字典树

这个例子的孩子节点 26 个小写字母，Leetcode 上多数题目是这样的。

Trie (Prefix Tree)

In this example the child nodes are 26 lowercase letters, which is the case for most LeetCode problems.

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
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
struct TreeNode{
    int val;
    vector<TreeNode*> children;
    TreeNode(int x):val(x),children(vector<TreeNode*>(26,nullptr)){}
    TreeNode():val(-1),children(vector<TreeNode*>(26,nullptr)){}
};

class trie_map{
private:
    
    TreeNode* root;
    int size;
    TreeNode* get_node(TreeNode* node,string key){
        TreeNode* p = node;
        
        for(int i = 0; i < key.size(); i++){
            if( p == nullptr){
                return nullptr;
            }
            char c = key[i];
            p = p->children[c-'a'];
        }
        return p;
    }
    void recur(TreeNode* node,string& path,vector<string>& res){
        if(node == nullptr){
            return;
        }
        if(node->val != -1){
            res.push_back(path);
        }
        for(int i = 0;i < 26;i++){
            path += ('a'+i);
            recur(node->children[i],path,res);
            path.pop_back();
        }
    }
    void recur(TreeNode* node,string& path,string pattern,int i,vector<string>& res){
        if(node == nullptr){
            return;
        }
        if( i == pattern.size()){
            if(node->val != -1){
                res.push_back(path);
            }
            return;
        }
        char c = pattern[i];
        if( c == '.'){
            for(int i = 0; i < 26;i++){
                path += ('a' + i);
                recur(node->children[i],path,pattern,i+1,res);
                path.pop_back();
            }
        }
        else{
            path += c;
            recur(node->children[c-'a'],path,pattern,i+1,res);
            path.pop_back();
        }
    }
    bool has_key_with_pattern(TreeNode* node,string pattern,int i){
        if( !node) return false;
        if( i == pattern.size()){
            return node->val != -1;
        }
        char c = pattern[i];
        if(c != '.'){
            return has_key_with_pattern(node->children[c-'a'],pattern,i+1);
        }
        for(int j = 0; j < 26;j++){
            if(has_key_with_pattern(node->children[j],pattern,i+1)){
                return true;
            }
        }
        return false;
    }
    TreeNode* put(TreeNode* node,string key,int val,int i){
        if(node == nullptr){
            node = new TreeNode();
        }
        if( i == key.size()){
            node->val = val;
            return node;
        }
        char c = key[i];
        node->children[c-'a'] = put(node->children[c-'a'],key,val,i+1);
        return node;
    }
    TreeNode* remove(TreeNode* node,string key,int i){
        if(node == nullptr){
            return nullptr;
        }
        if( i == key.size()){
            node->val = -1;
        }
        else{
            char c = key[i];
            node->children[c-'a'] = remove(node->children[c-'a'],key,i+1);
        }
        if(node->val != -1){
            return node;
        }
        for(int j = 0; j < 26; j++){
            if(node->children[j] != nullptr){
                return node;
            }
        }
        return nullptr;
    }
    
public:
    trie_map(){
        root = new TreeNode();
        size = 0;
    }
    // 增
    void put(string key,int val){
        if(!contain(key)){
            size++;
        }
        root = put(root,key,val,0);
    }
    // 删
    void remove(string key){
        if(!contain(key)){
            return;
        }
        root = remove(root,key,0);
        size--;
    }
    // 查
    int get(string key){
        TreeNode* p = get_node(root,key);
        if(p == nullptr || p->val == -1){
            return -1;
        }
        return p->val;
    }
    // 判断 key 是否在 map 中
    bool contain(string key){
        return get(key) != -1;
    }
    // 判断是否存在前缀为 prefix 的key
    bool has_key_with_prefix(string prefix){
        return get_node(root,prefix) != nullptr;
    }
    // 在所有 key 中寻找 query 的最短前缀
    string shortest_prefix_of(string query){
        TreeNode* p = root;
        for(int i = 0; i < query.size();i++){
            if(p == nullptr){
                return "";
            }
            if( p->val != -1){
                return query.substr(0,i);
            }
            char c = query[i];
            p = p->children[c - 'a'];
        }
        if(p && p->val != -1){
            return query;
        }
        return "";
    }
    // 在所有 key 中寻找 query 的最长前缀
    string longest_prefix_of(string query){
        TreeNode* p = root;
        int max_len = 0;
        for(int i = 0;i < query.size();i++){
            if(p == nullptr){
                break;
            }
            if(p->val != -1){
                max_len = i;
            }
            char c= query[i];
            p = p->children[c-'a'];
        }
        if( p && p->val != -1){
            return query;
        }
        return query.substr(0,max_len);
    }
    // 搜索所有 prefix 为前缀的 key
    vector<string> keys_with_prefix(string prefix){
        vector<string> res;
        TreeNode* p = get_node(root,prefix);
        if(!p){
            return res;
        }
        // DFS 遍历以 p 为根的树
        string path;
        recur(p,path,res);
        return res;
    }
    // 通配符 '.' 匹配任意字符
    vector<string> keys_with_pattern(string pattern){
        vector<string> res;
        string path;
        recur(root,path,pattern,0,res);
        return res;
    }
    bool has_key_with_pattern(string pattern){
        return has_key_with_pattern(root,pattern,0);
    }
    
};

未完待续…

To be continued…