设计类

LRU cache

设计一个 LRU cache

class LRUCache:
    class ListNode:
        def __init__(self, val=None, key=None, prev=None, next=None):
            self.val = val
            self.key = key
            self.prev = prev
            self.next = next
    def __init__(self, capacity: int):
        self.hashMap = {}
        self.head = self.ListNode()
        self.tail = self.ListNode()
        self.head.next = self.tail
        self.tail.prev = self.head
        self.capacity = capacity
        self.count = 0
    def move_to_head(self, head, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        node.next = head.next
        node.prev = head
        node.next.prev = node
        head.next = node
    def get(self, key: int) -> int:
        if key in self.hashMap:
            self.move_to_head(self.head, self.hashMap[key])
            return self.hashMap[key].val
        else:
            return -1
    def del_node(self, node):
        node.prev.next = node.next
        node.next.prev = node.prev
        del self.hashMap[node.key]
    def insert_new(self, node):
        self.head.next.prev = node
        node.prev = self.head
        node.next = self.head.next
        self.head.next = node
    def put(self, key: int, value: int) -> None:
        if key in self.hashMap:
            self.hashMap[key].val = value
            self.move_to_head(self.head, self.hashMap[key])
            return
        if self.count >= self.capacity:
            self.del_node(self.tail.prev)
            new_node = self.ListNode(val=value, key=key)
            self.insert_new(new_node)
            self.hashMap[key] = new_node
        else:
            new_node = self.ListNode(val=value, key=key)
            self.insert_new(new_node)
            self.hashMap[key] = new_node
            self.count += 1
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)