思路:
通过哈希表迅速找到映射关系。
通过双向链表和头、尾指针迅速定位第一个节点和最后一个节点,之所以用链表是为了确定当空间满后应当删除哪个值。链表的顺序代表了内存中数据的使用情况(越往后就说明越久没有被使用)
核心逻辑:
查的时候,先通过hash表找有没有,有的话直接取值,并把对应节点移动至链表头部,没有的话新建节点,放入链表头部
插入数据,先通过hash表找有没有,有的话更新并移向头部,没有的话再判断容量满没满,满了就删除最后一个节点(同时也删除hash表中的映射,所以需要节点中保存key),然后再往头部插入节点并建立hash表映射。
待纠错
一直出错的原因是当链表达到最大长度删除最后一个节点的时候忘记连tail的pre指针了。。。
class LRUCache {
private:
struct Node{
int key;
int val;
Node *pre;
Node *next;
Node(int x,int y) :key(x),val(y), pre(nullptr), next(nullptr){};
};
Node *head, *tail;
map<int, Node *> rec;
int count, size;
void moveToHead(Node *&node){
Node *pre = node->pre, *next = node->next;
pre->next = next;
next->pre = pre;
next = head->next;
node->next = next;
next->pre = node;
head->next = node;
node->pre = head;
}
public:
LRUCache(int capacity) {
size = capacity;
count = 0;
head = new Node(0,0);
tail = new Node(0,0);
head->next = tail;
tail->pre = head;
};
int get(int key) {
if (rec.find(key) == rec.end())
return -1;
else{
Node *node = rec[key];//get the val
//move the node to head
moveToHead(node);
return node->val;
}
};
void put(int key, int value) {
if (rec.find(key) != rec.end()){
Node *node = rec[key];
moveToHead(node);
node->val = value;
return;
}
else{
if (count == size){
Node *cur = tail->pre, *pre = cur->pre;
rec.erase(cur->key);
pre->next = tail;
tail->pre=pre;//之前出错就是因为漏了这个。。。
delete cur;
count--;
}
Node *node = new Node(key,value),*next=head->next;
head->next = node;
node->pre = head;
next->pre = node;
node->next = next;
rec.insert(make_pair(key, node));
count++;
}
};
};
网友评论