題目描述
運用你所掌握的數據結構，設計和實現一個 LRU (最近最少使用) 緩存機制。它應該支持以下操作： 獲取數據 get 和 寫入數據 put 。
獲取數據 get(key) - 如果密鑰 (key) 存在於緩存中，則獲取密鑰的值（總是正數），否則返回 -1。
寫入數據 put(key, value) - 如果密鑰不存在，則寫入其數據值。當緩存容量達到上限時，它應該在寫入新數據之前刪除最近最少使用的數據值，從而為新的數據值留出空間。
進階:
你是否可以在 O(1) 時間複雜度內完成這兩種操作？
示例:
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
思路解析
這道題是讓我們實現一個 LRU 緩存器，LRU是 Least Recently Used 的簡寫，就是最近最少使用的意思。
這個緩存器主要有兩個成員函數，get 和 put。
其中 get 函數是通過輸入 key 來獲得 value，如果成功獲得後，這對 (key, value) 升至緩存器中最常用的位置（頂部），如果 key 不存在，則返回 -1 。
而 put 函數是插入一對新的 (key, value)，如果原緩存器中有該 key，則需要先刪除掉原有的，將新的插入到緩存器的頂部。如果不存在，則直接插入到頂部。
若加入新的值後緩存器超過了容量，則需要刪掉一個最不常用的值，也就是底部的值。
具體實現時我們需要三個私有變量，cap , l 和 m，其中 cap 是緩存器的容量大小，l 是保存緩存器內容的列表，m 是 HashMap，保存關鍵值 key 和緩存器各項的迭代器之間映射，方便我們以 O(1) 的時間內找到目標項。
然後我們再來看 get 和 put 如何實現。
其中，get 相對簡單些，我們在 m 中查找給定的key，若不存在直接返回 -1；如果存在則將此項移到頂部。
對於 put ，我們也是現在 m 中查找給定的 key，如果存在就刪掉原有項，並在頂部插入新來項，然後判斷是否溢出，若溢出則刪掉底部項(最不常用項)。
動畫演示
參考代碼
class LRUCache{
public:
LRUCache(int capacity) {
cap = capacity;
}
int get(int key) {
auto it = m.find(key);
if (it == m.end()) return -1;
l.splice(l.begin(), l, it->second);
return it->second->second;
}
void put(int key, int value) {
auto it = m.find(key);
if (it != m.end()) l.erase(it->second);
l.push_front(make_pair(key, value));
m[key] = l.begin();
if (m.size() > cap) {
int k = l.rbegin()->first;
l.pop_back();
m.erase(k);
}
}
private:
int cap;
list<pair>> l;
unordered_map>::iterator> m;
};
/<pair>代碼截圖
閱讀更多 五分鐘學算法 的文章
