We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. C++
  3. Classes
  4. Abstract Classes - Polymorphism
  5. Discussions

Abstract Classes - Polymorphism

  • mlyymlyy
     + 3 comments

    Attention! The test case on hackerrank is poorly designed.It may not cover all the situation that a LRU may occur.A personal suggestion is, due to that hackerrank is using the exact same API as leetcode, you can cut and paste all the code,except the main function, to leetcode to see what's going on. My AC answer:

    class LRUCache:public Cache{
public:
    LRUCache(int i):Cache(){
        cp = i;
        head = nullptr;
        tail = nullptr;
    }
    void set(int k,int v){
        if(cp <= 0)return;
        if(mp.size() == 0){
            Node *node = new Node(k,v);
            InsertIntoHead(node);
            mp.insert(make_pair(k,node));
        }
        else if(mp.find(k)!=mp.end()){
            auto it = mp[k];
            it->value = v;
            InsertIntoHead(it);
        }
        else if(mp.size() < cp){
            Node *node = new Node(k,v);
            InsertIntoHead(node);
            mp.insert(make_pair(k,node));
        }
        else{
            auto it = tail;
            mp.erase(it->key);
            LinkedListDelete(it);
            delete it;
            Node *node = new Node(k,v);
            InsertIntoHead(node);
            mp.insert(make_pair(k,node));
        }
    }
    int get(int k){
        if(mp.find(k) != mp.end()){
            InsertIntoHead(mp[k]);
            return mp[k]->value;
        }
        else return -1;
    }
private:
    void LinkedListDelete(Node* node){
        if(!node)return;
		if(node-> prev)
		{
			node->prev->next = node->next;
		}
		if(node->next)
		{
			node->next->prev = node->prev;
		}
		if(node == head)
		{
			head = node->next;
		}
		if(node == tail)
		{
			tail = node->prev;
		}
    }
    void InsertIntoHead(Node* node)
	{
		if(!node)return;
		LinkedListDelete(node);
		if(head)
			head->prev = node;
		node->next = head;
		node->prev = nullptr;
		if(!tail) tail = node;
		head = node;
	}
};