力扣146 - LRU缓存

视频讲解

哈希 + 双向链表

为什么要用双向链表？

快速删除节点（O(1））

如果是单链表的话，删除一个节点时，需要从头遍历，找到前驱节点，才能修改 prev->next，导致 O(n) 的时间复杂度。

双向链表存储了两个指针，一个指针指向下一个节点，另一个指针指向上一个节点（前驱指针）。所以我们可以根据前驱指针快速找到上一个节点，然后移除掉当前节点。

demo：

class LRUCache {
public:struct Node{int key,val;Node *prev,*next;Node(int k,int v) : key(k) , val(v) , prev(nullptr) , next(nullptr){}};map<int,Node*>mp;Node *L,*R; //双哨兵int n; //LRU的总数//创建操作LRUCache(int capacity) {n = capacity;L = new Node(-1,-1);R = new Node(-1,-1);L->next = R;R->prev = L;}//获取值操作 (获得值的时候需要注意：如果有值存在哈希表中的话，那么就要将这个值放在最新的地方)//比如： L | 2 1 4 | R //我们查询1这个数，那么查完后需要变成： L | 2 4 1 | R int get(int key) {if(mp.count(key)){Node* node = mp[key];remove(node); //在链表中移除该节点 通过双向指针移除insert(node->key,node->val); // 在链表中插入该节点return node->val;}else{return -1;}}//插入操作void put(int key, int value) {if(mp.count(key)){Node* node = mp[key];remove(node);insert(key,value); //这里需要用给的key和value而不是node->key和node->val（因为可能插入的是新的值）}else{if(mp.size() == n){Node* node = L->next; //满了，需要移除的节点remove(node);insert(key,value);}else{insert(key,value);}}}//以下为自定义新增函数 remove是移除节点的函数 insert是插入节点的函数//同时在链表和哈希表中删除nodevoid remove(Node* node){Node* pre = node->prev;Node* nxt = node->next;pre->next = nxt;nxt->prev = pre;mp.erase(node->key);}//同样要同时操作链表和哈希表void insert(int key,int val){Node* node = new Node(key,val);Node* pre = R->prev;//这里是最后一个插入的数//向右pre->next = node;node->next = R;//向左node->prev = pre;R->prev = node;mp[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);*/