Algorithm
Problem Name: 146. 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.
Code Examples
#1 Code Example with C Programming
Code -
C Programming
struct kvlist {
int key;
int val;
struct kvlist *prev;
struct kvlist *next;
struct kvlist *shadow;
};
typedef struct {
int kf;
int sz;
int idx;
struct kvlist **kp;
struct kvlist *buff;
struct kvlist *head;
struct kvlist *tail;
} LRUCache;
LRUCache* lRUCacheCreate(int capacity) {
LRUCache *obj;
int i;
obj = calloc(1, sizeof(LRUCache));
//assert(obj);
obj->kf = 1024 * 10;
obj->kp = calloc(obj->kf, sizeof(struct kvlist *));
obj->sz = capacity;
obj->buff = calloc(obj->sz, sizeof(struct kvlist));
obj->idx = 0;
obj->head = &obj->buff[0];
obj->tail = &obj->buff[obj->sz - 1];
obj->head->prev = obj->tail;
obj->tail->next = obj->head;
if (obj->sz > 1) {
obj->head->next = &obj->buff[1];
obj->tail->prev = &obj->buff[obj->sz - 2];
}
for (i = 1; i < obj->sz - 1; i ++) {
obj->buff[i].prev = &obj->buff[i - 1];
obj->buff[i].next = &obj->buff[i + 1];
}
return obj;
}
struct kvlist *lookup(LRUCache *obj, int key) {
struct kvlist *l;
l = obj->kp[key % obj->kf];
while (l && l->key != key) {
l = l->shadow;
}
return l;
}
void move2tail(LRUCache *obj, struct kvlist *l) {
if (l == obj->tail) return;
if (l == obj->head) {
obj->head = l->next;
obj->tail = l;
return;
}
// take it out of the loop
l->prev->next = l->next;
l->next->prev = l->prev;
// link to the tail
l->next = obj->head;
l->prev = obj->tail;
obj->head->prev = l;
obj->tail->next = l;
obj->tail = l;
}
int lRUCacheGet(LRUCache* obj, int key) {
int val;
struct kvlist *l;
l = lookup(obj, key);
if (!l) return -1;
val = l->val;
move2tail(obj, l);
return val;
}
void lRUCachePut(LRUCache* obj, int key, int value) {
int i;
struct kvlist *l, **pp;
l = lookup(obj, key);
if (!l) {
l = obj->head;
// remove it from hash table
i = l->key % obj->kf;
pp = &obj->kp[i];
while (*pp && *pp != l) {
pp = &(*pp)->shadow;
}
*pp = l->shadow;
// insert it to hash table with new key
l->key = key;
i = key % obj->kf;
l->shadow = obj->kp[i];
obj->kp[i] = l;
}
l->val = value;
move2tail(obj, l);
}
void lRUCacheFree(LRUCache* obj) {
free(obj->kp);
free(obj->buff);
}
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]
#2 Code Example with C++ Programming
Code -
C++ Programming
class LRUCache {
public:
LRUCache(int capacity) {
this->capacity = capacity;
}
int get(int key) {
if(!m.count(key) || m[key] == -1) return -1;
q.push_back(key);
visited[key]++;
return m[key];
}
void put(int key, int value) {
if(!m.count(key)|| m[key] == -1) count++;
else visited[key]++;
if(count > capacity){
while(visited[q.front()]) visited[q.front()]--, q.pop_front();
m[q.front()] = -1;
q.pop_front();
count--;
}
q.push_back(key);
m[key] = value;
}
private:
unordered_map < int, int>m;
unordered_map<int, int>visited;
deque < int>q;
int count = 0;
int capacity = 0;
};
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]
#3 Code Example with Java Programming
Code -
Java Programming
class LRUCache {
private final Map map;
private final Node head;
private final Node tail;
private int capacity;
public LRUCache(int capacity) {
this.map = new HashMap < >();
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
this.capacity = capacity;
}
public int get(int key) {
if (!this.map.containsKey(key)) {
return -1;
}
Node node = this.map.get(key);
removeNode(node);
addNode(node);
return this.map.get(key).val;
}
public void put(int key, int value) {
if (!map.containsKey(key)) {
if (capacity == 0) {
removeNode(tail.prev);
}
} else {
removeNode(this.map.get(key));
}
addNode(new Node(key, value));
}
private void addNode(Node node) {
Node nextToHead = head.next;
head.next = node;
node.next = nextToHead;
nextToHead.prev = node;
node.prev = head;
this.map.put(node.key, node);
this.capacity--;
}
private void removeNode(Node node) {
Node nextNode = node.next;
node.prev.next = nextNode;
nextNode.prev = node.prev;
this.map.remove(node.key);
this.capacity++;
}
private static class Node {
Node next;
Node prev;
int key;
int val;
public Node(int key, int val) {
this.key = key;
this.val = val;
this.next = null;
this.prev = null;
}
}
}
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]
#4 Code Example with Javascript Programming
Code -
Javascript Programming
class Node {
constructor(key, val) {
this.val = val;
this.key = key;
this.next = this.pre = null;
}
}
const LRUCache = function(capacity) {
this.capacity = capacity;
this.count = 0;
this.start = new Node(-1, -1);
this.end = new Node(-1, -1);
this.start.next = this.end;
this.end.pre = this.start;
this.map = {};
};
// insert node into the next of the start
const insertAfter = function(start, node) {
let next = start.next;
start.next = node;
node.pre = start;
node.next = next;
next.pre = node;
};
const detach = function(node) {
let pre = node.pre,
next = node.next;
pre.next = next;
next.pre = pre;
node.next = node.pre = null;
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
let node = this.map[key];
if (node != undefined) {
detach(node);
insertAfter(this.start, node);
return node.val;
} else {
return -1;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
let node = this.map[key];
if (!node) {
if (this.count == this.capacity) {
// deleting last nodes
let t = this.end.pre;
detach(t);
delete this.map[t.key];
} else {
this.count++;
}
node = new Node(key, value);
this.map[key] = node;
insertAfter(this.start, node);
} else {
node.val = value;
detach(node);
insertAfter(this.start, node);
}
};
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]
#5 Code Example with Python Programming
Code -
Python Programming
class Node:
def __init__(self, key, value):
self.key = key
self.val = value
self.next = self.pre = None
self.pre = None
class LRUCache:
def remove(self, node):
node.pre.next, node.next.pre = node.next, node.pre
self.dic.pop(node.key)
def add(self, node):
node.pre = self.tail.pre
node.next = self.tail
self.tail.pre.next = self.tail.pre = node
self.dic[node.key] = node
def __init__(self, capacity):
self.dic = {}
self.n = capacity
self.head = self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.pre = self.head
def get(self, key):
if key in self.dic:
node = self.dic[key]
self.remove(node)
self.add(node)
return node.val
return -1
def put(self, key, value):
if key in self.dic:
self.remove(self.dic[key])
node = Node(key, value)
self.add(node)
if len(self.dic) > self.n:
self.remove(self.head.next)
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]
#6 Code Example with C# Programming
Code -
C# Programming
using System.Collections.Generic;
namespace LeetCode
{
public class _0146_LRUCache
{
private readonly int capacity;
private readonly IDictionary < int, DoubleLinkNode> hashMap;
private readonly DoubleLinkNode dummyHead;
private readonly DoubleLinkNode dummyTail;
private int size;
public _0146_LRUCache(int capacity)
{
this.size = 0;
this.capacity = capacity;
this.hashMap = new Dictionary < int, DoubleLinkNode>();
this.dummyHead = new DoubleLinkNode();
this.dummyTail = new DoubleLinkNode();
dummyHead.Next = dummyTail;
dummyTail.Prev = dummyHead;
}
public int Get(int key)
{
if (!hashMap.ContainsKey(key)) return -1;
var node = hashMap[key];
MoveNodeToHead(node);
return node.Value;
}
public void Put(int key, int value)
{
if (hashMap.ContainsKey(key))
{
var node = hashMap[key];
node.Value = value;
MoveNodeToHead(node);
return;
}
var newNode = new DoubleLinkNode()
{
Key = key,
Value = value
};
hashMap.Add(key, newNode);
AddNodeToHead(newNode);
size++;
if (size > capacity)
{
var node = RemoveLatestNode();
hashMap.Remove(node.Key);
size--;
}
}
private void MoveNodeToHead(DoubleLinkNode node)
{
RemoveNode(node);
AddNodeToHead(node);
}
private void RemoveNode(DoubleLinkNode node)
{
var previous = node.Prev;
var next = node.Next;
previous.Next = next;
next.Prev = previous;
}
private void AddNodeToHead(DoubleLinkNode node)
{
var next = dummyHead.Next;
node.Next = next;
next.Prev = node;
dummyHead.Next = node;
node.Prev = dummyHead;
}
private DoubleLinkNode RemoveLatestNode()
{
var last = dummyTail.Prev;
RemoveNode(last);
return last;
}
public class DoubleLinkNode
{
public int Key { get; set; }
public int Value { get; set; }
public DoubleLinkNode Prev { get; set; }
public DoubleLinkNode Next { get; set; }
}
}
}
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]