1, the title
Design and implement a data structure that satisfies the LRU (least recently used) cache constraints. Implement the LRUCache class:
Capacity Initializes the LRU cache int GET (int key) Returns the value of the key if the key exists in the cache; otherwise -1 is returned. Void put(int key, int value) If the key already exists, change its value. If not, the group key-value is inserted into the cache. If the number of keywords exceeds capacity due to an insert operation, you need to export the unused keywords.Copy the codeThe functions get and PUT must run at the average time complexity of O(1)O(1)O(1).
Example:
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] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the codeTip:
1 <= capacity <= 30000 <= key <= 100000 <= value <= 105- Most call
2 * 10 ^ 5次get和put
2, train of thought
(doubly linked list + hash)O(1)O(1) O(1)
Use a double linked list and a hash table:
- A double-linked list stores a node’s get or PUT timestamp, sorted by the most recent use from left to right. The node that was first used is placed first in the double-linked list, so the last digit of the double-linked list is the node that has not been used for the longest time.
- Hash table storage
keyAddresses of nodes in the corresponding linked list, used forkey-valueAdd, delete, change and check;
Initialization:
nIs the cache size;- Double-linked and hash lists are empty;
Get (key) :
First use hash table to check whether key exists:
-
If key does not exist, -1 is returned;
-
If the key exists, the corresponding value is returned, and the node corresponding to the key is placed at the far left of the double-linked list.
Put (key, value) :
First use hash table to check whether key exists:
- if
keyIf yes, modify the correspondingvalueAnd at the same time willkeyThe corresponding node is placed at the far left of the double-linked list; - if
keyThere is no:- If the cache is full, delete the right-most node of the double-linked list (the oldest node last used) and update the hash table;
- Otherwise, insert
(key, value)At the same time willkeyThe corresponding node is placed at the far left of the double-linked list to update the hash table;
And time complexity analysis: double linked list hash table to add and delete operation time complexity is O (1) O (1) O (1), so the get and put operations of time complexity is O (1) O (1) O (1).
Several operations corresponding to the double-linked list
1. Delete node P
p->right->left = p->left;
p->left->right = p->right;
Copy the code2. Insert p node after L node
p->right = L->right;
p->left = L;
L->right->left = p;
L->right = p;
Copy the codeC++ code
class LRUCache {
public:
// Define a double-linked list
struct Node{
int key,value;
Node* left ,*right;
Node(int _key,int _value): key(_key),value(_value),left(NULL),right(NULL){}
}*L,*R;// The left-most and right-most nodes of a double-linked list do not store values.
int n;
unordered_map<int,Node*>hash;
void remove(Node* p)
{
p->right->left = p->left;
p->left->right = p->right;
}
void insert(Node *p)
{
p->right = L->right;
p->left = L;
L->right->left = p;
L->right = p;
}
LRUCache(int capacity) {
n = capacity;
L = new Node(- 1.- 1),R = new Node(- 1.- 1);
L->right = R;
R->left = L;
}
int get(int key) {
if(hash.count(key) == 0) return - 1; // The keyword key does not exist
auto p = hash[key];
remove(p);
insert(p);// Put the current node first in the double-linked list
return p->value;
}
void put(int key, int value) {
if(hash.count(key)) // If the key exists, change the corresponding value
{
auto p = hash[key];
p->value = value;
remove(p);
insert(p);
}
else
{
if(hash.size() == n) // If the cache is full, delete the right-most node of the double-linked list
{
auto p = R->left;
remove(p);
hash.erase(p->key); // Update the hash table
delete p; // Free memory
}
// Otherwise, insert (key, value)
auto p = new Node(key,value);
hash[key] = p;
insert(p); }}};/** * 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); * /
Copy the code
4. Java code
class LRUCache {
static Node head, tail;
static HashMap<Integer, Node> map = new HashMap<Integer,Node>();
static int n;
// Delete the current structure
static void remove(Node p)
{
p.right.left = p.left;
p.left.right = p.right;
}
// Add a structure to the team head
static void insert(Node p)
{
p.right = head.right;
p.right.left = p;
p.left = head;
head.right = p;
}
public LRUCache(int capacity) {
n = capacity;
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.right = tail;
tail.left = head;
map.clear();
}
public int get(int key) {
if(! map.containsKey(key))return -1;
Node p = map.get(key);
remove(p);
insert(p);
return p.val;
}
public void put(int key, int value) {
// If the hash table exists
if(map.containsKey(key))
{
Node p = map.get(key);
p.val = value;
remove(p);
insert(p);
}
// The hash table does not exist
else
{
if(map.size() == n)
{
Node p = tail.left;
remove(p);
map.remove(p.key);
}
Node t = newNode(key, value); insert(t); map.put(key, t); }}}class Node
{
int key, val;
Node left, right;
Node(int key, int val)
{
this.key = key;
this.val = val; }}/** * 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); * /
Copy the code