题目
解题
采用哈希表+双向链表的数据结构，双向链表创建虚拟头结点、虚拟尾结点，用来查询最近最少使用的元素，刚刚使用或添加的元素，放到虚拟头结点后面，淘汰掉虚拟尾结点的前一个元素
class LRUCache {
Map<Integer,Node> map;
int capacity;
// 虚拟头结点
Node first;
// 虚拟尾结点
Node last;
public LRUCache(int capacity) {
map = new HashMap<>(capacity);
// 容量
this.capacity = capacity;
first = new Node();
last = new Node();
first.next = last;
last.prev = first;
}
public void addFirstNode(Node node) {
node.next = first.next;
first.next.prev = node;
node.prev = first;
first.next = node;
}
public void removeNode(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
public int get(int key) {
Node node = map.get(key);
if (node == null) return -1;
removeNode(node);
addFirstNode(node);
return node.value;
}
public void put(int key, int value) {
Node node = map.get(key);
if (node != null) {
node.value = value;
removeNode(node);
addFirstNode(node);
} else {
if (map.size() == capacity) {
map.remove(last.prev.key);
removeNode(last.prev);
}
map.put(key, node = new Node(key,value));
addFirstNode(node);
}
}
public static class Node {
int key;
int value;
Node prev;
Node next;
public Node (int key, int value) {
this.key = key;
this.value = value;
}
public Node() {}
}
}
