前言：
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity)以 正整数 作为容量capacity初始化 LRU 缓存int get(int key)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。void put(int key, int value)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该 逐出 最久未使用的关键字。- 函数
get和put必须以O(1)的平均时间复杂度运行。
关键设计说明
-
双向链表：维护访问顺序
-
头部节点 (head
.next)：最近使用的数据 -
尾部节点 (end.prev)：最久未使用的数据
-
节点移动/删除操作都是 O(1) 时间复杂度
-
-
哈希表：提供 O(1) 的键值查找
-
Map<Integer, DLinkedNode>映射键到链表节点 -
快速判断键是否存在并获取对应节点
-
-
哨兵节点：简化边界处理
-
头节点 (
head) 和尾节点 (end) 作为虚拟节点 -
避免空指针检查，使代码更简洁
-
-
操作流程：
-
get()：存在则移动节点到头部 -
put()：-
存在 → 更新值并移到头部
-
不存在 → 创建新节点并添加到头部
-
容量超限 → 移除尾部节点
-
-
复杂度分析
-
时间复杂度：
get()和put()均为 O(1)-
哈希表操作：O(1) 的查找/插入/删除
-
链表操作：O(1) 的节点添加/删除/移动
-
代码实现：
import java.util.HashMap;
import java.util.Map;
class LRUCache {//双向链表class DLinkedNode{int key;int value;DLinkedNode prev;DLinkedNode next;public DLinkedNode(){}public DLinkedNode(int key,int value){this.key = key;this.value = value;}}//LRU缓存的属性//容量private int capacity = 0;//实际个数private int size = 0;//map装的key，node节点private final Map<Integer,DLinkedNode> cache = new HashMap();//链表前后节点哨兵,方便操作头尾。private final DLinkedNode head = new DLinkedNode();private final DLinkedNode end = new DLinkedNode();//初始化缓存public LRUCache(int capacity) {//不仅仅是赋值还要初始化链表//头尾节点互相指向head.next = end;end.prev = head;this.capacity = capacity;}public int get(int key) {//得到nodeDLinkedNode node = cache.get(key);//判断是否存在,存在就添加到链表头部if(node==null){return -1;}moveToNode(node);return node.value;}public void put(int key, int value) {DLinkedNode node = cache.get(key);if(node!=null){//已经存在就重新赋值node.value = value;moveToNode(node);}else{//不存在就要新建一个节点，在放入mapDLinkedNode Newnode = new DLinkedNode(key,value);cache.put(key,Newnode);addToTop(Newnode);size++;}//判断是否溢出if(size>capacity){//移除最后一个元素DLinkedNode endnode = end.prev;removeEndNode(endnode);}}//辅助方法//添加到链表头部public void addToTop(DLinkedNode node){node.prev = head;head.next.prev = node;node.next = head.next;head.next = node;}//移动链表到头部public void moveToNode(DLinkedNode node){removeNode(node);addToTop(node);}//移除nodepublic void removeNode(DLinkedNode node){node.next.prev = node.prev;node.prev.next = node.next;}//移除最后一个元素,还要清除hashpublic void removeEndNode(DLinkedNode node){removeNode(node);cache.remove(node.key);size--;}
}总结
本人是一个菜鸟，没怎么刷算法题，这算是我第一次刷算法题，不过基本的数据结构我还是会，这道题我是直接问的ai因为我完全没有思路，觉得这个很难，然后看了ai的解法，和思路，感觉非常清晰，就去自己动手写了一遍，一次过，很有成就感，后续也会继续刷题。
如果我的文章成功帮助了你，请点赞加关注，你们的支持是我最大的动力。
(5))
