Jianbo Dai's

mq007.LRU缓存机制

 
  • Nov 04, 2020

题目链接

嗯嗯，第一眼看见这个题目感觉是用循环顺序表或者队列和哈希表来实现，可是尝试了之后发现一个问题，就是题目中的get操作也会使得某个值被操作从而改变其在顺序表/队列中的位置，这会导致每次get操作时都要按顺序将后半部分的元素往前位移之类的操作，从而时间复杂度为O（N）与题意不符合。所以我就考虑应该用链表加哈希表来实现，不过由于不太熟练就直接看了别人的解答，这题可以使用python里已有的结合了双向链表和哈希表的数据结构如OrderedDict（见实现2），当然这样就和题意不符了。所以这题需要自己将双向链表写出来（见实现1），这个实现的各项操作中，访问哈希表的时间复杂度为O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为O(1)。而将一个节点移到双向链表的头部，可以分成”删除该节点”和”在双向链表的头部添加节点”两步操作，都可以在O(1) 时间内完成。

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

class LRUCache1:

    def __init__(self, capacity: int):
        self.cache = dict()
        self.head = DLNode()
        self.rear = DLNode()
        self.head.next = self.rear
        self.rear.prev = self.head
        self.cap = capacity
        self.num = 0

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        else:
            node = self.cache[key]
            self.moveToHead(node)
            return node.value

    def put(self, key: int, value: int) -> None:
        if key not in self.cache:
            node = DLNode(key, value)
            self.cache[key] = node
            self.addToHead(node)
            self.num += 1
            if self.num > self.cap:
                removed = self.removeRear()
                self.cache.pop(removed.key)
                self.num -= 1
        else:
            node = self.cache[key]
            node.value = value
            self.moveToHead(node)

    def removeRear(self):
        node = self.rear.prev
        self.removeNode(node)
        return node

    def addToHead(self, node):
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node
    
    def moveToHead(self, node):
        self.removeNode(node)
        self.addToHead(node)
    
    def removeNode(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev

class LRUCache2(collections.OrderedDict):

    def __init__(self, capacity: int):
        super().__init__()
        self.capacity = capacity


    def get(self, key: int) -> int:
        if key not in self:
            return -1
        self.move_to_end(key)
        return self[key]

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.capacity:
            self.popitem(last=False)


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