题目描述
为最近最少使用（LRU）缓存策略设计一个数据结构，它应该支持以下操作：获取数据和写入数据。
get(key) 获取数据：如果缓存中存在key，则获取其数据值（通常是正数），否则返回-1。
set(key, value) 写入数据：如果key还没有在缓存中，则写入其数据值。当缓存达到上限，它应该在写入新数据之前删除最近最少使用的数据用来腾出空闲位置。
最终, 你需要返回每次 get 的数据
测试样例
输入：
LRUCache(2)
set(2, 1)
set(1, 1)
get(2)
set(4, 1)
get(1)
get(2)
输出：[1,-1,1]
解释：
cache上限为2，set(2,1)，set(1, 1)，get(2) 然后返回 1，set(4,1) 然后 delete (1,1)，因为 （1,1）最少使用，get(1) 然后返回 -1，get(2) 然后返回 1。
输入：
LRUCache(1)
set(2, 1)
get(2)
set(3, 2)
get(2)
get(3)
输出：[1,-1,2]
解释：
cache上限为 1，set(2,1)，get(2) 然后返回 1，set(3,2) 然后 delete (2,1)，get(2) 然后返回 -1，get(3) 然后返回 2。
解题思路
补充说明下题意，关键点在于当缓存容量满了的时候，若再往其中添加元素，需要删掉历史记录最久远的那条数据，也就是距离当前最长时间没有使用到的数据，这里“使用”的范畴涵盖了get和set，注意，不仅仅是get！
OK，那么我们理所当然会想到使用collections.OrderDict，但是面试时应该不会允许你使用这个内置模块，需要你自己实现。因此，我们就需要构思如何设计这个OrderDict，其能够根据加入顺序来对字典排序，从而每次在删除数据时都是将最早那条记录对应的数据删掉。
为了能够在O(1)复杂度下实现添加与删除操作，因此我们使用链表而非列表来记录这些数据序列。既然是OrderDict，那么其本质也必然是dict，所以我们让key指向链表的每个node，在添加/删除dict的item对时同时也添加/删除这个key在链表中对应的node。
我们需要自己是实现链表的Node类型，设置4个属性：key、val、prev、next。
另外，我们为OrderDict设置head、tail两个属性（Node类型），作为dummy node，初始化时head.next = tail，tail.prev = head，这样便将它们链接起来形成了链表，后续插入和删除都针对这条链进行即可。
在实现OrderDict的popitem()方法时，我们取的key是head.next这个node对应的key，代表最早的那条记录，然后调用pop(key)删掉对应的数据与链表节点。
关于OrderDict的具体实现看下一节的代码，这里还要谈谈题目要求实现的LRUCache中的get()和set()方法。
对于get()方法，先判断key是否存在，如果是，那么先pop然后再存进来，最后返回pop()出来的值。之所以先pop是因为更新下使用记录，代表最近使用了这个数据；如果不是，那么返回-1。
而对于set()方法，如果key存在，那么pop掉对应的数据，之所以要先pop也是为了更新使用记录，将旧的这个key-value对应的node在链表中删除；否则（key不存在）如果当前空间已满，那么调用popitem删掉最老的那条数据。最后无论哪种情况都要将这个新的key-value对加入OrderDict中。
代码实现
class Node:
"""链表节点"""
def __init__(self, key, val):
self.key = key
self.val = val
# 链接前一个和后一个节点
self.prev = None
self.next = None
class OrderDict:
"""有序字典，按照插入顺序排序，popitem弹出最先插入的key-value对"""
def __init__(self):
# 头、尾是两个dummy node节点
self.head = Node(-1, -1)
self.tail = Node(-1, -1)
# 相互链接形成链表
self.head.next = self.tail
self.tail.prev = self.head
self.dict = {}
def __len__(self):
return len(self.dict)
def __contains__(self, key):
return key in self.dict
def __getitem__(self, key):
return self.dict[key].val
def __setitem__(self, key, val):
node = Node(key, val)
self.tail.prev.next = node
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev = node
self.dict[key] = node
def __delitem__(self, key):
node = self.dict.pop(key)
node.prev.next = node.next
node.next.prev = node.prev
def pop(self, key):
if key not in self.dict:
raise KeyError(str(key))
val = self.dict[key].val
# 将key对应的节点在链表中删掉
self.__delitem__(key)
return val
def popitem(self):
if not self.dict:
raise KeyError('dictionary is empty')
# FIFO
key = self.head.next.key
val = self.pop(key)
# 仿照collections.OrderDict，返回key-value对
return key, val
class LRUCache:
"""
@param: capacity: An integer
"""
def __init__(self, capacity):
# do intialization if necessary
self.cache = OrderDict()
self.capacity = capacity
"""
@param: key: An integer
@return: An integer
"""
def get(self, key):
# write your code here
if key in self.cache:
val = self.cache.pop(key)
self.cache[key] = val
return val
else:
return -1
"""
@param: key: An integer
@param: value: An integer
@return: nothing
"""
def set(self, key, value):
# write your code here
if key in self.cache:
self.cache.pop(key)
elif len(self) == self.capacity:
self.cache.popitem()
self.cache[key] = value
def __len__(self):
return len(self.cache)
网友评论