题目
运用你所掌握的数据结构，设计和实现一个 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
解答
第一想法是用哈希表。记录一下有哪些数，以及使用次数。
或者多记录一个set，每次get了啥就push进去，超过缓存容量的get，就记录，下次有put就删掉
有序字典
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = collections.OrderedDict()
def get(self, key: int) -> int:
if key not in self.data:
return -1
self.data.move_to_end(key)
return self.data[key]
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data.move_to_end(key)
self.data[key] = value
if len(self.data) > self.capacity:
self.data.popitem(last=False)
Runtime: 192 ms, faster than 95.99% of Python3 online submissions for LRU Cache.
Memory Usage: 22 MB, less than 27.27% of Python3 online submissions for LRU Cache.
python特有的数据结构，就是一个字典，但是有方法可以把里面元素放到最后。
感觉其他语言也可以写一个类似的函数
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.data = new Map()
this.capacity = capacity
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (this.data.has(key)) {
const value = this.data.get(key)
this.data.delete(key)
this.data.set(key, value)
return value
} else {
return -1
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.data.has(key)) {
this.data.delete(key)
} else if (this.data.size === this.capacity) {
const first_key = this.data.keys().next().value
this.data.delete(first_key)
}
this.data.set(key, value)
};
Runtime: 220 ms, faster than 31.35% of JavaScript online submissions for LRU Cache.
Memory Usage: 58.9 MB, less than 30.00% of JavaScript online submissions for LRU Cache.
哈希表+双向链表
增删查都要O(1)，因此就用哈希表+双向链表
class DLinkedNode():
def __init__(self, key=None, value=None):
self.key = key
self.value = value
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.data = {}
self.head = DLinkedNode()
self.tail = DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def move_to_tail(self, key: int) -> None:
node = self.data[key]
node.prev.next = node.next
node.next.prev = node.prev
node.prev = self.tail.prev
node.next = self.tail
self.tail.prev.next = node
self.tail.prev = node
def get(self, key: int) -> int:
if key in self.data:
self.move_to_tail(key)
res = self.data.get(key, -1)
if res == -1:
return -1
else:
return res.value
def put(self, key: int, value: int) -> None:
if key in self.data:
self.data[key].value = value
self.move_to_tail(key)
else:
if len(self.data) == self.capacity:
node = self.head.next
self.data.pop(node.key)
self.head.next = node.next
node.next.prev = self.head
new = DLinkedNode(key, value)
self.data[key] = new
new.next = self.tail
new.prev = self.tail.prev
self.tail.prev.next = new
self.tail.prev = new
Runtime: 216 ms, faster than 70.19% of Python3 online submissions for LRU Cache.
Memory Usage: 22.6 MB, less than 6.06% of Python3 online submissions for LRU Cache.
