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?
題意：實(shí)現(xiàn)一個(gè)簡(jiǎn)單的LRU cache，僅需要支持get和put夯辖，能否用O(1)的時(shí)間復(fù)雜度實(shí)現(xiàn)链嘀。
思路：用一個(gè)雙端鏈表記錄所有節(jié)點(diǎn)衫樊，有操作的節(jié)點(diǎn)就移到鏈表尾部锻煌，那么最近最少使用的節(jié)點(diǎn)就位于鏈表頭部秉溉。通過(guò)哈希表來(lái)做key到鏈表節(jié)點(diǎn)的映射肴裙。
private int max;
private Map<Integer, DListNode> map = new HashMap<>();
private DListNode head = new DListNode(0, 0);
private DListNode tail = new DListNode(0, 0);
public EP_LRUCache(int capacity) {
max = capacity;
head.next = tail;
tail.pre = head;
}
public int get(int key) {
if (!map.containsKey(key)) {
return -1;
}
this.moveToTail(map.get(key));
return map.get(key).val;
}
public void put(int key, int value) {
if (!map.containsKey(key) && map.size() >= max) {
this.removeLeastUse();
}
if (map.containsKey(key)) {
this.moveToTail(map.get(key));
map.get(key).val = value;
} else {
DListNode newNode = new DListNode(key, value);
map.put(key, newNode);
DListNode pre = this.tail.pre;
newNode.next = this.tail;
this.tail.pre = newNode;
newNode.pre = pre;
pre.next = newNode;
}
}
private void removeLeastUse() {
if (this.map.size() <= 0) {
return;
}
DListNode lease = this.head.next;
this.head.next = lease.next;
lease.next.pre = this.head;
map.remove(lease.key);
}
private void moveToTail(DListNode node) {
node.pre.next = node.next;
node.next.pre = node.pre;
DListNode pre = this.tail.pre;
node.next = this.tail;
this.tail.pre = node;
node.pre = pre;
pre.next = node;
}