Clean Python Solution O(1)

  • 0
    class List(object):
        def delete(elem):
   = elem.prev
            return elem
        def move(elem, newPrev, newNext):
            elem.prev = newPrev
   = newNext
   = elem
            newNext.prev = elem
        def append(head, elem):
            List.move(elem, head.prev, head)
        def initHead(head):
            head.prev = = head
    class Node(object):
        def __init__(self, key, value, head):
            self.key = key
            self.value = value
            self.head = head
            self.prev = = None
        def hit(self):
            List.append(self.head, self)
    class LRUCache(object):
        def __init__(self, capacity):
            :type capacity: int
            self.d = {}
            self.cap = capacity
            self.head = Node(-1, -1, None)
        def get(self, key):
            :rtype: int
            if key not in self.d:
                return -1
            return self.d[key].value
        def set(self, key, value):
            :type key: int
            :type value: int
            :rtype: nothing
            if self.cap == 0:
            if key in self.d:
                self.d[key].value = value
                if len(self.d) >= self.cap:
                    oldNode = List.delete(
                    del self.d[oldNode.key]
                newNode = Node(key, value, self.head)
                List.append(self.head, newNode)
                self.d[key] = newNode

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.