题目
链接
题解
import java.util.HashMap;
import java.util.Map;
class LRUCache {
// 缓存哈希表
private Map<Integer, Node> cache;
// 最大容量
private int max;
// 当前容量
private int cap;
// 缓存头指针
private Node head;
// 缓存尾指针
private Node tail;
// 缓存节点
private static class Node {
public int key;
public int value;
public Node next;
public Node prev;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public Node(int key, int value, Node prev, Node next) {
this.key = key;
this.value = value;
this.prev = prev;
this.next = next;
}
public Node() {}
}
public LRUCache(int capacity) {
cache = new HashMap<>(capacity);
this.max = capacity;
this.cap = 0;
head = new Node();
tail = head;
}
public int get(int key) {
Node node = cache.get(key);
if (node == null) {
return -1;
}
// 用到一次移动到头指针next
trafficToHeadNext(node);
return node.value;
}
public void put(int key, int value) {
Node node = cache.get(key);
// 覆盖
if (node != null) {
node.value = value;
// 用到一次移动到头指针next
trafficToHeadNext(node);
return;
}
// 新增
else {
// 新增节点插入头节点next
node = new Node(key, value, head, head.next);
cache.put(key, node);
head.next = node;
if (node.next != null) {
node.next.prev = node;
}
if (tail == head) {
tail = node;
}
// 容量溢出
if (cap + 1 > max) {
// 移除尾节点
tail.prev.next = null;
cache.remove(tail.key);
tail = tail.prev;
} else {
cap++;
}
}
}
/**
* 将节点移动到head的next处
*/
private void trafficToHeadNext(Node node) {
if (head.next == node) {
return;
}
// 尾指针变更
if (node == tail) {
tail = node.prev;
}
// 摘除当前节点
Node prev = node.prev;
Node next = node.next;
prev.next = next;
if (next != null) {
next.prev = prev;
}
// 当前节点移动到头节点next
node.next = head.next;
if (node.next != null) {
node.next.prev = node;
}
head.next = node;
}
}
/**
* 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);
*/