Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put. get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. Follow up: Could you do both operations in O(1) time complexity? Example: LRUCache cache = new LRUCache( 2 /* capacity */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // returns 1 cache.put(3, 3); // evicts key 2 cache.get(2); // returns -1 (not found) cache.put(4, 4); // evicts key 1 cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4
键值对想到hashmap, 增删节点考虑链表, + 头尾节点, 因此要构造相应的类
双向链表需要头尾节点
The problem can be solved with a hashtable that keeps track of the keys and its values in the double linked list. One interesting property about double linked list is that the node can remove itself without other reference. In addition, it takes constant time to add and remove nodes from the head or tail.
One particularity about the double linked list that I implemented is that I create a pseudo head and tail to mark the boundary, so that we don't need to check the NULL node during the update. This makes the code more concise and clean, and also it is good for the performance as well.
public class LRUCache {
private class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.pre = null;
this.next = null;
}
}
private int capacity;
private Node head = new Node(-1, -1);
private Node tail = new Node(-1, -1);
HashMap<Integer, Node> map = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node cur = map.get(key);
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
moveToTail(cur);
return cur.value;
}
public void put(int key, int value) {
if (get(key) != -1) {
map.get(key).value = value;
return;
}
Node cur = new Node(key, value);
if (map.size() == capacity) {
map.remove(head.next.key);
head.next.next.pre = head;
head.next = head.next.next;
}
map.put(key, cur);
moveToTail(cur);
}
private void moveToTail(Node cur) {
tail.pre.next = cur;
cur.pre = tail.pre;
tail.pre = cur;
cur.next = tail;
}
}
/**
* 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);
*/
public LinkedHashMap(int initialCapacity,
float loadFactor,
boolean accessOrder)
Constructs an empty LinkedHashMap instance with the specified initial capacity, load factor and ordering mode.
- Parameters:
initialCapacity- the initial capacityloadFactor- the load factoraccessOrder- the ordering mode - true for access-order, false for insertion-order
public class LRUCache {
private LinkedHashMap<Integer, Integer> map;
private final int CAPACITY;
public LRUCache(int capacity) {
CAPACITY = capacity;
map = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true){
protected boolean removeEldestEntry(Map.Entry eldest) {
return size() > CAPACITY;
}
};
}
public int get(int key) {
return map.getOrDefault(key, -1);
}
public void set(int key, int value) {
map.put(key, value);
}
}
map.get(key).value = value;
Wish : 第二轮电面， 中国大哥，LRU。 不让用dummy head tail。 处理corner case写出了bug
public class LRUCache {
private class Node{
int key;
int value;
Node pre;
Node next;
public Node(int key, int value) {
this.key = key;
this.value = value;
this.pre = null;
this.next = null;
}
}
private int capacity;
private Node head = null;
private Node tail = null;
HashMap<Integer, Node> map = new HashMap<>();
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
Node cur = map.get(key);
if (cur.key == head.key) {
if (map.size() != 1) {
head = head.next;
head.pre = null;
moveToTail(cur);
}
} else {
if (cur.key != tail.key) {
cur.pre.next = cur.next;
cur.next.pre = cur.pre;
moveToTail(cur);
}
}
return cur.value;
}
public void put(int key, int value) {
if (get(key) != -1) {
map.get(key).value = value;
return;
}
Node cur = new Node(key, value);
if (map.size() == capacity) {
map.remove(head.key);
if (map.size() == 0) {
head = null;
tail = null;
} else {
head = head.next;
head.pre = null;
}
}
if (head == null) {
head = cur;
tail = cur;
} else {
moveToTail(cur);
}
map.put(key, cur);
}
private void moveToTail(Node cur) {
tail.next = cur;
cur.pre = tail;
tail = cur;
}
}
/**
* 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);
*/