去年網易秋招面試的時候有一道現場手撕LRU的題，跟這道幾乎一樣，現記錄如下：
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.
先說一下題意，總共有三個操作：
LRUCache obj = new LRUCache(capacity);
obj.put(1, 1);
obj.get(1);
第一個是建立大小為
capacity
的
cache
第二個是在
key=1
的位置放入
value=1
的值
第三個是取出
key=1
位置的
value
需要清楚的幾點：若重複在某個
key
的位置放入值，則原值會被新值覆寫，例如現在又執行
obj.put(1, 2)
，則現在位置1存放的是2，而不是原先的1
此外，題目也寫了是LRU，即最近最少使用，這是作業系統中非常常見的一道題，假設記憶體隻能容納3個頁大小，按照 7 0 1 2 0 3 0 4 的次序通路頁，則通路順序為：
即一旦記憶體被放滿，則首先淘汰距目前最遠時間的頁中的值
那麼回到這道題本身，根據這個流程的了解，最容易想到的一個方法就是：
用一個數組來存儲資料，給每一個資料項标記一個通路時間戳，每次插入新資料項的時候，先把數組中存在的資料項的時間戳自增，并将新資料項的時間戳置為0并插入到數組中。
每次通路數組中的資料項的時候，将被通路的資料項的時間戳置為0。當數組空間已滿時，将時間戳最大的資料項淘汰。
這種方法實作很友善，就不寫了，很明顯，這樣做每次都要通路記憶體頁中的所有資料，複雜度太高，這道題如果用這種方法，也将逾時，這時候就想到，這個
<key, value>
的對應形式不就是
C++
中
map
的方法，而同時，也可以用一個向量來儲存每次讀入的
key
，對于新
key
則置頂，實作如下：
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity, cur = 0; //cur表示已存放的容量
}
int get(int key) {
vector<int>::iterator it = find(v.begin(), v.end(), key); //在vector中找對應的key
if(it == v.end()) return -1;
v.erase(it);
v.emplace_back(key); //每次get都将該key置頂
return m[key];
}
void put(int key, int value) {
if(m[key]) //如果原先key中就有值，則覆寫原值，同時置頂該key
{
m[key] = value;
vector<int>::iterator it = find(v.begin(), v.end(), key);
v.erase(it);
v.emplace_back(key);
return;
}
if(cur == cap)
{
int p = v.front();
m[p] = 0;
v.erase(v.begin());
m[key] = value;
v.emplace_back(key);
}
else
{
cur++;
v.emplace_back(key);
m[key] = value;
}
}
int cap, cur;
vector<int> v;
map<int, int> m;
};
然後想，這段代碼能否再精簡呢？可以看到
v.erase(v.begin());
v.emplace_back(key);
這一段重複了很多次，完全可以用一個函數代替，且
vector
在頭尾的操作很不友善，
C++
有已實作的
list
雙向連結清單。此外，既然每次都要找
key
的位置，為什麼不把這個位置也用一個
map
存放起來呢？
于是有了下面這段代碼：
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity, cur = 0;
}
int get(int key) {
if (cache.find(key) == cache.end())
return -1;
set(key);
return cache[key];
}
void put(int key, int value) {
set(key);
cache[key] = value;
}
private:
int cap, cur;
list<int> recent;
unordered_map<int, int> cache;
unordered_map<int, list<int>::iterator> pos;
void set(int key)
{
if (cache.find(key) != cache.end())
{
list<int>::iterator it = pos[key];
recent.erase(it);
pos.erase(key);
}
else
{
if (cur >= cap)
{
int last = recent.back();
recent.pop_back();
cache.erase(last);
pos.erase(last);
}
else
{
cur++;
}
}
recent.emplace_front(key);
pos[key] = recent.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);
*/
set
函數是将
key
置頂，由于無論是
put
還是
get
，都會使得“最近使用”的值更新，是以單獨用一個函數封裝
最後結果如下，當然這還不算最elegant最高效的，還有待學習~
