--- # System prepended metadata title: '[146. LRU Cache](https://leetcode.com/problems/lru-cache/)' tags: [leetcode] --- --- tags: leetcode --- # [146. LRU Cache](https://leetcode.com/problems/lru-cache/) --- # My Solution ## The Key Idea for Solving This Coding Question 用雙向環狀鏈結串列 (Circular Doubly Linked List) 串聯所有的 key-value pair。並將最近用到的 key-value pair 放在雙向環狀鏈結串列的串列首。 最近用到的 key-value pair 大致列舉如下: * 用 `get` 調用的 key-value pair * 新增的 key-value pair * 被更新 value 的 key 在這個問題中用雙向環狀鏈結串列可以自然地把 Least Recently Used (LRU) 放到雙向環狀鏈結串列的末端。 再搭配 `unordered_map` 可以用 key 以 $O(1)$ 的時間複雜度找到雙向環狀鏈結串列中相對應的節點。 ## C++ Code 1 ```cpp= struct Node { int key; int val; Node *prev; Node *next; Node() :key(0), val(0), prev(nullptr), next(nullptr) {} Node(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr) {} }; class LRUCache { public: LRUCache(int capacity) : capacity(capacity), size(0) { head = new Node(); head->next = head; head->prev = head; } int get(int key) { auto iter = keyToNode.find(key); if (iter == keyToNode.end()) { // key doesn't exixt. return -1; } // key exists. Node *node = iter->second; remove(node); addAtHead(node); return node->val; } void put(int key, int value) { auto iter = keyToNode.find(key); if (iter == keyToNode.end()) { // key doesn't exist. if (size < capacity) { // LRU cache is not full. Node *newNode = new Node(key, value); keyToNode[key] = newNode; addAtHead(newNode); ++size; return; } // LRU cache is full. Node *lru = head->prev; remove(lru); keyToNode.erase(keyToNode.find(lru->key)); delete lru; Node *newNode = new Node(key, value); keyToNode[key] = newNode; addAtHead(newNode); return; } // key exists. Node *node = iter->second; remove(node); node->val = value; addAtHead(node); } private: int capacity; int size; Node *head; unordered_map keyToNode; void remove(Node *node) { node->prev->next = node->next; node->next->prev = node->prev; node->next = node; node->prev = node; } void addAtHead(Node *node) { node->prev = head; node->next = head->next; head->next->prev = node; head->next = 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); */ ``` ## C++ Code 2 ```cpp= struct Node { int key; int val; Node *prev; Node *next; Node() : key(-1), val(-1), prev(nullptr), next(nullptr) {} Node(int key, int val) : key(key), val(val), prev(nullptr), next(nullptr) {} }; class LRUCache { public: LRUCache(int capacity) { cap = capacity; len = 0; head = new Node(); head->next = head; head->prev = head; } int get(int key) { auto iter = keyToNode.find(key); if (iter == keyToNode.end()) { // key doesn't exist. return -1; } // key exists. Node *node = iter->second; removeNode(node); addAtHead(node); return node->val; } void put(int key, int value) { auto iter = keyToNode.find(key); if (iter == keyToNode.end()) { // key doesn't exist. if (len < cap) { Node *newNode = new Node(key, value); addAtHead(newNode); return; } // len >= cap is true. Node *node = head->prev; removeNode(node); node->key = key; node->val = value; addAtHead(node); return; } // key exists. Node *node = iter->second; removeNode(node); node->val = value; addAtHead(node); return; } private: int cap; int len; Node *head; unordered_map keyToNode; void removeNode(Node *node) { node->prev->next = node->next; node->next->prev = node->prev; node->next = node; node->prev = node; keyToNode.erase(node->key); --len; } void addAtHead(Node *node) { node->next = head->next; node->prev = head; head->next->prev = node; head->next = node; keyToNode[node->key] = node; ++len; } }; /** * 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); */ ``` ## Time Complexity * `LRUCache` $O(1)$ * `get` $O(1)$ * `put` $O(1)$ ## Space Complexity * `LRUCache` $O(1)$ * `get` $O(1)$ * `put` $O(1)$ # Miscellaneous