刷题常用数据结构

注意：这篇文章上次更新于1555天前，文章内容可能已经过时。

This article was last updated1555 days ago, the content may be outdated.

写一些刷题常用数据结构

单链表节点

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 的算法也可以用并查集解决

LRUCache

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 上多数题目是这样的。

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);
    }
    
};

未完待续…