建设网站网站名,网络舆情监测专业,wordpress 网站投票,开通自媒体账号的步骤设计LRU缓存结构_牛客题霸_牛客网
描述
设计LRU(最近最少使用)缓存结构#xff0c;该结构在构造时确定大小#xff0c;假设大小为 k #xff0c;并有如下两个功能
1. set(key, value)#xff1a;将记录(key, value)插入该结构
2. get(key)#xff1a;返回key对应的val…设计LRU缓存结构_牛客题霸_牛客网
描述
设计LRU(最近最少使用)缓存结构该结构在构造时确定大小假设大小为 k 并有如下两个功能
1. set(key, value)将记录(key, value)插入该结构
2. get(key)返回key对应的value值 提示:
1.某个key的set或get操作一旦发生认为这个key的记录成了最常使用的然后都会刷新缓存。
2.当缓存的大小超过k时移除最不经常使用的记录。
3.输入一个二维数组与k二维数组每一维有2个或者3个数字第1个数字为opt第23个数字为keyvalue
若opt1接下来两个整数key, value表示set(key, value) 若opt2接下来一个整数key表示get(key)若key未出现过或已被移除则返回-1 对于每个opt2输出一个答案
4.为了方便区分缓存里key与value下面说明的缓存里key用号包裹 要求set和get操作复杂度均为 O(1)
示例1
输入
[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3
复制返回值
[1,-1]
复制说明
[1,1,1]第一个1表示opt1要set(1,1)即将(1,1)插入缓存缓存是{11}
[1,2,2]第一个1表示opt1要set(2,2)即将(2,2)插入缓存缓存是{11,22}
[1,3,2]第一个1表示opt1要set(3,2)即将(3,2)插入缓存缓存是{11,22,32}
[2,1]第一个2表示opt2要get(1)返回是[1]因为get(1)操作缓存更新缓存是{22,32,11}
[1,4,4]第一个1表示opt1要set(4,4)即将(4,4)插入缓存但是缓存已经达到最大容量3移除最不经常使用的{22}插入{44}缓存是{32,11,44}
[2,2]第一个2表示opt2要get(2)查找不到返回是[1,-1]
示例2
输入
[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2
复制返回值
[1,-1,-1,3,4]复制
备注
1≤K≤N≤105
−2×109≤x,y≤2×109
解题报告
首先设计数据结构使用hash表链表实现。
首先用链表来实现页面缓存。用hash表来快速定位每个key对应的value是什么。方便进行get操作。
AC代码
优化后较为简单的代码
即我们调用层代码十分清晰。具体实现层实现了链表层面的insert和remove顺便更新下key就可以了。
注意点1remove函数里面的k_pos.erase操作要放到if内不然已经return了就不会执行erase了。
class Solution {
public:/*** lru design* param operators int整型vectorvector the ops* param k int整型 the k* return int整型vector*/struct Node {int key, val;Node* pre, *nxt;Node(int k, int v):key(k), val(v){}};int K;unordered_mapint, Node* k_pos;Node* head, *tail;void insert(int key, int value) {Node* newNode new Node(key, value);newNode-nxt head-nxt;newNode-pre head;head-nxt-pre newNode;head-nxt newNode;k_pos[key] newNode;}bool remove(int key) {if(k_pos.find(key) ! k_pos.end()) {Node* tar k_pos[key];tar-pre-nxt tar-nxt;tar-nxt-pre tar-pre;delete tar;k_pos.erase(key);return true;}return false;}void set(int key, int value) {remove(key);if(k_pos.size() K) {remove(tail-pre-key);}insert(key, value);}int get(int key) {if(k_pos.find(key) ! k_pos.end()) {int ret k_pos[key]-val;remove(key);insert(key, ret);return ret;}return -1;}vectorint LRU(vectorvectorint operators, int k) {// write code hereK k;head new Node(-1, -1);tail new Node(-1, -1);head-nxt tail;tail-pre head;vectorint ans;for(int i 0; ioperators.size(); i) {if(operators[i][0] 1) {set(operators[i][1], operators[i][2]);} else {ans.push_back(get(operators[i][1]));}}return ans;}
}; 重构前较为复杂的代码
class Solution {
public:/*** lru design* param operators int整型vectorvector the ops* param k int整型 the k* return int整型vector*/struct Node {int key, val;Node* pre, *nxt;Node(int k, int v):key(k), val(v){}};int K;unordered_mapint, Node* k_pos;Node* head, *tail;bool remove(int key) {if(k_pos.find(key) ! k_pos.end()) {Node* tar k_pos[key];tar-pre-nxt tar-nxt;tar-nxt-pre tar-pre;delete tar;k_pos.erase(key);return true;}return false;}void set(int key, int value) {remove(key);if(k_pos.size() K) {remove(tail-pre-key);}Node* newNode new Node(key, value);newNode-nxt head-nxt;newNode-pre head;head-nxt-pre newNode;head-nxt newNode;k_pos[key] newNode;}int get(int key) {if(k_pos.find(key) ! k_pos.end()) {int ret k_pos[key]-val;remove(key);Node* newNode new Node(key, ret);newNode-nxt head-nxt;newNode-pre head;head-nxt-pre newNode;head-nxt newNode;k_pos[key] newNode;return ret;}return -1;}vectorint LRU(vectorvectorint operators, int k) {// write code hereK k;head new Node(-1, -1);tail new Node(-1, -1);head-nxt tail;tail-pre head;vectorint ans;for(int i 0; ioperators.size(); i) {if(operators[i][0] 1) {set(operators[i][1], operators[i][2]);} else {ans.push_back(get(operators[i][1]));}}return ans;}
};
