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.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

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

解析：

此题目让设计一个LRU算法，首先看一下LRU算法：

按照英文的直接原义就是Least Recently Used,最近最久未使用法，它是按照一个非常著名的计算机操作系统基础理论得来的：最近使用的页面数据会在未来一段时期内仍然被使用,已经很久没有使用的页面很有可能在未来较长的一段时间内仍然不会被使用。基于这个思想,会存在一种缓存淘汰机制，每次从内存中找到最久未使用的数据然后置换出来，从而存入新的数据。

这里有两个方法，get和put，get是根据key从cache中检索信息，如果key不存在则返回-1，否则，返回对应的value，同时将此(key,value)置于cache首位置；put是将(key,value)插入到缓存中。具体实现时我们需要三个私有变量，cap, li和m，其中 cap是缓存器的容量大小，li是保存缓存器内容的列表，m是HashMap，保存关键值 key 和缓存器各项的迭代器之间映射，方便我们以 O(1) 的时间内找到目标项。

具体实现代码如下：

class LRUCache {
public:
    LRUCache(int capacity) {
        cap = capacity;
    }
    
    int get(int key) {
        auto it = cahe.find(key);
        if (it == cahe.end())//如果key不存在，则返回-1
            return -1;
        li.splice(li.begin(), li, it->second);//如果存在，则将对应键值对置于链表首
        return it->second->second;
    }
    
    void put(int key, int value) {
        auto it = cahe.find(key);
        if (it != cahe.end())//如果存在则删除原有元素
            li.erase(it->second);
        li.push_front(make_pair(key, value));
        cahe[key] = li.begin();//存放key和对应List位置的映射关系
        if(cahe.size() > cap)//当前超过容量大小，删除末尾最近未使用的数据
        {
            int k = li.rbegin()->first;
            li.pop_back();
            cahe.erase(k);
        }
    }
    private:
        int cap;//标识容量大小
        list<pair<int, int>> li;//存放键值对的缓存列表
        unordered_map<int, list<pair<int, int>>::iterator > cahe;//hashmap 方便以O(1)的方式查找目标 存放key和对应位置的映射关系
};

/**
 * 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);
 */