146. LRU Cache
· 閱讀時間約 3 分鐘
Hint
struct Node {
// Constructor to initialize a node with key and value
};
class LRUCache {
private:
// Capacity of the cache
// Hash map to store key to node mappings
// Dummy head and tail nodes for the doubly linked list
// Helper function to remove a node from the doubly linked list
void remove()
{
}
// Helper function to add a node to the end (before the tail) of the doubly linked list
void add()
{
}
public:
// Constructor to initialize the LRU Cache with given capacity
LRUCache(int capacity)
{
}
// Destructor to clean up all nodes
~LRUCache()
{
}
// Function to get the value of a key
int get(int key)
{
// If key is not found, return -1
// Move the accessed node to the end (most recently used)
// Return the value associated with the key
}
// Function to put a key-value pair in the cache
void put(int key, int value)
{
// If key already exists, remove the existing node
// Create a new node for the key-value pair
// If the cache exceeds capacity, remove the least recently used (LRU) node
if ()
{
}
}
};
/**
* 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);
*/
struct Node {
int key;
int val;
Node* next;
Node* prev;
Node(int key, int val) : key(key), val(val), next(nullptr), prev(nullptr) {}
};
class LRUCache {
private:
int cap;
unordered_map<int, Node*> m;
Node* head = new Node(-1, -1);
Node* tail = new Node(-1, -1);
// head <-> 1 <-> 2 <-> 3 <-> tail
// ^ node
// ^ prev_node
// ^ next_node
void remove(Node* node)
{
Node* prev_node = node->prev;
Node* next_node = node->next;
prev_node->next = next_node;
next_node->prev = prev_node;
}
// head <-> 1 <-> 2 <-> tail
// ^ prev_node
// ^ next_node
void add(Node* node)
{
Node* prev_node = tail->prev;
Node* next_node = tail;
prev_node->next = node;
next_node->prev = node;
node->next = next_node;
node->prev = prev_node;
}
public:
LRUCache(int capacity)
{
cap = capacity;
// head <-> tail
head->next = tail;
tail->prev = head;
}
~LRUCache()
{
Node* cur = head;
while (cur) {
Node* next = cur->next;
delete cur;
cur = next;
}
}
int get(int key)
{
if(!m.count(key)) return -1;
Node* node_to_get = m[key];
remove(node_to_get);
add(node_to_get);
return node_to_get->val;
}
void put(int key, int value)
{
if(m.count(key)) remove(m[key]);
Node* node_to_put = new Node(key, value);
m[key] = node_to_put;
add(node_to_put);
if (m.size() > cap)
{
Node* node_to_delete = head->next;
remove(node_to_delete);
m.erase(node_to_delete->key);
delete node_to_delete;
}
}
};
/**
* 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);
*/
- T: $O(1)$
- S: $O(capacity)$
