help to review on Python code error!


  • 0
    W
    class Node:
        def __init__(self,k,x):
            self.key=k
            self.val=x
            self.prev=None
            self.next=None
    
    class DoubleLinkedList:
        def __init__(self):
            self.tail=None
            self.head=None
            
        def removeLast(self):
            self.remove(self.tail)
            
        def remove(self,node):
            # case1
            if self.head == self.tail:                 
                self.head,self.tail = None,None
                return 
    
            # case2: node head, do nothing  
            if node == self.head or self.tail == self.head:                     
                return
    
            # case3: node tail
            if node == self.tail:                    
                node.prev.next = None                 # new tail node has no 'next'
                self.tail = node.prev                 # !!need update self.tail here!
                node.prev = None
                return
    
            node.prev.next = node.next                
            node.next.prev = node.prev
            node.prev = None
            node.next = None
            
    
        def moveToHead(self, node):
            if not self.head:                           
                self.head = node
                self.tail = node
                node.prev = node.next = None
                return
    
            # case2: current node is head already, or current only one node:
            if node == self.head or self.tail == self.head:   
                return
    
            if node != self.head:
                node.next = self.head
                self.head.prev = node
                self.head = node
                node.prev = None
    
    
    class LRUCache:
        # @param capacity, an integer
        def __init__(self, capacity):
            self.capacity = capacity
            self.size = 0
            self.P = dict()
            self.cache = DoubleLinkedList()
    
        # @return an integer
        def get(self, key):
            if key in self.P:
                self.cache.remove(self.P[key])
                self.cache.moveToHead(self.P[key])
                return self.P[key].val
            else:
                return -1
    
        def put(self, key, value):
            if key in self.P:
                self.cache.remove(self.P[key])
                self.cache.moveToHead(self.P[key])
                self.P[key].val = value
            else:
                node = Node(key,value)
                self.P[key] = node
                self.cache.moveToHead(node)
                self.size += 1
                if self.size > self.capacity:
                    self.size -= 1
                    del self.P[self.cache.tail.key]
                    self.cache.removeLast()
    
    

    I get error in case:
    Input:
    ["LRUCache","put","put","get","put","get","put","get","get","get"]
    [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]
    Output:
    [null,null,null,1,null,2,null,-1,3,4]
    Expected:
    [null,null,null,1,null,-1,null,-1,3,4]

    Can anyone help to debug on this? I tried many times, still didn't figure out why....


Log in to reply
 

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