Share My clear solution, easy to understand.


  • 0
    Y
    struct NodeVal{
        NodeVal *pre, *next;
        int val, key;
        NodeVal(int v, int k):val(v), key(k), pre(NULL), next(NULL){}
    };
    
    struct NodeFreq{
        NodeVal *front, *back;
        NodeFreq *pre, *next;
        int freq;
        NodeFreq(int f):freq(f){
            front = new NodeVal(-1, -1);
            back = new NodeVal(-1, -1);
            front -> next = back;
            back -> pre = front;
        }
    };
    
    
    class LFUCache {
    public:
        unordered_map<int, pair<NodeVal*, NodeFreq*>> imv;
        NodeFreq *front, *back;
        int size, capacity;
        LFUCache(int capacity) {
            this -> capacity = capacity;
            this -> size = 0;
            front = new NodeFreq(-1);
            back = new NodeFreq(-1);
            front -> next = back;
            back -> pre = front;
        }
    
        void delVal(NodeVal *nv){        
            nv -> pre -> next = nv -> next;
            nv -> next -> pre = nv -> pre;
            free(nv);
        }
    
        void delFreq(NodeFreq *nf){
            nf -> pre -> next = nf -> next;
            nf -> next -> pre = nf -> pre;
            free(nf);
        }
    
        NodeFreq* addFreq(NodeFreq *nf, int freq){
            NodeFreq *node = new NodeFreq(freq);
            node -> next = nf -> next;
            node -> pre = nf;
            nf -> next = node;
            node -> next -> pre = node;
    
            return node;
        }
    
        NodeVal* addVal(NodeVal *nv, int val, int key){
            NodeVal *node = new NodeVal(val, key);
            node -> next = nv -> next;
            node -> pre = nv;
            nv -> next = node;
            node -> next -> pre = node;
    
            return node;
        }
        
        int get(int key) {
            if(imv.count(key) == 0) return -1;
    
            NodeVal *nv = imv[key].first;
            NodeFreq *nf = imv[key].second;
            
            if(nf -> next -> freq != nf -> freq + 1){
                addFreq(nf, nf -> freq + 1);
            }
            NodeFreq *nnf = nf -> next;
            NodeVal *nnv = addVal(nnf -> front, nv -> val, nv -> key);
            delVal(nv);
            if(nf -> front -> next == nf -> back)
                delFreq(nf);
    
            imv[key].first = nnv;
            imv[key].second = nnf;
    
            return nnv -> val;
        }
        
        void put(int key, int value) {
            if(capacity <= 0) return;
    
            if(imv.count(key) != 0){
                NodeVal *nv = imv[key].first;
                NodeFreq *nf = imv[key].second;
                
                if(nf -> next -> freq != nf -> freq + 1){
                    addFreq(nf, nf -> freq + 1);
                }
                NodeFreq *nnf = nf -> next;
                NodeVal *nnv = addVal(nnf -> front, value, key);
                delVal(nv);
                if(nf -> front -> next == nf -> back)
                    delFreq(nf);
    
                imv[key].first = nnv;
                imv[key].second = nnf;
    
                return ;
            }
    
            NodeFreq *dnf = this -> front -> next;
    
            if(size == capacity){
                NodeVal *dnv = dnf -> back -> pre;
                imv.erase(dnv -> key);
                delVal(dnv);
                size --;
                if(dnf -> front -> next == dnf -> back)
                    delFreq(dnf);
            }
            dnf = this -> front -> next;
            if(dnf -> freq != 0)
                addFreq(this -> front, 0);
            NodeFreq *nnf = this -> front -> next;
            NodeVal *nnv = addVal(nnf -> front, value, key);
    
            imv[key] = make_pair(nnv, nnf);
            size ++;
    
            // cout << "A: " << front -> next -> back -> pre -> key << endl;
        }
    };
    

Log in to reply
 

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