Short C++ code using unordered_map works on my machine, but fails on LeetCode


  • 0
    H
    #include <unordered_map>
    #include <iostream>
    using namespace std;    
    
    class LRUCache{
    private:
    	unordered_map<int, int>  cache;
    	int c_capacity = 0;
    public:
    	LRUCache(int capacity) {
    		c_capacity = capacity;
    	}
    
    	int get(int key) {
    		auto key_item = cache.find(key);
    		if (key_item != cache.end()){
    			int val = key_item->second;
    			cache.erase(key);
    			cache.insert({ key, val });
    			return val;
    		}
    		else return -1;
    	}
    
    	void set(int key, int value) {
    		auto val = cache.find(key);
    		if (val != cache.end())
    			cache.erase(key);
    		cache.insert({ key, value });
    		if (cache.size() > c_capacity)
    			cache.erase(cache.begin());			
    	}    	
    };

  • 0
    D

    You used unordered_map and it is un-ordered as its name says. You may use doubly linked list or std::list.

    Good luck!


  • 0
    H
    #include <iostream>
    #include <map>
    using namespace std;
    
    struct Node{
        Node* prev ,*next;
        int key, value;
        Node(int k, int v){
            key = k; value = v;
            next = prev = NULL;
        }
    };
    
    class LRUCache{
        private:
            std::map<int, Node*> key_map;
            Node *front, *back;
            int size, c_capacity = 0;
    
            void eraseNodePtr(Node* node){
                if (front == NULL || node == NULL) 	return;
    
                if (node == front)	front = node->next;
                if (node == back)  back = node->prev;
    
                if (node->next != NULL)   node->next->prev = node->prev;
                if (node->prev != NULL)   node->prev->next = node->next;
    
                delete node; 	size--;		
            }
    
            Node* push_back(int k, int v){
                Node *n = new Node(k, v);
                if (back == NULL){
                    front = n; 	back = n;
                }
                else{
                    back->next = n;
                    n->prev = back;
                    back = n;
                }
                size++;
                return n;
            }		
        public:
            LRUCache(int capacity) : front(NULL), back(NULL), size(0), c_capacity(capacity){}
    
            ~LRUCache(){
                Node *T = back;
                while (T != NULL){
                    Node *T2 = T; T = T->prev; delete T2;
                }
                front = NULL; back = NULL; size = 0;
            }
    
            int get(int key) {
                if (key_map.count(key)){
                    int val = key_map[key]->value;
                    eraseNodePtr(key_map[key]);
                    key_map[key] = push_back(key, val);
                    return val;
                }
                else return -1;
            }
    
            void set(int key, int value) {
                if (key_map.count(key)){
                   eraseNodePtr(key_map[key]);
                   key_map.erase(key);
               }
    	
               Node* n = push_back( key, value );
               key_map.insert({ key, n });
    
               if ( size > c_capacity ){			
                   key_map.erase(front->key);
                   eraseNodePtr(front);
               }
            }	
    };

  • 0
    H

    David, thank you for pointing out this.

    After several tries on std::list for cache and std::map for recording iterators of (key,value) pairs with O(1) complexity, LeetCode still gave me Time Limit Exceeded. So I decided to embed the doubly linked list in LRUCache class for easily accessing, deleting and inserting nodes.


Log in to reply
 

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