赞
踩
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类:
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例:
输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废,缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废,缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
LRU缓存也算是比较高频和经典的题目了,尤其是后端选手很容易遇到这个题(不过我这里是用python来实现的)。对于LRU主要就是定义一个get和一个put的接口,然后每次操作到相关的数据之后,就需要把该数据更新到面板最前面。
首先直接说实现方式和结论:为了使get和put的平均时间复杂度都为O(1),我们需要使用一个双向链表和一个哈希表。
根据题意,每次存入的数据都是key-value的形式,因此对于链表中的每一个节点,内部至少有两个变量:key和value,其次因为它是双向链表,我们要需要pre指针和next指针;而哈希表的使用则是这样的:哈希表中的key就是存入数据的key,哈希表中的value就是节点,直观点可以这么理解:哈希表[3]=Node(3,5),即int型对应Node型。
因此节点的定义方式是这样的:
class ListNode():#里面有四个变量
def __init__(self,key=None,value=None):
self.key = key
self.value=value
#还有两个指针,创建了但是没值,就等于None吧
self.pre=None
self.next=None
整个LRUCache的定义方式是这样的:
class LRUCache():
def __init__(self,capacity): #一开始除了头尾节点外,长度为0,头尾互相指
self.head=ListNode()#头结点
self.tail=ListNode()#尾节点
self.head.next=self.tail#头节点的next初始化指向尾
self.tail.pre=self.head#为节点的pre初始化指向头
self.hashmap={} #双向链表有了,再定义一个哈希表
self.capacity=capacity#第四个参数 容量
数据结构弄清了,接下来就是put和get的算法部分。
在说get和put之前,先要弄清一个事情,LRU的一大特点就是在操作某个数据之后,需要我们把某个数据移动到“最上面”,表示刚刚操作过。因此后面不管是get还是put都会有这个需求,我们可以提前定义出来。目前我们的双向链表头结点是head,尾节点是tail,这两个变量我们不会用来存放实际数据,只是用于插入和取出真正的首位数据。
注意:我这里默认越往右的数据越新,越往左的数据越老。
比如现在我们要把数据移到LRU的“最上面”、“最新处”,我们把这个功能叫做move_to_first,而这个first的位置是在最右边,也就是tail之前的那个节点。而最老的节点在哪呢?在head的后面。
知道了first的位置,我们定义起这个功能就很简单了:
def move_to_first(self,key):
node = self.hashmap[key] #把node从当前双向链表取出
#取出时让原来的左右两边相连,不要断开
node.pre.next=node.next
node.next.pre=node.pre
#把node移动到最后当作first (严格说其实是tail的前面一位,head,tail始终首尾)
#双向链表插入节点方式:先建立新链接(前两句)再断开和改变原链接(后两句)
node.next=self.tail
node.pre = self.tail.pre
node.next.pre=node
node.pre.next=node
现在我们可以正式开始看get和put了。
首先是get,这个很简单,通过哈希表来进行get(key)的查找,复杂度就是O(1),如果查不到则按提议返回-1,若查到了则返回这个Node的value值,并且因为get过这个数字,需要把这个节点move_to_first。
其次是put,put是往链表里添加节点了,会涉及到容量capacity的问题,所以会麻烦一些。Put的总体逻辑是这样的:首先判断要添加的节点的key在不在哈希表中,如果在的话,我们不需要添加新节点,只需要更新value值即可,并且将其move_to_first。如果不在哈希表中,我们要先去判断容量是否足够,如果容量足够,则我们直接在first(tail之前)的位置插入这个新节点;如果容量不够,则需要先删除最末尾(head之后)的节点,空出一个位置后,再在first位置插入这个新节点。
- # class LRUCache:
-
- # def __init__(self, capacity: int):
-
- # def get(self, key: int) -> int:
-
- # def put(self, key: int, value: int) -> None:
-
- class ListNode():#里面有四个变量
-
- def __init__(self,key=None,value=None):
-
- self.key = key
-
- self.value=value
-
- #还有两个指针,创建了但是没值,就等于None吧
-
- self.pre=None
-
- self.next=None
-
- class LRUCache():
-
- def __init__(self,capacity): #一开始除了头尾节点外,长度为0,头尾互相指
-
- self.head=ListNode()#头结点
-
- self.tail=ListNode()#尾节点
-
- self.head.next=self.tail#头节点的next初始化指向尾
-
- self.tail.pre=self.head#为节点的pre初始化指向头
-
- #双向链表有了,再定义一个哈希表
-
- self.hashmap={}
-
- #第四个参数 容量
-
- self.capacity=capacity
-
- def move_to_first(self,key):
-
- node = self.hashmap[key] #把node从当前双向链表取出
-
- #取出时让原来的左右两边相连,不要断开
-
- node.pre.next=node.next
-
- node.next.pre=node.pre
-
- #把node移动到最后当作first (严格说其实是tail的前面一位,head,tail始终首尾)
-
- #双向链表插入节点方式:先建立新链接(前两句)再断开和改变原链接(后两句)
-
- node.next=self.tail
-
- node.pre = self.tail.pre
-
- node.next.pre=node
-
- node.pre.next=node
-
- #按要求写get方法,传入一个key
-
- def get(self,key):
-
- #判断有无
-
- if key not in self.hashmap:
-
- return -1#无则直接返回-1
-
- #如果有,调用move_to_first更新一波
-
- self.move_to_first(key)
-
- node = self.hashmap[key]#通过哈希表取出节点
-
- return node.value#通过节点取出值
-
- #put方法,传入key和value两个值
-
- def put(self,key,value):
-
- #首先判断key是不是已经在hash表中了
-
- if key in self.hashmap:
-
- node = self.hashmap[key]
-
- node.value=value#有则更新值
-
- #再移至第first
-
- self.move_to_first(key)
-
- else:#不在hash表里
-
- #判断够不够装下
-
- if len(self.hashmap)==self.capacity:#已经满了
-
- #删除掉head后面的节点
-
- #既要删除节点 还要删除哈希表中的映射!!!不要漏写
-
- delete_key = self.head.next.key#定位到要删除的key
-
- self.hashmap.pop(delete_key)#哈希表删除映射,这里容易漏
-
- #删除这个节点
-
- self.head.next = self.head.next.next
-
- self.head.next.pre = self.head
-
- #插入这个新节点
-
- node = ListNode(key,value)#new一个节点
-
- self.hashmap[key]=node#建立映射
-
- #双向链表插入节点方式:
-
- #先建立新链接(前两句)再断开和改变原链接(后两句)
-
- node.next=self.tail
-
- node.pre=self.tail.pre
-
- node.next.pre = node
-
- node.pre.next=node
LRU机制首先得知道它是做什么的,清楚它最基本的机制(好像就类似于手机后台的缓存一样,刚刚用过的会出现在最上面,很久不用的在最底部直至被淘汰挤没)。然后要记住满足题目复杂度的实现方法:使用双向链表+哈希表。此外把尝试用的功能move_to_first提前定义出来,方便put和get等地方的调用。最后要注意一些细节,put 的时候先查找是否已存在,插入的时候考虑容量等。
总体来说LRU看起来步骤挺复杂的但是逻辑很清楚,不过能不出错地一遍写出来也不是很容易。写的时候要注意细节,一定要自己亲自写一下才知道哪些地方要注意。
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。