Accept C++ Solution, 100ms


  • 0
    D

    class LRUCache{
    private:
    struct item_t {
    int key, val;
    item_t(int k, int v) : key(k), val(v) {}
    };

    typedef list<item_t> list_t;
    typedef std::unordered_map<int, list_t::iterator> dict_t; // { key: list_t::iterator}
    
    dict_t m_dict; // {key : list_iter}
    list_t m_list; // FIFO + LRU, front()==LRU, list<item_t(key,value)>
    int capacity;
    
    // remove LRU item at front of the list
    void remove_LRU_item() {
        int pop_key = m_list.front().key;
        m_dict.erase(pop_key);
        m_list.pop_front();
    }
    
    // add item at the end of the list
    void add_new_item(int key, int value) {
        m_list.push_back(item_t(key, value));
        m_dict[key] = (--m_list.end());
    }
    
    // get value and promote item to the end of the list
    int get_value_and_promote_key(int key) {
        list_t::iterator it = m_dict[key];
        item_t item = item_t(it->key, it->val);
        m_list.erase(it);
        m_list.push_back(item);
        m_dict[key] = (--m_list.end());
        return item.val;
    }
    

    public:
    LRUCache(int capacity) {
    this->capacity = capacity;
    }

    int get(int key) {
        if (m_dict.find(key) == m_dict.end()) {
            return -1;
        } else {
            return get_value_and_promote_key(key);
        }
    }
    
    void set(int key, int value) {
        // cout<<"set key:"<<key<<" value:"<<value<<endl;
        if (capacity == 0) return;
    
        // item not found
        if (m_dict.find(key) == m_dict.end()) {
            // remove LRU item if out of capacity
            if (!m_dict.empty() && m_dict.size() == capacity) {
                remove_LRU_item();
            }
    
        } else { // item found, move item to the end of the list
            m_list.erase(m_dict[key]);
        }
        
        add_new_item(key, value);
    }
    

    };


Log in to reply
 

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