Python solution without using OrderedDict (beats 95.54%)


  • 0
    N
    class LRUCache(object):
        
        class Node(object):
            def __init__(self, data=None, prev=None, next=None):
                self.data = data
                self.prev = prev
                self.next = next
    
        def __init__(self, capacity):
            """
            :type capacity: int
            """
            self.cache = {}
            self.order = self.Node()
            self.tail = self.order
            self.capacity = capacity
            self.count = 0
            
        def moveNodeToFront(self, node):
            if self.order.next is not node:
                if self.tail is node:
                    self.tail = node.prev
                node.prev.next = node.next
                if node.next:
                    node.next.prev = node.prev
                self.order.next.prev = node
                node.next = self.order.next
                self.order.next = node
                node.prev = self.order
    
        def get(self, key):
            """
            :rtype: int
            """
            node = self.cache.get(key)
            if node is not None:
                self.moveNodeToFront(node)
                return node.data[1]
            return -1
            
    
        def set(self, key, value):
            """
            :type key: int
            :type value: int
            :rtype: nothing
            """
            node = self.cache.get(key)
            if node is not None:
                node.data = (key, value)
                self.moveNodeToFront(node)
                return
            if self.count is not 0 and self.count == self.capacity:
                del self.cache[self.tail.data[0]]
                if self.count is 1:
                    self.order.next = None
                    self.tail = self.order
                else:
                    self.tail.prev.next= None
                    self.tail = self.tail.prev
            else:
                self.count += 1
            node = self.Node((key, value), self.order, self.order.next)
            if self.order.next:
                self.order.next.prev = node
            else:
                self.tail = node
            self.order.next = node
            self.cache[key] = node
    

Log in to reply
 

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