咨询白癜风医院 http://baidianfeng.39.net/index.html一、题目
请你设计并实现一个满足LRU(最近最少使用)缓存约束的数据结构。
实现LRUCache类：
LRUCache(intcapacity)以正整数作为容量capacity初始化LRU缓存
intget(intkey)如果关键字key存在于缓存中，则返回关键字的值，否则返回-1。
voidput(intkey,intvalue)如果关键字key已经存在，则变更其数据值value；如果不存在，则向缓存中插入该组key-value。如果插入操作导致关键字数量超过capacity，则应该逐出最久未使用的关键字。
函数get和put必须以O(1)的平均时间复杂度运行。
二、示例2.1示例：
["LRUCache","put","put","get","put","get","put","get","get","get"][[2],[1,1],[2,2],[1],[,],[2],[4,4],[1],[],[4]][null,null,null,1,null,-1,null,-1,,4]LRUCachelRUCache=newLRUCache(2);lRUCache.put(1,1);//缓存是{1=1}lRUCache.put(2,2);//缓存是{1=1,2=2}lRUCache.get(1);//返回1lRUCache.put(,);//该操作会使得关键字2作废，缓存是{1=1,=}lRUCache.get(2);//返回-1(未找到)lRUCache.put(4,4);//该操作会使得关键字1作废，缓存是{4=4,=}lRUCache.get(1);//返回-1(未找到)lRUCache.get();//返回lRUCache.get(4);//返回4
提示：
1=capacity=
0=key=10
0=value=10^5
最多调用2*10^5次get和put
三、解题思路
根据题目描述，我们需要构造一个LRU缓存，那么我们需要解决两个问题：
实现对key和value的数据进行缓存。实现LRU的能力，即：最近最少使用。
那么针对第一个问题，我们可以采用哈希表或者数组的方式进行数据存储，因为本题的提示部分已经指出key值是在[0,10]区间内的，并不存在负数，所以为了提升执行速度，我们选择数组作为底层的存储结构。其中，需要注意的是，存储的value是下面要介绍的双向链表中的Node节点。
那么针对第二个问题，我们可以采用双向链表的方式进行支持，那么为什么是双向链表呢？因为当调用lRUCache.get()或lRUCache.set()方法对某个Node进行操作的时候，我们需要将这个Node放到链表的尾部，这样，就需要操作该Node节点的前置节点和后置节点，为了便于这种操作，所以我们采用双向链表。执行步骤如下所示：
断开PreNode与Node的链接关系；断开NextNode与Node的链接关系；链接PreNode与NextNode；将Node放到链表尾部；
那么这里还有一个小细节，就是如果待移动的节点在头节点，那么我们还需要进行特殊的判断（因为头节点没有前置节点PreNode），而同样的，如果待删除的节点是尾节点，那么我们也需要进行特殊的判断（因为尾节点没有后置节点NextNode）。为了统一处理逻辑，我们可以通过创建虚拟的头尾节点来解决这个问题，即：
Nodehead=newNode(-1,-1);Nodetail=newNode(-2,-1);head.next=tail;tail.pre=head;
由于我们可以知道LRU链表容量的，所以当超出这个容量的时候，就将整个链表中，第一个节点删除即可（不包含虚拟收尾节点），并将哈希表/数组中相应key对应的value置为null；以上就是这道题的解题思路，为了便于大家理解，我们通过创建2节点容量的LRU，具体看一下具体的处理过程，请见下图所示：
四、代码实现
classLRUCache{Node[]hashTable;//哈希表intcapacity=0,count=0;Nodehead,tail;publicLRUCache(intcapacity){this.capacity=capacity;hashTable=newNode[11];head=newNode(-1,-1);//虚拟头节点tail=newNode(-2,-1);//虚拟尾节点head.next=tail;tail.pre=head;}publicintget(intkey){Nodenode;if((node=hashTable[key])==null)return-1;//如果不存在，直接返回-1moveNode(node);//将node节点移动到末尾（位置是tail节点的pre节点）returnnode.value;}publicvoidput(intkey,intvalue){Nodenode;if((node=hashTable[key])!=null){//已存在节点，直接修改value值node.value=value;}else{//不存在节点，则新建Nodeif(countcapacity){//没有到达容量上限count++;}else{//超出容量上限，则需要删除“最近最少使用”的节点hashTable[head.next.key]=null;delNode(head.next);}node=newNode(key,value);hashTable[key]=node;}moveNode(node);//将node节点移动到末尾}//删除节点操作publicvoiddelNode(Nodenode){if(node.pre==null
node.next==null)return;node.pre.next=node.next;node.next.pre=node.pre;}//将节点移动到“末尾”操作（位置是tail节点的pre节点）publicvoidmoveNode(Nodenode){if(tail.pre==node)return;//如果已经是“末尾”节点，则不操作delNode(node);//删除该节点的前后关联，下面会进行重新关联操作tail.pre.next=node;node.pre=tail.pre;node.next=tail;tail.pre=node;}//双向链表结构classNode{publicintkey,value;publicNodepre,next;publicNode(intkey,intvalue){this.key=key;this.value=value;}}}
今天的文章内容就这些了：
写作不易，笔者几个小时甚至数天完成的一篇文章，只愿换来您几秒钟的点赞分享。
更多技术干货，欢迎大家
