C++ Solution - Runtime error, but runs with the same test cases in VS2013!


  • 0
    L

    I use a linked list + hashmap implementation. This code works for me in VS2013 when I have some test code, but seems to get a runtime error on leetcode. If anyone could enlighten me, that would be fantastic.

    struct Node {
    	Node * next;
    	Node * prev;
    	int key;
    	int data;
    };
    
    class LRUCache{
    public:
    	Node * head;
    	Node * tail;
    	int currSize;
    	int cap;
    	unordered_map<int, Node*> nodeTrack;
    
    	LRUCache(int capacity) {
    		currSize = 0;
    		cap = capacity;
    	}
    
    	int get(int key) {
    		if (nodeTrack.find(key) == nodeTrack.end()){
    			return -1;
    		}
    		else {
    			nodeTrack[key]->next = head;
    			Node * temp = nodeTrack[key];
    			if (head) {
    				head->prev = nodeTrack[key];
    			}
    			if (temp->prev) {
    				temp->prev->next = temp->next;
    			}
    			if (temp->next) {
    				temp->next->prev = temp->prev;
    			}
    			if (temp == tail && temp->prev) {
    				tail = temp->prev;
    			} else if (temp == tail) {
    				tail = NULL;
    			}
    			head = nodeTrack[key];
    			return nodeTrack[key]->data;
    		}
    
    	}
    
    	void set(int key, int value) {
    		if (nodeTrack.find(key) == nodeTrack.end()) {
    			Node * new1 = new Node;
    			new1->key = key;
    			new1->data = value;
    			nodeTrack[key] = new1;
    			if (head) {
    				head->prev = new1;
    				new1->next = head;
    				new1->prev = NULL;
    				head = new1;
    			}
    			else {
    				head = new1;
    				new1->next = NULL;
    				new1->prev = NULL;
    				tail = new1;
    			}
    			currSize++;
    			if (currSize > cap) {
    				nodeTrack.erase(tail->key);
    				Node * temp = tail;
    				tail = tail->prev;
    				tail->next = NULL;
    				free(temp);
    				currSize--;
    			}
    		}
    		else {
    			Node * toNode = nodeTrack[key];
    			toNode->data = value;
    			if (toNode->prev) {
    				toNode->prev->next = toNode->next;
    			}
    			if (toNode->next) {
    				toNode->next->prev = toNode->prev;
    			}
    			if (toNode == tail && toNode->prev) {
    				tail = toNode->prev;
    			} else if (toNode == tail) {
    				tail = NULL;
    			}
    			toNode->next = head;
    			if (head) {
    				head->prev = toNode;
    			}
    			head = toNode;
    		}
    	}
    };
    

  • 0

    @limenuke You should init head and tail to NULL.

    Or the bellowing branch would always been true (which cause logic error):

    void set(int key, int value) {
    	if (nodeTrack.find(key) == nodeTrack.end()) {
    		Node * new1 = new Node;
    		new1->key = key;
    		new1->data = value;
    		nodeTrack[key] = new1;
    		if (head) { // here always TRUE!
                        
    

    I use a test case and encountered Segment Fault:

        LRUCache s = LRUCache::LRUCache(5);
        for(int i = 0; i < 10000; i++) {
            cout << "put " << i << endl;
            s.set(i % 100, i);
        }
        return 0;
    

    After put 5 into cache it crashed.


Log in to reply
 

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