Grind 75 - Leetcode146 LRU缓存

Leetcode146 LRU缓存

经典题，典型compund data structure思想
link
思绪：

• 主要思想就是hash table + double-linked list
  
• 重点就是手动实现这些功能
  
• 因为get和put都要求                                        O                            (                            1                            )                                  O(1)                     O(1)时间内实现，所以就是要用hash table
  
• 而要实现LRU，所以用双向链表维护近来使用
  

   ps: code 多打几遍就认识了

1. class Node {
2. public:
3.     int key;
4.     int value;
5.     Node *last, *next;
6.     Node(int k = 0, int val = 0) : key(k), value(val), last(nullptr), next(nullptr) {}
7. };
9. class LRUCache {
10. private:
11.     unordered_map<int, Node*> cache;
12.     int size;
13.     int capacity;
14.     Node *head;
15.     Node *tail;
17.     void addNode(Node *node) {
18.         node->next = head->next;
19.         head->next->last = node;
20.         node->last = head;
21.         head->next = node;
22.     }
24.     void deleteNode(Node *node) {
25.         node->last->next = node->next;
26.         node->next->last = node->last;
27.     }
29.     void move(Node *node) {
30.         deleteNode(node);
31.         addNode(node);
32.     }
34.     Node *deleteTail() {
35.         Node *node = tail->last;
36.         deleteNode(node);
37.         return node;
38.     }
40. public:
41.     LRUCache(int capacity) : capacity(capacity), size(0) {
42.         head = new Node();
43.         tail = new Node();
44.         head->next = tail;
45.         tail->last = head;
46.     }
47.    
48.     int get(int key) {
49.         if (cache.count(key) == 0)
50.             return -1;
51.         Node *node = cache[key];
52.         move(node);
53.         return node->value;
54.     }
55.    
56.     void put(int key, int value) {
57.         if (cache.count(key) > 0) {
58.             Node *node = cache[key];
59.             node->value = value;
60.             move(node);
61.         }
62.         else {
63.             Node *node = new Node(key, value);
64.             cache[key] = node;
65.             addNode(node);
66.             ++size;
67.             if (size > capacity) {
68.                 Node *lastUsed = deleteTail();
69.                 cache.erase(lastUsed->key);
70.                 --size;
71.                 delete lastUsed;
72.             }
73.         }
74.     }
75. };

复制代码

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