链表：LRU缓存

LeetCode146 LRU缓存

1. class Node{
2. public:
3.     int key;
4.     int value;
5.     Node* pre;
6.     Node* next;
7.     Node(int k=0,int v=0):key(k),value(v){}
8. };
10. class LRUCache {
11. private:
12.     int capacity;
13.     Node* dummy; //哨兵节点
14.     unordered_map<int,Node*> key_node;
16.     //删除一个节点(抽出一本书)
17.     void remove(Node* x){
18.         x->next->pre=x->pre;
19.         x->pre->next=x->next;
20.     }
22.     //在链表头添加一个节点(把一本书放在最上面)
23.     void push_front(Node* x){
24.         x->pre=dummy;
25.         x->next=dummy->next;
26.         dummy->next=x;
27.         x->next->pre=x;   
28.     }
30.     //获取key对应的节点, 同时把节点移到链表头部
31.     Node* get_node(int key){
32.         auto it=key_node.find(key);
33.         if(it==key_node.end()){//没有这个关键值(这本书)
34.             return nullptr;
35.         }
36.         Node* node=it->second;
37.         remove(node); //将这本书抽出来
38.         push_front(node); //放在最上面
39.         return node;
40.     }
42. public:
43.     LRUCache(int capacity):capacity(capacity),dummy(new Node()) {
44.         dummy->next=dummy;
45.         dummy->pre=dummy;
46.     }
47.    
48.     int get(int key) { //如果关键字key存在于缓存中，则返回关键字的值，否则返回-1
49.         Node* node=get_node(key);
50.         if(node==nullptr) return -1;
51.         return node->value;
52.     }
53.    
54.     void put(int key, int value)
55.         Node* node=get_node(key);
56.         if(node!=nullptr){//关键字key已存在，变更其数据值value
57.             node->value=value;
58.             return;
59.         }
60.         else{ //如果不存在，则向缓存中插入该组 key-value。如果插入操作导致关键字数量超过 capacity ，则应该逐出最久未使用的关键字。
61.             Node* new_node=new Node(key,value); //新书
62.             key_node[key]=new_node;
63.             push_front(new_node); //放在最上面
64.             if(key_node.size()>capacity){ //书太多了
65.                 Node* back_node=dummy->pre; //找到最后一本书
66.                 key_node.erase(back_node->key);
67.                 remove(dummy->pre); //去掉最后一本书
68.                 delete back_node; //释放内存
69.             }
70.         }
71.     }
72. };
74. /**
75. * Your LRUCache object will be instantiated and called as such:
76. * LRUCache* obj = new LRUCache(capacity);
77. * int param_1 = obj->get(key);
78. * obj->put(key,value);
79. */

复制代码

时间复杂度：全部操作的时间复杂度均为O(1)
空间复杂度：O(min(p, capacity))，p为put的调用次数

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。