146. LRU缓存机制

我不是女神ヾ 2022-12-04 09:12 217阅读 0赞

# 146. LRU缓存机制 #

## 题目描述 ##

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。  
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。  
当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

使用包括：get和put操作

进阶:  
你是否可以在 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

## Python代码 ##

class ListNode:
        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.hashmap = {
        }  # 集合
            # 新建两个节点 head 和 tail
            self.head = ListNode()
            self.tail = ListNode()
            # 初始化链表为 head <-> tail
            self.head.next = self.tail
            self.tail.prev = self.head
    
        # 因为get与put操作都可能需要将双向链表中的某个节点移到末尾，所以定义一个方法
        def move_node_to_tail(self, key):
            # 先将哈希表key指向的节点拎出来，为了简洁起名node
            #      hashmap[key]                               hashmap[key]
            #           |                                          |
            #           V              -->                         V
            # prev <-> node <-> next         pre <-> next   ...   node
            node = self.hashmap[key]
            node.prev.next = node.next
            node.next.prev = node.prev
            # 之后将node插入到尾节点前
            #                 hashmap[key]                 hashmap[key]
            #                      |                            |
            #                      V        -->                 V
            # prev <-> tail  ...  node                prev <-> node <-> tail
            node.prev = self.tail.prev
            node.next = self.tail
            self.tail.prev.next = node
            self.tail.prev = node
    
        def get(self, key: int) -> int:
            res = self.hashmap.get(key, -1)
            if res == -1:
                return res
            else:
                # 如果已经在链表中了久把它移到末尾（变成最新访问的）
                self.move_node_to_tail(key)
                return res.value
    
        def put(self, key: int, value: int) -> None:
            if key in self.hashmap:
                # 如果key本身已经在哈希表中了就不需要在链表中加入新的节点
                # 但是需要更新字典该值对应节点的value
                self.hashmap[key].value = value
                # 之后将该节点移到末尾
                self.move_node_to_tail(key)
            else:
                if len(self.hashmap) == self.capacity:
                    # 去掉哈希表对应项
                    self.hashmap.pop(self.head.next.key)
                    # 去掉最久没有被访问过的节点，即头节点之后的节点
                    self.head.next = self.head.next.next
                    self.head.next.prev = self.head
                # 如果不在的话就插入到尾节点前
                new = ListNode(key, value)
                self.hashmap[key] = new
                new.prev = self.tail.prev
                new.next = self.tail
                self.tail.prev.next = new
                self.tail.prev = new
    
    
    if __name__ == '__main__':
        cache = LRUCache(2)
        cache.put(1, 1)
        cache.put(2, 2)
        print(cache.get(1))
        cache.put(3, 3)
        print(cache.get(2))
        cache.put(4, 4)
        print(cache.get(1))
        print(cache.get(3))
        print(cache.get(4))