難度: Medium
類型: Array,Matrix,Linked List,Doubly-Linked List
CPP程式下載: 146.cpp
Topic:
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity)Initialize the LRU cache with positive sizecapacity.int get(int key)Return the value of thekeyif the key exists, otherwise return-1.void put(int key, int value)Update the value of thekeyif thekeyexists. Otherwise, add thekey-valuepair to the cache. If the number of keys exceeds thecapacityfrom this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
Example 1:
Input ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] Output [null, null, null, 1, null, -1, null, -1, 3, 4] Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 30000 <= key <= 1040 <= value <= 105- At most
2 * 105calls will be made togetandput.
Consideration:
1. A unsorted_map to store key and double linked list's "Node*".
2. A Node structure to store key, value integers and prev, next pointers.
3. During the implementation, I finally know that Node has to store key. When we try to remove the LRU memory map, we can't get the key from the Double Linked List Node.
4. Add the latest used key, value to the head.
5. Remove the lastest used key, value from the tail.
6. When there is existed key get or value set, remove the current node and add to the tail.
Code:
class LRUCache {
private:
int cap;
struct Node {
int key;
int value;
Node* prev;
Node* next;
Node(int k, int v) : key(k), value(v), prev(nullptr), next(nullptr) {}
};
Node* head; // Dummy head
Node* tail; // Dummy tail
unordered_map<int, Node*> lru_map;
// Helper: Remove a node from the linked list
void remove(Node* node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
// Helper: Add a node right after the dummy head (Most Recently Used)
void add(Node* node) {
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
}
public:
LRUCache(int capacity) {
cap = capacity;
head = new Node(-1, -1);
tail = new Node(-1, -1);
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (lru_map.find(key) == lru_map.end()) {
return -1;
}
Node* node = lru_map[key];
remove(node);
add(node);
return node->value;
}
void put(int key, int value) {
if (lru_map.find(key) != lru_map.end()) {
Node* node = lru_map[key];
remove(node);
node->value = value;
add(node);
return;
}
Node* newNode = new Node(key, value);
lru_map[key] = newNode;
add(newNode);
if (lru_map.size() > cap) {
Node* lru_node = tail->prev;
remove(lru_node);
lru_map.erase(lru_node->key);
delete lru_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);
*/
Result:
https://leetcode.com/problems/lru-cache/submissions/1940361643/
Runtime
70msBeats69.18%
Memory
173.14MBBeats68.45%
