A 128 ms C++ solution.


  • 0

    ・Use list to sort nodes, the first node is the most rarely used node. If a node is get() or set(), move it to the end of list.

    ・Use map to pair key and node's address to find the node directly.

    ・To help change the order of list, a double linked list is needed.

    class LRUCache{
    private:
    	struct node
    	{
    		int key;
    		int val;
    		node *pre, *fol;
    		node(int a, int b)
    		{
    			key = a;
    			val = b;
    			pre = fol = 0;
    		}
    		~node()
    		{}
    	};
    	map<int, node*> mp;
    	node* root;
    	node* end;
    	int sz;
    	void changeorder(int key)
    	{
    		node *t = mp[key];
    		if (t != end)
    		{
    			if (t == root)
    			{
    				root = root->fol;
    				root->pre = 0;
    			}
    			else
    			{
    				t->pre->fol = t->fol;
    				t->fol->pre = t->pre;
    			}
    			end->fol = t;
    			t->pre = end;
    			t->fol = 0;
    			end = t;
    		}
    		return;
    	}
    public:
    	LRUCache(int capacity) 
    	{
    		sz = capacity;
    		root = end = 0;
    	}
    	int get(int key) 
    	{
    		if (!root || 0 == mp.count(key))
    			return -1;
    		changeorder(key);
    		node *t = mp[key];
    		return t->val;
    	}
    
    	void set(int key, int value) 
    	{
    		node *t;
    		if (mp.count(key) > 0)
    		{
    			t = mp[key];
    			changeorder(key);
    			t->val = value;
    		}
    		else
    		{
    			if (!root || mp.size() < sz)
    			{
    				t = new node(key, value);
    				if (!root)
    					root = end = t;
    				else
    				{
    					end->fol = t;
    					t->pre = end;
    					end = t;
    				}
    				mp[key] = t;
    			}
    			else
    			{
    				t = root;
    				changeorder(t->key); 
    				mp.erase(t->key);
    				t->key = key;
    				t->val = value;
    				mp[key] = t;
    			}
    		}
    		return;
    	}
    };

Log in to reply
 

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