LeetCode-146-LRU缓存机制-Python

7次阅读

共计 2878 个字符，预计需要花费 8 分钟才能阅读完成。

题目来源：力扣（LeetCode）https://leetcode-cn.com/problems/lru-cache

运用你所掌握的数据结构，设计和实现一个 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

思路：哈希表、双向链表

首先，先解释一下 LRU，LRU（Least Recently Used），最近最少使用。它是一种缓存淘汰策略。

比如，正常来说缓存容量是有限的，如果希望删除一些内容时腾出空间时，这个时候就应该考虑删除哪些内容？哪些内容是没用的，可以删除的？哪些应该保留，是有用的？

LRU 这种策略，就认为最近使用的数据是有用的，而哪些长时间未使用的就是没用的，当缓存不足时，就会优先删除这些长时间未使用的。

这就是 LRU 这个策略的简单描述，当然还有其他的策略，比如 LFU 等。

再看本题，因为题目有个要求，【是否可以在 O(1) 时间复杂度内完成获取数据 get 和写入数据 put 操作？】

在这里就应该考虑，要实现时间复杂度 O(1) 内完成上面的操作，我们要使用的数据结构条件就应该具有以下的特点：查找、插入、删除都要快。

我们知道哈希表，查找速度快，但是没有顺序之分。而链表，插入删除快，有顺序，但是查找慢。此时，我们考虑将两者结合使用。

在这里，因为当缓存容量达到上限的时候，我们需要执行删除操作，此时删除节点，不仅要当前节点本身的指针，还需要前驱节点的指针，这里则需要使用双向链表，才能够在删除并查找前驱时，实现 O(1) 的时间复杂度。

那么现在来看，如果使用哈希表 + 双向链表实现功能设计：

首先双向链表部分，按照使用顺序存储键值对。靠近头部为最近使用，靠近尾部为非最近使用。
哈希表，键映射其在双向链表的位置。

具体实现的方法：

get：首先要判断 key 是否存在：
- 不存在返回 -1
- 存在时，此时对应的节点则定为最近使用。那么先定位它在双向链表的位置，将其移动到头部，返回该节点的值。
put：同样判断 key 是否存在：
- 不存在，创建新节点，在双向链表头部添加该节点，同时也要添加到哈希表中。同时还需要判断双向链表容量是否超出，如果超出，将末尾节点删除，同时删除哈希表对应部分。
- 存在时，通过哈希表定位在双向链表的位置，更新它的值，同时移动到双向链表头部。

具体的实现代码如下。

class Node(object):
    def __init__(self, key=0, value=0):
        self.key = key
        self.value = value
        self.prev = None
        self.next = None

class DoubleLinkedList(object):
    def __init__(self):
        self.head = Node(0, 0)
        self.tail = Node(0, 0)
        self.head.next = self.tail
        self.tail.prev = self.head
        self.size = 0
    
    def add_to_head(self, node):
        """添加节点到头部"""
        node.next = self.head.next
        node.prev = self.head
        self.head.next.prev = node
        self.head.next = node
        self.size += 1
    
    def remove_node(self, node):
        """删除节点"""
        node.prev.next = node.next
        node.next.prev = node.prev
        self.size -= 1
    
    def remove_tail(self):
        """删除尾部节点"""
        if self.size == 0:
            return None
        node = self.tail.prev
        self.remove_node(node)
        return node
    
    def get_size(self):
        return self.size

class LRUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.hashmap = {}
        self.cache = DoubleLinkedList()

    def get(self, key: int) -> int:
        # 判断 key 是否存在，分情况处理
        if key not in self.hashmap:
            return -1
        # 通过哈希表定位其在双向链表的位置
        value = self.hashmap[key].value
        # 这里实现的逻辑在 put 操作体现
        # put 操作在键存在时，同样需要移至链表头部
        self.put(key, value)
        return value

    def put(self, key: int, value: int) -> None:
        # 先创建节点
        node = Node(key, value)
        # 同样判断 key 是否存在
        # 分情况处理
        if key in self.hashmap:
            self.cache.remove_node(self.hashmap[key])
            self.cache.add_to_head(node)
            self.hashmap[key] = node
        else:
            # 判断缓存容量是否不够
            if self.capacity == self.cache.get_size():
                # 删除最后的节点
                tail = self.cache.remove_tail()
                self.hashmap.pop(tail.key)
            # 添加到头部
            self.cache.add_to_head(node)
            self.hashmap[key] = node



# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)