面接手はコードの高周波のテーマを引き裂きます:1つのLRU Cacheを実現します
7923 ワード
LRUキャッシュは面接で簡単に合格できる知識点であり、その原理を熟知するほか、簡単な実現も身につけなければならない.2つのhash map+listのデータ構造を採用することで,getとput操作をO(1)の時間的複雑さで実現できる.
class LRUCache {
private:
int size;
list<int> lru; //key
unordered_map<int, list<int>::iterator> map; //key, iterator
unordered_map<int, int> kv; //key, value
void update(int key) {
if (kv.find(key) != kv.end())
lru.erase(map[key]);
lru.push_front(key);
map[key] = lru.begin();
}
void evict() {
map.erase(lru.back());
kv.erase(lru.back());
lru.pop_back();
}
public:
LRUCache(int capacity) {
size = capacity;
}
int get(int key) {
if (kv.find(key) == kv.end())
return -1;
update(key);
return kv[key];
}
void put(int key, int value) {
if (kv.size() == size && kv.find(key) == kv.end())
evict();
update(key);
kv[key] = value;
}
};
/**
* 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);
*/