LeetCode： 146. LRU Cache

题目描述

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

解题思路

用一个链表来记录顺序， 用一个哈希表来记录 key-value。

AC 代码

class LRUCache {
private: 
    int m_capacity;
    int m_count;
    list<int> m_keys;
    unordered_map<int, int> m_cache;
public:
    LRUCache(int capacity) : m_capacity(capacity), m_count(0) {
    }

    int get(int key) {
        auto iter = m_cache.find(key);
        auto iterk = find(m_keys.begin(), m_keys.end(), key);
        if(iter != m_cache.end() && iterk != m_keys.end())
        {
            m_keys.erase(iterk);
            m_keys.push_back(key);
            return iter->second;
        }
        else
        {
            return -1;
        }
    }

    void put(int key, int value) {
        auto iter = find(m_keys.begin(), m_keys.end(), key);
        if(iter != m_keys.end())
        {
            m_keys.erase(iter);
            --m_count;
        }

        if(m_count == m_capacity)
        {
            m_cache[m_keys.front()] = -1;
            m_keys.pop_front();
            --m_count;
        }

        m_keys.push_back(key);
        m_cache[key] = value;
        ++m_count;
    }
};

/** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */