牛客NC93-设计LRU缓存结构

た入场券 2022-12-02 15:24 110阅读 0赞

### 题意 ###

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能：

*  set(key, value)：将记录(key, value)插入该结构
 *  get(key)：返回key对应的value值

\[要求\]

1.  set和get方法的时间复杂度为O(1)
2.  某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
3.  当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

若opt=1，接下来两个整数x, y，表示set(x, y)  
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1  
对于每个操作2，输出一个答案

### 思路 ###

> 首先用unordered\_map来记录key-value键值对，由于要进行移动，所以用数组来模拟链表。用一个vector存储key的值，并再用哈希表记录key在数组中的下标。现在针对这两个操作：
> 
> 1.  set(x, y)，先记录一下mp\[x\] = y，然后将x压入数组尾部，并记录一下key值对应数组的下标。如果元素大于k，那么就将头部元素清空，L指向数组中第一个合法元素的下标。  
>     2.get(x)，先判断一下-1的情况，然后找到数组中key的位置，然后将其压入尾部表示最近使用，再将原来的位置清空（值<=2e9，所以我将其设置成2e9+1表示非法）

#include<unordered_map>
    class Solution { 
    public:
    	/** * lru design * @param operators int整型vector<vector<>> the ops * @param k int整型 the k * @return int整型vector */
    	unordered_map<int, int> mp, pos; //mp记录value, pos记录key在数组中的下标
    	vector<int> v, res;
    	vector<int> LRU(vector<vector<int> >& operators, int k) { 
    		// write code here
    		v.push_back(0);
    		int L = 1, R = 0, flag = 0;
    		for(int i = 0; i < operators.size(); ++i)
    		{ 
    			if(operators[i][0] == 1) //set
    			{ 
    				mp[operators[i][1]] = operators[i][2];
    				v.push_back(operators[i][1]);
    				++R;
    				pos[operators[i][1]] = R;
    				++flag;
    				if(flag > k) //要删除头部元素
    				{ 
    					mp[v[L]] = 2e9 + 1; //清空
    					++L;
    					while(L <= R && v[L] == 2e9 + 1) ++L;
    				}
    			}
    			else //get
    			{ 
    				if(L > R || !mp.count(operators[i][1]) || mp[operators[i][1]] == 2e9 + 1)
    				{ 
    					res.push_back(-1);
    					continue;
    				}
    				res.push_back(mp[operators[i][1]]);
    				int id = pos[operators[i][1]];
    				v.push_back(v[id]);
    				++R;
    				v[id] = 2e9 + 1;
    				if(L == id) //L指向数组中第一个合法元素的下标
    				{ 
    					while(L <= R && v[L] == 2e9 + 1) ++L;
    				}
    			}
    		}
    		return res;
    	}
    };

当然用list来做更加方便

#include<unordered_map>
    class Solution { 
    public:
    	/** * lru design * @param operators int整型vector<vector<>> the ops * @param k int整型 the k * @return int整型vector */
    	unordered_map<int, int> mp;
    	list<int> lt;
    	vector<int> LRU(vector<vector<int> >& operators, int k) 
    	{ 
    		// write code here
    		vector<int> res;
    		for(auto v : operators)
    		{ 
    			if(v[0] == 1) //set
    			{ 
    				mp[v[1]] = v[2];
    				lt.push_back(v[1]);
    				if(lt.size() > k)
    				{ 
    					mp.erase(lt.front());
    					lt.erase(lt.begin());
    				}
    			}
    			else //get
    			{ 
    				if(!mp.count(v[1]))
    				{ 
    					res.push_back(-1);
    					continue;
    				}
    				res.push_back(mp[v[1]]);
    				lt.remove(v[1]); //删除key值
    				lt.push_back(v[1]);
    			}
    		}
    		return res;
    	}
    };