The result is correct in visual stuido 2008,but leetcode says "runtime error"


  • 0
    A

    This is my code ,It runs correctly in visual studio 2008,and output the correct answer,but leetcode always says "runtime error".
    The test case is "set(2,1),get(2),set(3,2),get(2),get(3)".

    typedef struct _Node_{
    
    	int key;    
    	int value;  
    
    	struct _Node_ *next;  //next node
    	struct _Node_ *pre;   //previous node
    
    }CacheNode;
    
    class LRUCache{
    private:
    
    	int cache_size_;                   //cache length
    	int cache_real_size_;              //real cache length
    	CacheNode *p_cache_list_head;      //head node point
    	CacheNode *p_cache_list_near;      //tail node point
    	map<int ,CacheNode> mapNodes;       //map which store the CacheNode,we could use this to save much time                   when we seach the CacheNode
    
    	void detachNode(CacheNode *node) //remove the node
    	{
    		node->pre->next=node->next;
    		node->next->pre=node->pre;
    	}
    	void addToFront(CacheNode *node) //insert the node to the first node
    	{
    		node->next=p_cache_list_head->next;
    		p_cache_list_head->next->pre=node;
    		p_cache_list_head->next=node;
    		node->pre=p_cache_list_head;
    	}
    
    public:
    	LRUCache(int capacity) {
    		cache_size_=capacity;  
    		cache_real_size_=0;  
    		p_cache_list_head=new CacheNode();  
    		p_cache_list_near=new CacheNode();  
    		p_cache_list_head->next=p_cache_list_near;  
    		p_cache_list_head->pre=NULL;  
    		p_cache_list_near->pre=p_cache_list_head;  
    		p_cache_list_near->next=NULL;  
    	}
    
    	int get(int key) {
    		map<int,CacheNode >::iterator iter;
    		CacheNode * p=NULL;
    		iter=mapNodes.find(key);//search the node 
    		if (iter!=mapNodes.end())//if we find it ,put it in the fisrt place and return the value
    		{
    			p=&(iter->second);
    			detachNode(p);
    			addToFront(p);
    			return p->value;
    		}
    		return -1;
    	}
    
    	void set(int key, int value) {
    
    		map<int,CacheNode>::iterator iter;
    		CacheNode *p=NULL;
    		iter=mapNodes.find(key);
    		if (iter!=mapNodes.end())
    		{
    			p=&(iter->second);
    			p->value=value;
    			get(key);
    			return ;
    		}
    
    		if(cache_real_size_ >= cache_size_)
    		{
    			p=p_cache_list_near->pre->pre;
    			delete p->next;
    			p->next=p_cache_list_near;
    			p_cache_list_near->pre=p;
    		}
    
    		p=new CacheNode();//(CacheNode *)malloc(sizeof(CacheNode));
    
    		if(p==NULL)
    			return ;
    
    		addToFront(p);
    		p->key=key;  
    		p->value=value;  
    
    		cache_real_size_++;
    		mapNodes.insert(pair<int,CacheNode>(key,*p));
    	}
    
    
    };

  • 0
    R

    First of all, the way you insert is in the wrong order. The recently used node should always inserted back to the end of the list. Second, when i debug on Xcode, it does have an runtime error about freeing a node that was not allocated


Log in to reply
 

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