题目链接

讲解视频
Tips：

代码：

import java.util.*; // 修改导入语句，正确引入 java.util 包class Node{//双链表int key,value;Node pre,next;public Node(int k,int v){this.key = k;this.value = v;this.pre = null;this.next = null;}
}class LRUCache{int capacity;Map<Integer,Node> mp;Node head,tail;//dummy nodepublic LRUCache(int capacity){//实例化this.capacity = capacity;mp = new HashMap<>();head = new Node(-1, -1); // 修改头结点的初始化，给定默认值tail = new Node(-1, -1); // 修改尾结点的初始化，给定默认值head.next = tail;tail.pre = head;}public void add(Node node){node.pre = head;node.next = head.next;head.next.pre = node;head.next = node;}public void remove(Node node){node.pre.next = node.next;node.next.pre = node.pre;}public void update(Node node){//访问后将此节点从当前位置删除并添加到表头remove(node);add(node);}public int get(int key){if(!mp.containsKey(key)){//未在哈希表中存在过return -1;}Node node = mp.get(key);//取出键为key对应的节点update(node);//更新节点return node.value;//并返回节点对应的值}public void put(int key,int val){if(!mp.containsKey(key)){Node node = new Node(key,val);//未出现过的新增节点并分别在双链表和哈希表新增mp.put(key,node);//哈希表新增add(node);//双链表新增if(mp.size()>capacity){//超出最大cache容量Node toDel = tail.pre;remove(toDel);//在双链表删除mp.remove(toDel.key);//在哈希表删除}}else{Node node = mp.get(key); // 修改变量名，避免和方法参数名重复node.value = val;update(node);}}
}