LeetCode 146. LRU缓存机制
原题链接
中等
作者:
郭松源
,
2024-02-18 21:24:48
,
所有人可见
,
阅读 34
class LRUCache {
private int capacity;
private Map<Integer, Node> key2Node;
private Node L, R;
public LRUCache(int capacity) {
this.capacity = capacity;
this.L = new Node();
this.R = new Node();
this.L.right = R;
this.R.left = L;
this.key2Node = new HashMap<>();
}
public int get(int key) {
if (!key2Node.containsKey(key)) {
return -1;
} else {
Node node = key2Node.get(key);
node.left.removeRight(key2Node);
R.left.insertRight(node, key2Node);
return node.val;
}
}
public void put(int key, int value) {
if (!key2Node.containsKey(key)) {
if (this.key2Node.size() + 1 > this.capacity) {
L.removeRight(key2Node);
}
Node node = new Node(key, value, null, null);
R.left.insertRight(node, key2Node);
} else {
Node node = key2Node.get(key);
node.val = value;
node.left.removeRight(key2Node);
R.left.insertRight(node, key2Node);
}
}
private class Node {
public int key;
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int key, int val, Node left, Node right) {
this.key = key;
this.val = val;
this.left = left;
this.right = right;
}
public void removeRight(Map<Integer, Node> key2Node) {
Node remNode = this.right;
key2Node.remove(remNode.key);
this.right = remNode.right;
remNode.right.left = this;
}
public void insertRight(Node node, Map<Integer, Node> key2Node) {
Node right = this.right;
right.left = node;
node.right = right;
node.left = this;
this.right = node;
key2Node.put(node.key, 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);
*/