146. LRU Cache
Last updated
Last updated
/**
* Time complexity : O(1) both for put and get since all operations with
* ordered dictionary. get/in/set/move_to_end/popitem
* (get/containsKey/put/remove) are done in a constant time.
* Space complexity : O(capacity) since the space is used only for an
* ordered dictionary with at most capacity + 1 elements.
*/
class LRUCache extends LinkedHashMap<Integer, Integer> {
private int capacity;
public LRUCache(int capacity) {
super(capacity, 0.75F, true);
this.capacity = capacity;
}
public int get(int key) {
return super.getOrDefault(key, -1);
}
public void put(int key, int value) {
super.put(key, value);
}
@Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
return size() > capacity;
}
}
/**
* 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 :
* Space complexity :
*/
class LRUCache {
class Node {
int key;
int value;
Node prev;
Node next;
Node(int key, int value) {
this.key = key;
this.value = value;
}
}
private int capacity;
private Node head;
private Node tail;
private Map<Integer, Node> cache;
public LRUCache(int capacity) {
this.capacity = capacity;
this.cache = new HashMap();
}
public int get(int key) {
Node node = cache.get(key);
if(node == null) return -1;
removeNode(node);
offerNode(node);
return node.value;
}
public void put(int key, int value) {
if(cache.containsKey(key)) {
Node node = cache.get(key);
node.value = value;
removeNode(node);
offerNode(node);
} else {
if(cache.size() >= capacity) {
cache.remove(head.key);
removeNode(head);
}
Node node = new Node(key, value);
offerNode(node);
cache.put(key, node);
}
}
private void offerNode(Node node) {
if(tail != null) {
tail.next = node;
}
node.next = null;
node.prev = tail;
tail = node;
if(head == null) {
head = tail;
}
}
private void removeNode(Node node) {
if(node.prev != null) {
node.prev.next = node.next;
} else {
head = node.next;
}
if(node.next != null) {
node.next.prev = node.prev;
} else {
tail = node.prev;
}
}
}
/**
* 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);
*/