運用你所掌握的數(shù)據(jù)結(jié)構(gòu)，設(shè)計和實現(xiàn)一個 LRU (最近最少使用) 緩存機制。它應(yīng)該支持以下操作： 獲取數(shù)據(jù) get 和 寫入數(shù)據(jù) put 。

獲取數(shù)據(jù) get(key) - 如果密鑰 (key) 存在于緩存中，則獲取密鑰的值（總是正數(shù)），否則返回 -1。
寫入數(shù)據(jù) put(key, value) - 如果密鑰不存在，則寫入其數(shù)據(jù)值。當(dāng)緩存容量達到上限時，它應(yīng)該在寫入新數(shù)據(jù)之前刪除最近最少使用的數(shù)據(jù)值，從而為新的數(shù)據(jù)值留出空間。

你是否可以在 O(1) 時間復(fù)雜度內(nèi)完成這兩種操作？

實例：

LRUCache cache = new LRUCache( 2 /* 緩存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 該操作會使得密鑰 2 作廢
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 該操作會使得密鑰 1 作廢
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

思考：

在O(1)的時間復(fù)雜度里面完成對key對應(yīng)val的獲取，肯定是使用hash map的方式；同時需要考慮LRU，
可以使用鏈表，通過erase(list iterator)來完成O(1)時間內(nèi)的刪除元素，同時將最近使用的元素放到鏈表的頭或者尾部;
(1)get函數(shù)，通過hash map查找是否存在對應(yīng)的key，不存在則返回-1；
存在則將使用過的元素放置到鏈表的頭部；
(2)put函數(shù)，先對該key值進行搜索是否存在，如果存在，則直接修改原來對應(yīng)的val，同時將其放到鏈表的頭部（表示最近被使用）；
如果不存在，則需要考慮是否隊列已經(jīng)滿了，如果已經(jīng)滿了，則需要將鏈表尾部的元素移除，再將新的元素移入；

題目的難點在于設(shè)計數(shù)據(jù)結(jié)構(gòu)完成操作。

1.使用hash map在時間復(fù)雜度O(1)的查找key值對應(yīng)的val；
2.同時要在O(1)時間內(nèi)找到對應(yīng)鏈表的節(jié)點，完成在原鏈表中的移除并且添加到鏈表頭部；
因此設(shè)計的時候應(yīng)該是 unordered_map<key, list::iterator>
3.在這個緩沖區(qū)滿的時候，找到list對應(yīng)的節(jié)點進行刪除，同時還需要刪除原h(huán)ash map中的內(nèi)容，
所以需要從list中需要存儲key值，這樣才能返回hash map中去刪除元素
list<pair<key, val>> unordered_map<key, list<pair<key, val>>::iterator>

代碼：

class LRUCache {
public:
    LRUCache(int capacity) {
        this->max_cap = capacity;
        this->LRUMap.clear();
        this->LRUList.clear();
    }
    
    // 通過key來獲取val，這里不僅要判斷key是否存在，同時要考慮如果存在則使用了要將該數(shù)值放在隊列的頭部
    int get(int key) {
        unordered_map<int, list<pair<int, int>>::iterator>::iterator iter = this->LRUMap.find(key);
        if(iter == this->LRUMap.end()) {
            return -1;
        }else {
            // 處理LRU緩沖隊列
            int value = iter->second->second;
            LRUList.erase(iter->second);
            pair<int, int> pair_ = make_pair(key, value);
            LRUList.push_front(pair_);
            this->LRUMap[key] = this->LRUList.begin();
            return value;
        }
    }
    
    // 添加一個數(shù)值的時候首先判斷是否已經(jīng)存在了
    void put(int key, int value) {
        unordered_map<int, list<pair<int, int>>::iterator>::iterator iter_ = this->LRUMap.find(key);
        if(iter_ != this->LRUMap.end()) {
            list<pair<int, int>>::iterator _iter = iter_->second;
            this->LRUList.erase(_iter);
            this->LRUList.push_front(pair<int, int>(key, value));
            this->LRUMap[key] = this->LRUList.begin();
            return ;
        }
        if(this->LRUMap.size() == this->max_cap) {
            // 隊滿
            int key_ = this->LRUList.back().first;
            list<pair<int, int>>::iterator list_iter = this->LRUMap[key_];
            this->LRUList.erase(list_iter);
            this->LRUMap.erase(key_);
        }
        pair<int, int> pair_ = make_pair(key, value);
        this->LRUList.push_front(pair_);
        this->LRUMap[key] = this->LRUList.begin();
    }
private:
    int max_cap; // 最大容量
    unordered_map<int, list<pair<int, int>>::iterator> LRUMap;
    list<pair<int, int>> LRUList; // 用于判定清除哪一個元素,超過時候每次刪除list尾巴
};

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