Python solution using Dict + Single LinkedList


  • 0
    X

    class ListNode(object):
    slots = ('val', 'next')

    def __init__(self, val):
    	self.val = val
    	self.next = None
    

    class LinkedList(object):
    slots = ('head', 'tail')

    def __init__(self):
    	self.head = None
    	self.tail = None
    
    def insertTail(self, val):
    	node = ListNode(val)
    	if not self.head:
    		self.head = self.tail = node
    	else:
    		self.tail.next = node
    		self.tail = node 
    	return node
    
    def moveToTail(self, node):
    	if node is self.tail: # already tail
    		return ()
    
    	nodeval = node.val
    	nextnode = node.next
    	node.val = nextnode.val
    	node.next = nextnode.next  # remove nextnode
    	if nextnode is self.tail:
    		self.tail = node 
    
    	nextnode.val = nodeval
    
    	self.tail.next = nextnode
    	self.tail = nextnode
    	return node, nextnode
    
    
    def removeHead(self):
    	head = self.head
    	self.head = head.next 
    	head.next = None 
    
    	return head 
    

    class LRUCache(object):

    def __init__(self, capacity):
    	self.capacity = capacity
    	self.map = {}
    	self.lrulist = LinkedList()
    	
    def get(self, key):
    	if key in self.map:
    		node = self.map[key]
    		value = node.val[1]
    		for cn in self.lrulist.moveToTail(node):
    			self.map[cn.val[0]] = cn
    		return value
    	else:
    		return -1
    
    def put(self, key, value):
    	if key in self.map:
    		node = self.map[key]
    		node.val = (key, value)
    		for cn in self.lrulist.moveToTail(node):
    			self.map[cn.val[0]] = cn
    	else:
    		if len(self.map) == self.capacity: # full, remove one
    			head = self.lrulist.removeHead()
    			del self.map[head.val[0]]
    
    		node = self.lrulist.insertTail( (key, value) )
    		self.map[key] = node

Log in to reply
 

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