LeetCode - LRU怎么将书架上的旧书完美淘汰呢

你有一排书架，有空时会拿些书来看，经常性会买些新书。无奈书架容量有限，当新买的书放不下时，需要一个策略将旧书淘汰。
LRU（最近最少使用）缓存淘汰机制正合适。
1)新买的书放在最左侧。
2)最近常看的书也放在最左侧。
久而久之，越往右边的书越是长时间没看，当有新书时，就从右侧淘汰起。Perfect。

下面一起来动手实现这个算法。附加条件只有一个，要在 O(1) 的时间复杂度内完成操作。

查找操作能在O(1)的数据结构：哈希
增、删除操作能在O(1)的数据结构：链表
所以考虑哈希 + 单链或哈希 +双链表。不过现实中，双链表的使用场景远多于单链表。
原因大家仔细考虑下，欢迎留言

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):
        self.capacity = capacity
        self.hashmap = {}
        
        # 哨兵
        self.head = ListNode()
        self.tail = ListNode()
        
        self.head.next = self.tail
        self.tail.prev = self.head
        
    def move_node_to_tail(self, key):

        node = self.hashmap[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.hashmap:
            self.move_node_to_tail(key)
        res = self.hashmap.get(key, -1)
        if res == -1:
            return res
        else:
            return res.value
        
    def put(self, key:int, value:int)->int:
        if key in self.hashmap:
            self.hashmap[key].value= value
            self.move_node_to_tail(key)
            return
        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

LeetCode - LRU怎么将书架上的旧书完美淘汰呢

推荐阅读