我們可以用一個 vector 來儲存 (key, value) pair，越晚被使用過的 pair 就存在越前面，所以如果 set 時 vector 已經滿了，那就把最後一個丟掉。
class LRUCache {
public:
LRUCache(int capacity) {
cap = capacity;
db.reserve(cap);
}
int get(int key) {
for(int i=0; i<db.size(); i++){
pair<int, int> p = db[i];
if(p.first == key) {
pair<int, int> tmp = p;
db.erase(db.begin()+i);
db.insert(db.begin(), 1, tmp);
return tmp.second;
}
}
return -1;
}
void put(int key, int value) {
// If key is in db
bool foundKey = false;
for(int i=0; i<db.size(); i++){
pair<int, int> p = db[i];
if(p.first == key) {
foundKey = true;
p.second = value;
// Move p to the front
pair<int, int> tmp = p;
db.erase(db.begin()+i);
db.insert(db.begin(), 1, tmp);
}
}
// key is not in the db
if(!foundKey) {
if(db.size() == cap) {
db.pop_back();
db.insert(db.begin(),1,make_pair(key, value));
}
else {
db.insert(db.begin(),1,make_pair(key, value));
}
}
cout << "db: " << endl;
for(auto p: db) {
cout << "(" << p.first << ", " << p.second << "), ";
}
cout << endl;
}
private:
int cap;
vector<pair<int, int>> db;
};
/**
* 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);
*/
解法二 - Hash Table + Doubly Linked List
因為題目有要求 get 跟 set 都能在 O(1) 內解決，所以自然會想到要用 Hash Table。不過下一件事就是，該怎麼 maintain least recently used 這件事，我們可以用一個 doubly linked list 來幫助。
每一個 linked list node 會儲存 value，然後 Hash Table 會儲存 (key, (value, list node position)) 這樣的 pair。