C++ Linked List + Hash solution with comments.


  • 0
    A
    class LRUCache{
    public:
        LRUCache(int capacity) {
            head = tail = nullptr;
            m_capacity = capacity;
            m_size = 0;
        }
        
        int get(int key) {
            if( !m_hash.count( key ) )
                return -1; // we don't have the key
    
            assert( head && tail && m_size >= 1 );
            ListNode *prev = m_hash[ key ];
            ListNode *me = prev ? prev->next : head;
            assert( me );
            assert( me->key == key );
            if( me != tail ) {
                assert( m_size >= 2 ); // there's at least me and tail
                assert( me->next ); // me is not the tail!
    
                // detach 'me' from present location
                m_hash[ me->next->key ] = prev;
                ( prev ? prev->next : head ) = me->next;
                me->next = nullptr;
    
                // attach 'me' to the end
                m_hash[ key ] = tail;
                tail->next = me;
                tail = me;
            }
            return me->value;
        }
        
        void set(int key, int value) {
            if( m_capacity <= 0 )
                return; // nothing can be done
    
            if( m_hash.count( key ) ) { // if the key already exists...
                get( key ); // ... just refresh it,
                tail->value = value; // and set the new value.
                return;
            }
            
            m_hash[ key ] = tail;
            tail = ( tail ? tail->next : head ) = new ListNode{ key, value, nullptr };
            ++m_size;
            
            if( m_size > m_capacity ) {
                // we mustdrop the least recently used node
                ListNode *deleteMe = head;
                head = deleteMe->next;
                m_hash.erase( deleteMe->key );
                m_hash[ head->key ] = nullptr;
                delete deleteMe;
                --m_size;
            }
        }
        
    private:
    
        // head is the LRU and tail is the MRU element
        // A singly linked list suffices
        struct ListNode { int key; int value; struct ListNode *next; } *head, *tail;
        
        /* The hashtable maps keys to the previous node in the list,
           i.e. m_hash[key]->next is the node that corresponds to key.
           If the key corresponds to the head node, m_hash[key] is null.
           This "previous" antic enables us to use a singly linked list.
        */
        std::unordered_map<int, ListNode *> m_hash;
    
        int m_size; // how many elements are currently in the cache?
        int m_capacity; // max. elements allowed in the cache
        
    };
    

Log in to reply
 

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