LeetCode 146. LRU缓存机制
题目描述
运用你所掌握的数据结构,设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作: 获取数据 get 和 写入数据 put 。
获取数据 get(key) – 如果密钥 (key) 存在于缓存中,则获取密钥的值(总是正数),否则返回 -1。
写入数据 put(key, value) – 如果密钥不存在,则写入其数据值。当缓存容量达到上限时,它应该在写入新数据之前删除最近最少使用的数据值,从而为新的数据值留出空间。
进阶:
你是否可以在 O(1) 时间复杂度内完成这两种操作?
示例:
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 该操作会使得密钥 2 作废 cache.get(2); // 返回 -1 (未找到) cache.put(4, 4); // 该操作会使得密钥 1 作废 cache.get(1); // 返回 -1 (未找到) cache.get(3); // 返回 3 cache.get(4); // 返回 4
题目的地址
用库函数实现
Java中的LinkedHashMap
Python中的OrderedDict
都是属于有“顺序”的map,他们有散列表的特点,同时元素的顺序是按照先进来的在前面,后进来的在后面这样存放的。
下图是一个有“顺序”的map内部存储结构
1:100,表示key为1,value为100
key=1 是最先放入的,key=4是最后放入的
当访问一个元素时
1.如果这个元素不在容器中,返回-1
2.如果在容器中,就返回这个值,同时还要将这个元素从容器中删除,再插入最后最后(最后一个位置代表是最新的)
当新插入一个元素
1.如果key在容器中,这时候还分为两种情况
容器满了,或者容器没满
我们可以统一处理这种情况,直接将这个元素删除就行了,之后再插入一次就行了
2.如果key不在容器中,这时候也分两种情况
容器满了,这时候我们要删除一个元素,直接删除容器最左边的元素就可以了
如果容器没满,啥也不用做
最后,将这个新元素插入即可
实现代码如下
class LRUCache(object): def __init__(self, capacity): """ :type capacity: int """ import collections # 我们创建一个self.d的变量,用来表示OrderedDict self.d = collections.OrderedDict() # 同时,还要记录容器的大小,当容器满的时候会用到这个变量做判断 self.size = capacity def get(self, key): """ :type key: int :rtype: int """ # 当key在容器中时,首先获取这个元素,然后删除这个元素,再重新插入(重新插入到最右端) if(key in self.d): value = self.d[key] del self.d[key] self.d[key] = value return value # 如果key不在容器中,直接返回-1即可 return -1 def put(self, key, value): """ :type key: int :type value: int :rtype: None """ # 如果key在容器中,这时候有两种情况,容器满了/或者没满,我们就将这个元素删除就行了 # 因为删除完了就肯定会多出一个空位了,这样就可以插入元素了,然后最后收尾的时候将元素 # 插入到容器右端就可以了 if(key in self.d): del self.d[key] self.d[key] = value # 如果key不在容器中,同样也有两种情况,容器满了/或者没满,满的判断方式是 # 容器的长度==self.size,如果没满就啥也不做直接添加,等加的元素足够多时, # 就会触发else里面的那个if判断了。 # 之后删除容器最左边的元素(最老的元素) else: if(len(self.d)==self.size): self.d.popitem(False) # 统一处理,不管上面怎么操作,最后都将新元素插入到容器右端,页就是最新的位置 self.d[key] = value
用双链表实现
LRU缓存需要两种数据结构,map和双链表
这里我们就自己手动构造一个双链表
map的key指向的value就是双链表中的一个节点(下面代码实现中的Node类)
双链表中的每个元素都是有pre(前驱)指针,next(后继)指针,我们通过tail尾节点就可以很快定位到最后一个元素,然后将这个元素删除(删除最久没有使用的元素)
同样,根据map中的key也可以快速定位到一个Node,然后找到这个Node的值并返回
双链表实现的数据结构如下
再看下面这个图,假设LRU现在有四个元素,key分别是3,1,5,2
当2这个元素被访问时,就要从双链表中删除,然后插入到双链表的最开头,至于map中的key不同
当插入一个元素,比如还是2:200(key和value跟以前一样),此时要从双链表的最后删除一个元素,然后再新插入一个元素到双链表的最开头,当然map中的key也要删除,因为散列规则的原因,map中的2最后看起来还是放到了map中最后一个
代码实现如下:
# 增加一个Node类,用来表示双链表中的一个节点,其中每个节点有pre指针(指向上一个元素),还有next # 指针(指向下一个元素),以及key和value,注意这里的key实际上是冗余了。当LRU缓存满了,我们要 # 删除双链表中最后一个元素,之后还要删除map中对应的元素,此时删除链表中的元素很容器,但删除 # map中的元素就不知道怎么办了,原因是map和双链表之间没有任何关联,所以这里冗余了一份key,用来 # 再删除map中对应的元素 class Node(object): def __init__(self,key=None,val=None): self.pre = None self.next = None self.key = key self.val = val class LinkList(object): # 创建两个节点,head和tail,初始的时候 head <--> tail def __init__(self): self.head = Node() self.tail = Node() self.head.pre = self.tail self.head.next = self.tail self.tail.pre = self.head self.tail.next = self.head # 将一个节点插入到双链表的最开头,这个操作用来表示Node节点是最新的 def add_to_first(self,node): node.next = self.head.next self.head.next.pre = node node.pre = self.head self.head.next = node # 根据传入的node,删除双链表中的节点 def delete(self,node): pre_node = node.pre next_node = node.next pre_node.next = next_node next_node.pre = pre_node node.pre = None node.next = None # 获取最后一个元素,当LRU缓存满时,就需要拿到最后一个元素然后删除 def get_last(self): return self.tail.pre class LRUCache(object): # 创建三个变量,remian用于记录当前还有多少空闲位置,d是python内置的map # 还有一个link_list表示自定义的双链表 def __init__(self, capacity): """ :type capacity: int """ self.remain = capacity self.d = dict() self.link_list = LinkList() # 这个get()函数跟 用库函数实现的那个一样,也是key不再就直接返回-1 # key存在了就获取这个元素,然后从self.d(也就是内置的map中)删除,再从双链表中删除 # 最后将这个元素插入到双链表的最开头 def get(self, key): """ :type key: int :rtype: int """ if(key not in self.d): return -1 node = self.d[key] self.link_list.delete(node) self.link_list.add_to_first(node) return node.val # put函数的逻辑其实跟 库函数实现的那一套类似,只是因为很多事情库函数帮我们去做了,所以 # 自定义双链表去实现就需要多一些步骤 def put(self, key, value): """ :type key: int :type value: int :rtype: None """ # 首先是key如果在LRU中,也就是self.d中,那就直接删除这个元素,最后再统一插入就可以 if(key in self.d): tmp = self.d[key] self.link_list.delete(tmp) del self.d[tmp.key] # 如果key不在LRU中,这里也分为两种情况,LRU满了/或者LRU没满 else: # 如果remain>0 就说明没满,remain--就可以了,最后收尾的时候会插入一个新元素 if(self.remain > 0): if(key not in self.d): self.remain -=1 # 如果LRU满了,就需要从双链表中获取最后一个元素,然后删除 # 这里可以将if-else直接改成一个if,类似上面用库函数的那种方式 # if(len(slef.d)==self.remain) 就可以了 else: tmp = self.link_list.get_last_node() del self.d[tmp.key] self.link_list.delete(tmp) # 最后统一插入新元素 node = Node(key,value) self.d[key] = node self.link_list.add_to_first(node)
20 次阅读