A Python implement


  • -1
    C

    My Python implement,Like LinkedHashMap in Java .

     class Entry:
        def __init__(self,key,value,before=None,next=None):
            self.key = key;
            self.value = value;
            self.before = before;
            self.next = next;
    
        def __str__(self):
            return str((self.key,self.value))
    
    
    class LRUCache:
    
        # @param capacity, an integer
        def __init__(self, capacity):
            self.head = Entry(None,None)
            self.tail = Entry(None,None)
            self.head.next = self.tail;
            self.tail.before = self.head;
            self.capacity = capacity
            self.store = {}
    
        # @return an integer
        def get(self, key):
            entry = self.store.get(key)
            if entry == None:
                return -1;
            self.move_head(entry)
            return entry.value
    
    
        # @param key, an integer
        # @param value, an integer
        # @return nothing
        def set(self, key, value):
            if self.store.has_key(key):
                entry = self.store[key]
                entry.value = value;
                self.move_head(entry)
                return;
            if len(self.store)==self.capacity:
                entry = self.remove_tail()
                del self.store[entry.key]
            entry = Entry(key,value)
            self.insert_head(entry)
            self.store[key]=entry
    
    
        def insert_head(self,entry):
            curfirst = self.head.next;
            self.head.next = entry;
            entry.next = curfirst;
            entry.before = self.head
            curfirst.before = entry;
    
        def move_head(self,entry):
            b = entry.before
            n = entry.next
            b.next = n;
            n.before = b
            self.insert_head(entry)
    
        def remove_tail(self):
            cur_tail = self.tail.before;
            cur_tail.before.next = self.tail;
            self.tail.before = cur_tail.before
            return cur_tail
    
        def __str__(self):
            ret = "[ "
            cur = self.head.next;
            while cur != self.tail:
                ret = ret+str(cur)
                cur = cur.next;
            ret = ret+" ]"
            return ret;

Log in to reply
 

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