C++ solution use two hashMap and DoubleLinked list, Two version


  • 0
    A

    The only difference for this two version: one using the c++ built in DoubleLinkedlist and another use the Double Linked list constructor by myself.

    This one using the built in LinkedList

    class LFUCache {
        struct Node{
            int key;
            int val;
            int frequency;
            Node(int key, int val, int frequency){
                this->key = key;
                this->val = val;
                this->frequency = frequency;
            }
        };
        unordered_map<int, list<Node>::iterator> nodes;   // key , node      find the node with the key
        unordered_map<int, list<Node>::iterator> range;   // frequency, node  find the start point of a frequency
        list<Node> cache;
        int capacity;
    public:
        LFUCache(int capacity) {
            this->capacity = capacity;
        }
        
        int get(int key) {
            if(nodes.find(key) == nodes.end())
                return -1;
            increment(key);
            return nodes[key]->val;
        }
        
        void set(int key, int value) {
            if(capacity == 0)
                return;
            if(nodes.find(key) == nodes.end()){
                if(cache.size() == capacity)
                    decrement();
                Node node(key, value, 0);
                auto it = cache.insert(cache.end(), node);
                nodes[key] = it;
                range[0] = it;
               // capacity++;
            }
            nodes[key]->val = value;
            increment(key);
        }
        
        void decrement(){
            Node node = cache.back();
            if(nodes[node.key] == range[node.frequency])
                range.erase(node.frequency);
            nodes.erase(node.key);
            cache.pop_back();
            //capacity--;
        }
        
        void increment(int key){
            list<Node>::iterator it = nodes[key];
            list<Node>::iterator position = range[it->frequency];
    
            if(position == it){
                position++;
                if(position == cache.end() || position->frequency != it->frequency)
                    range.erase(it->frequency);
                else
                    range[position->frequency] = position;
            }
            
            if(range.find(it->frequency+1) != range.end())
                position = range[it->frequency+1];
            
            Node node = *it;
            cache.erase(it);
            it = cache.insert(position, node);
            range[it->frequency+1] = it;
            nodes[key] = it;
            it->frequency++; 
        }
    };
    

    This version use customer LinkedList

    class LFUCache {
        class LinkedList{
        public:
            int key;
            int val;
            int frequency;
            LinkedList* previous;
            LinkedList* next;
            LinkedList(int key, int val, int frequency):key(key), val(val), frequency(frequency), previous(NULL), next(NULL){
            }
        };
        unordered_map<int, LinkedList*> nodes;
        unordered_map<int, LinkedList*> range;
        LinkedList* head;
        LinkedList* tail;
        int size;
        int capacity;
        
    public:
        LFUCache(int capacity) {
            this->capacity = capacity;
            this->size = 0;
            this->head = new LinkedList(0, 0, 0);   // just make add node easier no special purpose
            this->tail = head;
        }
        
        int get(int key) {
    
            if(nodes.find(key) == nodes.end())
                return -1;
            increment(key);
    
            return nodes[key]->val;
    
        }
        
        void set(int key, int value) {
            if(capacity == 0)
                return;
            if(nodes.find(key) == nodes.end()){
                if(size == capacity)
                    decrement();
                LinkedList* node = new LinkedList(key, value, 0);
                node->previous = tail;
                tail->next = node;
                tail = node;
                range[0] = node;
                nodes[key] = node;
                size++;
            }
            nodes[key]->val = value;
            increment(key);
        }
        
        void decrement(){
            LinkedList* node = tail;
            tail = tail->previous;
            tail->next = NULL;
            if(nodes[node->key] == range[node->frequency])
                range.erase(node->frequency);
            nodes.erase(node->key);
            delete node;
            size--;
        }
        
        void increment(int key){
            LinkedList* node = nodes[key];
            LinkedList* position = range[node->frequency];
            if(node == position){
                if(position == tail || position->next->frequency != position->frequency){
                    range.erase(position->frequency);
                    position = position->next;
                }
                else{
                    position = position->next;
                    range[position->frequency] = position;
                }
            }
            
            if(node == tail){
                tail = node->previous;
                tail->next = NULL;
            }
            else{
                node->previous->next = node->next;
                node->next->previous = node->previous;
            }
            node->frequency++;
            if(range.find(node->frequency) != range.end())
                position = range[node->frequency];
            
            if(position == NULL){
                tail->next = node;
                node->previous = tail;
                tail = node;
                node->next = NULL;
            }
            else{
                node->previous = position->previous;
                position->previous = node;
                node->next = position;
                node->previous->next = node;
            }
            
            range[node->frequency] = node;
        }
    };
    

Log in to reply
 

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