题目描述
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.
The cache is initialized with a positive capacity.
Follow up:
Could you do both operations in O(1) time complexity?
Example1:
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.put(4, 4); // evicts key 1
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4
解题思路
- LRU Cache，感觉这里最难的应该是数据结构需要自己定义
- 首先定义LinkNode双向链表的结构（包含，前指针prev，下一个指针next，具体的key，value，构造函数）
- 然后LRU Cache里，私有的数据结构有，容量大小，此时的size（便于要不要扩容），一个基于Hashmap的数据结构，key为int型，value为上面定义的LinkNode，还有指向LinkNode的头尾指针
- LRU Cache里，构造函数有会初始化头尾指针，让其互相指向，容量大小等等
- put的时候，要建立映射关系 mmap[key] = value
C++代码
struct LinkNode{
LinkNode* prev = NULL;
LinkNode* next = NULL;
int key;
int value;
LinkNode() = default;
LinkNode(int key, int value) : key(key), value(value), prev(NULL), next(NULL){}
};
class LRUCache {
private:
int capacity = 0;
int size = 0;
unordered_map<int, LinkNode*> mmap;
LinkNode* head = NULL;
LinkNode* tail = NULL;
public:
LRUCache(int capacity) {
this -> capacity = capacity;
head = new LinkNode;
tail = new LinkNode;
head -> next = tail;
tail -> next = head; // double LinkNOde
}
int get(int key) {
if(mmap.find(key) != mmap.end()){
LinkNode* node = mmap.at(key);
node -> next -> prev = node -> prev;
node -> prev -> next = node -> next;
node -> next = head -> next;
head -> next -> prev = node;
head -> next = node;
node -> prev = head;
return node -> value;
}else{
return -1;
}
}
void put(int key, int value) {
if(get(key) != -1){
head -> next -> value = value; // update
return;
}
if(mmap.count(key) == 0){
++size;
}
if(size > capacity){
LinkNode* destroy = tail -> prev;
tail -> prev = destroy -> prev;
destroy -> prev -> next = tail;
mmap.erase(destroy -> key);
delete destroy;
--size;
}
LinkNode* node = new LinkNode(key, value);
node -> next = head -> next;
head -> next -> prev = node;
head -> next = node;
node -> prev = head;
mmap[key] = node;
}
};
/**
* 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);
*/
0206解题思路
- 首先容易想到这应该是个双向链表
- 那么双向链表都该有哪些数据成员呢？ 至少指向下一个，前一个指针应该是有的，然后代表key，value的数值应该是有的
- 其次是LRU类，应该有哪些数据成员？
- 首先，size是需要的，（如果size超过最大容量的话，需要从末尾删除最冷的元素），
- capacity也是需要的，put的时候，需要判断是否size与之相等，达到最大元素，
- 双向链表的head， tail也是需要的，
- 承载数据的哈希结构也是需要的，这里用 unordered_map<key, LinkNode*>
- 构造函数应该怎么初始化？
- 初始化capacity
- new节点，将head，tail相互指向（即head -> next = tail, tail -> next = head） // 这样用指针就互相指向了
- get
- mmap进行查找，如果能够找到，用at方法定位到具体位置，需要把找到的元素进行移动到最前面 head 指针指向的位置
- 移动需要两点，需要先断开指针，然后移动到最前面
- 如果没有找到，返回-1即可
- put
- 关键是要将key，value插入
- 插入分两种情况，存在和不存在，如果存在，那么get(key)方法已经将元素移动到最前面了， 这时候进行更新就可
- 如果不存在，那么需要重新插入一个节点。在插入之前，需要进行判断，size与capacity的大小，如果当前size大于capacity，则还需要进行删除操作，淘汰末尾节点，也是断开指针，然后delete元素，需要将mmap按照key进行删除，即mmap.erase(key)
- 下面就开始重新插入一个节点了
- 插入完节点后，别忘了在mmap哈希表中进行赋值操作。 mmap[key] = node // node 为新生成的节点
