92 ms solution with Cartesian tree


  • 0
    D
    #include <iostream>
    #include <cstdio>
    
    using namespace std;
    
    struct node_t{
        int m_key;
        int m_value;
        int m_priority;
        node_t* m_left;
        node_t* m_right;
        node_t() : m_key(0), m_value(0), m_priority(0), m_left(NULL), m_right(NULL) {}
        void show(){
            printf("key:%d, value:%d, p:%d\n", m_key, m_value, m_priority);
        }
    };
    
    void show_tree(node_t *t, int indent){
        if(!t) return;
        for(int i = 0; i < indent; i++) printf(" ");
        t->show();
        show_tree(t->m_left, indent + 4);
        show_tree(t->m_right, indent + 4);
    }
    
    void cut_tree(node_t *t, int v, node_t* &l, node_t* &r) {
        node_t *pTree;
        
        l = r = NULL;
        if(!t) return;
        
        if(v < t->m_key){
            cut_tree(t->m_left, v, l, r);
            pTree = t;
            pTree->m_left = r;
            r = pTree;
        }else{
            cut_tree(t->m_right, v, l, r);
            pTree = t;
            pTree->m_right = l;
            l = pTree;
        }
    }
    
    void cat_tree(node_t* &t, node_t* &l, node_t* &r){
        if(!l) t = r;
        else if(!r) t = l;
        else if(l->m_priority < r->m_priority){
            cat_tree(t, l->m_right, r);
            l->m_right = t;
            t = l;
        }else{
            cat_tree(t, l, r->m_left);
            r->m_left = t;
            t = r;
        }
    }
    
    void insert_tree(node_t* &t, node_t* n){
        node_t *l, *r;
        if(!n) return;
        n->m_left = n->m_right = NULL;
        if(!t){
            t = n;
            return;
        }
        if(n->m_priority < t->m_priority){
            cut_tree(t, n->m_key, l, r);
            n->m_left = l;
            n->m_right = r;
            t = n;
        }else if(n->m_key < t->m_key){
            insert_tree(t->m_left, n);
        }else{
            insert_tree(t->m_right, n);
        }
    }
    
    int search_tree(node_t *t, int key){
        if(!t) return -1;
        if(t->m_key == key) return t->m_value;
        if(key < t->m_key) return search_tree(t->m_left, key);
        else return search_tree(t->m_right, key);
    }
    
    void extract_tree(node_t* &t, int key){
        if(!t) return;
        node_t *tree = NULL;
        if(t->m_key == key){
            cat_tree(tree, t->m_left, t->m_right);
            t = tree;
        }else if(key < t->m_key){
            extract_tree(t->m_left, key);
        }else{
            extract_tree(t->m_right, key);
        }
    }
    
    class LRUCache{
    public:
        int m_c;
        int m_size;
        node_t *m_lru;
        int m_access;
        
        LRUCache(int capacity) {
            m_c = capacity;
            m_lru = NULL;
            m_access = 0;
            m_size = 0;
        }
        
        int get(int key) {
            int v;
            v = search_tree(m_lru, key);
            if(v != -1){
                extract_tree(m_lru, key);
                node_t *n = new node_t();
                n->m_priority = m_access++;
                n->m_key = key;
                n->m_value = v;
                insert_tree(m_lru, n);
            }
            return v;
        }
        
        void set(int key, int value) {
            int v;
            v = search_tree(m_lru, key);
            if(v != -1){
                extract_tree(m_lru, key);
                m_size --;
            }
            while(m_size >= m_c){
                extract_tree(m_lru, m_lru->m_key);
                m_size --;
            }
            node_t *n = new node_t();
            n->m_priority = m_access++;
            n->m_key = key;
            n->m_value = value;
            insert_tree(m_lru, n);
            m_size++;
        }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.