Give the good answer in local but wrong answers during submissions ?


  • 0
    P
       struct Node
       {
            int key;
        int value;
        Node * prev;
        Node * next;
    
            Node(int k, int v) : key(k), value(v), prev(NULL), next(NULL)
            {
            }
       };
    
       struct DoubleLinkedList
       {
         Node * head;
         Node * last;
    
         DoubleLinkedList(): head(NULL), last(NULL)
    	{
    		
    	}
    
         ~DoubleLinkedList()
    	{
    		for(Node * tmp = head; tmp != NULL; tmp = tmp->next)
    			delete tmp;
    	}
    
           Node * InsertNode(int key, int value)
    	{
    		// Insert the node at the head of the list
    		Node * newnode = new Node(key, value);
    		newnode->next = head;
    		if(head)
    		{
    			head->prev = newnode;
    			head = newnode;
    		}
    		else
    		{
    			head = newnode;
    			last = newnode;
    		}
    
    		return newnode;
    	}
    
           void RemoveLastNode()
    	{
    		assert(last != NULL);
    		Node * prevLastNode = last->prev;
    		delete last;
    		last = prevLastNode;
    		if(last)
    			last->next = NULL;
    		else
    			head = NULL;
    	}
    
            int GetNode(Node * node)
    	{
    		if(node == head)
    		{
    			return node->value;
    		}
    		else
    		{
    			if(node == last)
    			{
    				node->next = head;
    				head->prev = node;
    				node->prev->next = NULL;
    				last = node->prev;
    				node->prev = NULL;
    				head = node;
    			}
    			else
    			{
    				node->prev->next = node->next;
    				node->next->prev = node->prev;
    				node->next = head;
    				head->prev = node;
    				node->prev = NULL;
    				head = node;
    			}
    			return head->value;
    		}
    	}
         };
    
       class LRUCache
       {
       public:
    
           LRUCache(int capacity): m_CurrentSize(0), m_Capacity(capacity)
    	{		
    	}
    
           int get(int key)
    	{
    		if(m_Container.find(key) == m_Container.end())
    			return -1;
    		else
    		{
    			Node * n = m_Container[key];
    			return priorityList.GetNode(n);
    		}
    	}
    
            void set(int key, int value)
    	{
    		if(m_Container.find(key) == m_Container.end())
    		{
    			if(m_CurrentSize == m_Capacity)
    			{
    				// Remove the key from the map
    				m_Container.erase(priorityList.last->key);
    				priorityList.RemoveLastNode();
    				// Remove the corresponding key from the map
    				m_Container[key] = priorityList.InsertNode(key, value);
    			}
    			else
    			{
    				m_Container[key] = priorityList.InsertNode(key, value);
    				m_CurrentSize++;
    			}
    		}
    	}
    
           int m_CurrentSize;
           int m_Capacity;
               DoubleLinkedList priorityList;
           std::unordered_map<int, Node *> m_Container;
        };

  • 0
    L

    Actually, I think I have the same issue as you:

    Specifically, this is output from the leetcode:

    Input: 1, [set(2,1),get(2)]
    Output: [-1]
    Expected: [1]
    

    My local answer to such a scenario:

    LRUCache c(1);
    c.set(2, 1);
    cout << c.get(2);
    

    is 1. However, the leetcode says that it is -1. I am confused what is going on with this. My solution is implemented in C++.

    Thanks,


Log in to reply
 

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