144 - 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

解答

第一想法是用哈希表。记录一下有哪些数，以及使用次数。

或者多记录一个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.

哈希表+双向链表

https://leetcode-cn.com/problems/lru-cache/solution/shu-ju-jie-gou-fen-xi-python-ha-xi-shuang-xiang-li/

image-20191116233243147

增删查都要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.