运用你所掌握的数据结构,设计和实现一个 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
tips:
数据结构:用unordered_map实现O(1)内访问,用list的O(1)时间的插入删除特性,实现维护缓冲区的大小以及优先顺序。
class LRUCache {
private:
int capacity;
list<pair<int,int>> cache;
unordered_map<int, list<pair<int,int>>::iterator> mymap;
public:
LRUCache(int cap) {
capacity=cap;
}
int get(int key) {
if(mymap.find(key)!=mymap.end()) {
auto iter= mymap[key];
int val=(*iter).second;
cache.erase(iter);
cache.push_front({key,val});
mymap[key]=cache.begin();
return val;
} else {
return -1;
}
}
void put(int key, int value) {
if(mymap.find(key)!=mymap.end()) {
auto iter= mymap[key];
cache.erase(iter);
cache.push_front({key,value});
mymap[key]=cache.begin();
} else {
// 判断容量是否已满
if(cache.size() == capacity) {
auto back=cache.back();
mymap.erase(back.first);
cache.pop_back();
}
cache.push_front({key,value});
mymap[key]=cache.begin();
}
}
};
java 版本,手写一个双向链表,外加HashMap 实现。
双向链表中可以先设置头尾的虚节点,避免复杂的判断。
attention :
- 超出容量限制的时候,要同时从链表和map里面删除最后的元素。
- put已有元素时,也要把该元素提到链表的头部
class DLinkList{
DLinkList left;
DLinkList right;
int val;
int key;
DLinkList(int key, int val) {
this.key = key;
this.val = val;
this.left = null;
this.right = null;
}
}
class LRUCache {
private Map<Integer, DLinkList> map;
private DLinkList head;
private DLinkList tail;
private int capacity;
public LRUCache(int capacity) {
map = new HashMap<>();
this.capacity = capacity;
this.head = new DLinkList(-1,-1);
this.tail = new DLinkList(-1,-1);
head.right = tail;
tail.left = head;
}
public int get(int key) {
if(map.get(key) == null) {
return -1;
} else {
moveToHead(key);
return map.get(key).val;
}
}
public void put(int key, int value) {
if(map.get(key) == null) {
DLinkList node = new DLinkList(key, value);
node.left = head;
node.right = head.right;
head.right.left = node;
head.right = node;
map.put(key, node);
if(map.size() > capacity) {
map.remove(tail.left.key);
tail.left.left.right = tail;
tail.left = tail.left.left;
}
} else {
map.get(key).val = value;
moveToHead(key);
}
}
public void moveToHead(int key) {
DLinkList node = map.get(key);
node.left.right = node.right;
node.right.left = node.left;
node.left = head;
node.right = head.right;
head.right.left = node;
head.right = node;
}
}