TLE, but I tested my code in local machine and get less than 300ms, while another AC code get more than 1000ms


  • 0
    E

    how could it be...
    my code:

    struct Node{
    public:
    int val;
    Node * next;
    Node(int v) :val(v), next(NULL) {}
    };
    
    class LRUCache{
    private:
    Node *khead;
    Node *vhead;
    int capa, count;
    public:
    LRUCache(int capacity) {
    	khead = NULL;
    	vhead = NULL;
    	capa = capacity;
    	count = 0;
    }
    
    int get(int key, bool isSet = false) {
    	if (count == 0)return -1;
    	if (khead->val == key)return vhead->val;
    	if (count == 1)return -1;
    	int i = 1;
    	Node *p = khead, *tmp = p;
    	while (i < count)
    	{
    		if (p->next->val == key){
    			break;
    		}
    		i++;
    		tmp = p;
    		p = p->next;
    	}
    	if (i == count){
    		if (isSet && count == capa){
    			p->next = khead;
    			khead = p;
    			tmp->next = NULL;
    
    			p = vhead;
    			while (p->next){
    				tmp = p;
    				p = p->next;
    			}
    			p->next = vhead;
    			vhead = p;
    			tmp->next = NULL;
    		}
    		return -1;//not found
    	}
    
    	//adjust key list
    	tmp = p->next->next;
    	p->next->next = khead;
    	khead = p->next;
    	p->next = tmp;
    	
    	//adjust value list
    	Node *v = vhead;
    	int j = 0;
    	while (j++ < i - 1)v = v->next;
    	tmp = v->next;
    	v->next = tmp->next;
    	tmp->next = vhead;
    	vhead = tmp;
    
    	return vhead->val;
    }
    
    void set(int key, int value) {
    	if (capa == 0)return;
    	if (count == 0)
    	{
    		khead = new Node(key);
    		vhead = new Node(value);
    		count++;
    		return;
    	}
    	
    	int res = get(key, true);
    	if (count < capa && res == -1){
    		Node *k = new Node(key);
    		Node *v = new Node(value);
    		k->next = khead;
    		v->next = vhead;
    		khead = k;
    		vhead = v;
    		count++;
    		return;
    	}
    
    	khead->val = key;
    	vhead->val = value;
    	return;
    	
    }
    };

Log in to reply
 

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