链表篇
灵神题解
class LRUCache {
private static class Node{
int key,value;
Node prev,next;
Node (int k,int v){
key=k;
value=v;
}
}
private final int capacity;
//哨兵节点
private final Node dummy=new Node(0,0);
private final Map<Integer,Node> keyToNode =new HashMap<>();
public LRUCache(int capacity) {
this.capacity=capacity;
dummy.prev=dummy;
dummy.next=dummy;
}
public int get(int key) {
Node node=getNode(key);
return node!=null?node.value:-1;
}
public void put(int key, int value) {
Node node=getNode(key);
//有书则更新
if(node!=null){
node.value=value;
return;
}
node=new Node(key,value);
keyToNode.put(key,node);
//放在最上面
pushFront(node);
//书太多了
if(keyToNode.size()>capacity){
Node backNode=dummy.prev;
keyToNode.remove(backNode.key);
//去掉最后一本书
remove(backNode);
}
}
//取节点
private Node getNode(int key){
//没有这本书
if(!keyToNode.containsKey(key)){
return null;
}
//有这本书
Node node=keyToNode.get(key);
//抽出来
remove(node);
//放在最上面
pushFront(node);
return node;
}
//删除一个节点(抽出一本书)
private void remove(Node x){
x.prev.next=x.next;
x.next.prev=x.prev;
}
//链表头添加节点
private void pushFront(Node x){
x.prev=dummy;
x.next=dummy.next;
x.prev.next=x;
x.next.prev=x;
}
}
/**
* 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);
*/
背题
标签:Node,node,java,int,next,hot100,key,LRU,prev From: https://blog.csdn.net/m0_73629042/article/details/142851855