leetcode146 LRU 缓存机制

思路：

双向链表+哈希表。

实现：

 1 class node
 2 {
 3 public:
 4     int key, val;
 5     node* prev, *next;
 6     node(int k, int v): key(k), val(v) { prev = NULL; next = NULL; }
 7 };
 8 class LRUCache
 9 {
10     int _capacity = 0;
11     unordered_map<int, node*> mp;
12     node* dummy_head = NULL, *dummy_tail = NULL;
13     int cnt = 0;
14 public:
15     LRUCache(int capacity): _capacity(capacity)
16     {
17         dummy_head = new node(-1, -1);
18         dummy_head->next = new node(-1, -1);
19         dummy_tail = dummy_head->next;
20         dummy_tail->prev = dummy_head;
21     }
22             
23     void move_back(node* tmp)
24     {
25         node* p = tmp->prev, *n = tmp->next;
26         p->next = tmp->next; n->prev = tmp->prev;
27         node* fuck = dummy_tail->prev;
28         fuck->next = tmp;
29         tmp->prev = fuck;
30         dummy_tail->prev = tmp;
31         tmp->next = dummy_tail;
32     }
33 
34     void erase()
35     {
36         node* tmp = dummy_head->next, *n = tmp->next;
37         dummy_head->next = n;
38         n->prev = dummy_head;
39         tmp->next = tmp->prev = NULL;
40         mp.erase(tmp->key);
41         delete(tmp); tmp = NULL;
42     }
43 
44     int get(int key)
45     {
46         if (mp.count(key))
47         {
48             node* tmp = mp[key];
49             move_back(tmp);
50             return mp[key]->val;
51         }
52         return -1;
53     }
54                         
55     void put(int key, int value)
56     {
57         if (mp.count(key))
58         {
59             node* tmp = mp[key];
60             tmp->val = value;
61             move_back(tmp);
62         }
63         else
64         {
65             if (cnt == _capacity) { erase(); cnt--; }
66             node* p = dummy_tail->prev;
67             node* tmp = new node(key, value);
68             p->next = tmp; tmp->next = dummy_tail;
69             dummy_tail->prev = tmp; tmp->prev = p;
70             mp[key] = tmp;
71             cnt++;
72         }
73     }
74 };
75 
76 /**
77  * Your LRUCache object will be instantiated and called as such:
78  * LRUCache* obj = new LRUCache(capacity);
79  * int param_1 = obj->get(key);
80  * obj->put(key,value);
81  */