注意：这篇文章上次更新于931天前，文章内容可能已经过时。
写一些刷题常用数据结构
单链表节点
struct ListNode{
int val;
struct ListNode* next;
ListNode():val(-1),next(nullptr){}
ListNode(int x):val(x),next(nullptr){}
};二叉树节点
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){}
}并查集
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 的算法也可以用并查集解决
LRUCatch
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 LRUCatch{
public:
unordered_map<int,Node*> k_to_n;
Node* head;
Node* tail;
int size;
int cap;
LRUCatch(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 上多数题目是这样的。
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);
}
};未完待续…
