leetcode 面试150之 156.LUR 缓存

请你设计并实现一个满足  LRU (最近最少使用) 缓存 约束的数据结构。

实现 LRUCache 类：

• LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

题目重点：O(1)实现查找和删除

O(1)查找我们可以通过unordered_map底层哈希表来实现
这里我们如果缓存满了还得删除最久未使用关键字 ，所以我们得使用一个O(1)维护的“使用队列”，数组我们无法实现O(1)删除，而双向链表能实现O(1)删除，但是无法实现O(1)查询

所以我们这里用到了unordered_map<int,listnode*>映射为listnode*，通过map去实现O(1)查询
而listnode*双向链表实现O(1)插入和删除

起初我并未想到用双向链表而是用deque去维护“使用队列”，后者在维护队列无法做到O(1),包超时的

上代码：

class LRUCache {
public:
	struct listnode{
		int key;
		int val;
		listnode* pre;
		listnode* next;
		listnode(int k,int v):key(k),val(v),pre(nullptr),next(nullptr){}
	};
	int max_;                          //最大空间
	listnode* head;                    //头哨兵节点
	listnode* tail;                    //尾哨兵节点
	unordered_map<int,listnode*> dp;   //精华

    //初始化    
    LRUCache(int capacity) 
    {
      max_=capacity;
      head=new listnode(0,0);
	  tail=new listnode(0,0);
	  head->next=tail;
	  tail->pre=head;
    }

    //双向链表头插法 将处理的node节点 使用优先级提高
    void addnode(listnode* node)
    {
        node->next=head->next;
        head->next->pre=node;
        head->next=node;
        node->pre=head;
	}

    //断开node节点 并未delete  
	void remove_node(listnode* node)
	{
		node->pre->next=node->next;
		node->next->pre=node->pre;
	}


    //查询数据
    int get(int key) 
    {
        if(dp.count(key))          //查询成功 提高该节点的“使用队列”优先级
        {
        	remove_node(dp[key]);
        	addnode(dp[key]);
        	return dp[key]->val;
		}
		else return -1;
    }

    //插入数据
    void put(int key, int value) 
    {
        if(dp.count(key))
        {
        	dp[key]->val=value;    //已经存在   更新val后，取走节点后插入头  提高优先级
        	remove_node(dp[key]);
        	addnode(dp[key]);
		}
		
        //key不存在
        else
		{
			if(max_==dp.size())          //空间已满  删除优先级低节点 也就是 tail->pre
            {
				listnode* temp=tail->pre;
				remove_node(temp);
				dp.erase(temp->key);
				delete temp;               //释放内存
			}

            //无论空间是否够 都需要插入这个key节点
			listnode* node=new listnode(key,value); 
			addnode(node);
			dp.insert({key,node});
		}
    }
};

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache* obj = new LRUCache(capacity);
 * int param_1 = obj->get(key);
 * obj->put(key,value);
 */