題目描述：為最近最少使用緩存LRU Cache設(shè)計數(shù)據(jù)結(jié)構(gòu)虏缸，它支持兩個操作：get和put温艇。

• get(key)：如果key在cache中鹅很，則返回對應(yīng)的value值攒至，否則返回-1

• set(key,value)：如果key不在cache中厚者，則將該(key,value)插入cache中（注意，如果cache已滿迫吐，則必須把最近最久未使用的元素從cache中刪除）库菲；如果key在cache中，則重置value的值渠抹。

要求兩操作的時間復(fù)雜度都為O(1)蝙昙。如：

LRUCache cache = new LRUCache( 2 ); //capacity 設(shè)為2
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是操作系統(tǒng)中內(nèi)存頁面置換算法，Cache算法和內(nèi)存頁面置換算法的核心思想是一樣的：都是在給定一個限定大小的空間的前提下梧却，設(shè)計一個原則如何來更新和訪問其中的元素奇颠。LRU算法的設(shè)計原則是：如果一個數(shù)據(jù)在最近一段時間沒有被訪問到，那么在將來它被訪問的可能性也很小放航。也就是說烈拒，當(dāng)限定的空間已存滿數(shù)據(jù)時，應(yīng)當(dāng)把最久沒有被訪問到的數(shù)據(jù)淘汰。如大小為4的cache傳入序列為A B C D E D F：

• void splice (iterator position, list& x);
  //將列表x中的所有元素移到當(dāng)前l(fā)ist中，從當(dāng)前列表的position指向的位置開始独撇，操作后列表x為空

• void splice (iterator position, list& x, iterator i); //將列表x中迭代器 i 指向的元素移到當(dāng)前l(fā)ist的position指向的位置處屑墨，操作后 i 指向的元素從列表x中被移除，所以迭代器 i 此時是invalid的纷铣；position是當(dāng)前列表的迭代器卵史，i是列表x的迭代器

• void splice (iterator position, list& x, iterator first, iterator last);
  //將列表x中[first, last)的元素移到當(dāng)前l(fā)ist中，從position指向的位置開始搜立；first, last是列表x的迭代器
  代碼：

class LRUCache {
private:
    //cache結(jié)點(diǎn)的結(jié)構(gòu)以躯，一鍵一值
    struct CacheNode{
        int key;
        int val;
        CacheNode(int k, int v):key(k), val(v){}
    };
    //LRUCache的屬性，一個鏈表一個哈希表
    list<CacheNode> cacheList;        //cache結(jié)點(diǎn)的列表
    unordered_map<int, list<CacheNode>::iterator> cacheMap;          //哈希表的值是結(jié)點(diǎn)的鍵啄踊，值是鏈表迭代器
    int capacity;            //cache大小
    
public:
    //初始化cache大小
    LRUCache(int capacity) {
        this -> capacity = capacity;
    }
    //查找
    int get(int key) {
        if (cacheMap.find(key) == cacheMap.end()) return -1;
        //將要訪問的結(jié)點(diǎn)移到鏈表頭
        cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
        cacheMap[key] = cacheList.begin();
        return cacheMap[key] -> val;
    }
    //插入
    void put(int key, int value) {
        if (cacheMap.find(key) == cacheMap.end())
        {  //沒找到忧设，首先要判斷鏈表是否已滿
            if (cacheList.size() == capacity)
            {  //先在哈希表中刪除鏈表的尾結(jié)點(diǎn)的鍵對應(yīng)的迭代器，再在鏈表尾刪除此結(jié)點(diǎn)
                cacheMap.erase(cacheList.back().key);
                cacheList.pop_back();
            }
            //將該結(jié)點(diǎn)插到表頭颠通，再在哈希表中加入其迭代器
            cacheList.push_front(CacheNode(key, value));
            cacheMap[key] = cacheList.begin();
        }
        else         //找到址晕，更新其值且將該結(jié)點(diǎn)移到鏈表頭，最后更新哈希表的值——該鍵的迭代器顿锰，為表頭迭代器
        {
            cacheMap[key] -> val = value;
            cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
            cacheMap[key] = cacheList.begin();
        }
    }
    
};

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