1.简述: 描述 一个缓存结构需要实现如下功能。 set(key, value):将记录(key, value)插入该结构 get(key):返回key对应的value值 但是缓存结构中最多放K条记录,如果新的第K+1条记录要加入,就
1.简述:
描述一个缓存结构需要实现如下功能。
set(key, value):将记录(key, value)插入该结构
get(key):返回key对应的value值
但是缓存结构中最多放K条记录,如果新的第K+1条记录要加入,就需要根据策略删掉一条记录,然后才能把新记录加入。这个策略为:在缓存结构的K条记录中,哪一个key从进入缓存结构的时刻开始,被调用set或者get的次数最少,就删掉这个key的记录;
如果调用次数最少的key有多个,上次调用发生最早的key被删除
这就是LFU缓存替换算法。实现这个结构,K作为参数给出
数据范围:,
要求:get和set的时间复杂度都是 ,空间复杂度是
若opt=1,接下来两个整数x, y,表示set(x, y)若opt=2,接下来一个整数x,表示get(x),若x未出现过或已被移除,则返回-1
对于每个操作2,返回一个答案
示例1输入:
[[1,1,1],[1,2,2],[1,3,2],[1,2,4],[1,3,5],[2,2],[1,4,4],[2,1]],3返回值:
[4,-1]说明:
在执行"1 4 4"后,"1 1 1"被删除。因此第二次询问的答案为-12.代码实现:
import java.util.*;public class Solution {
//设置节点结构
static class Node{
int freq;
int key;
int val;
//初始化
public Node(int freq, int key, int val) {
this.freq = freq;
this.key = key;
this.val = val;
}
}
//频率到双向链表的哈希表
private Map<Integer, LinkedList<Node> > freq_mp = new HashMap<>();
//key到节点的哈希表
private Map<Integer, Node> mp = new HashMap<>();
//记录缓存剩余容量
private int size = 0;
//记录当前最小频次
private int min_freq = 0;
public int[] LFU (int[][] operators, int k) {
//构建初始化连接
//链表剩余大小
this.size = k;
//获取操作数
int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
int[] res = new int[len];
//遍历所有操作
for(int i = 0, j = 0; i < operators.length; i++){
if(operators[i][0] == 1)
//set操作
set(operators[i][1], operators[i][2]);
else
//get操作
res[j++] = get(operators[i][1]);
}
return res;
}
//调用函数时更新频率或者val值
private void update(Node node, int key, int value) {
//找到频率
int freq = node.freq;
//原频率中删除该节点
freq_mp.get(freq).remove(node);
//哈希表中该频率已无节点,直接删除
if(freq_mp.get(freq).isEmpty()){
freq_mp.remove(freq);
//若当前频率为最小,最小频率加1
if(min_freq == freq)
min_freq++;
}
if(!freq_mp.containsKey(freq + 1))
freq_mp.put(freq + 1, new LinkedList<Node>());
//插入频率加一的双向链表表头,链表中对应:freq key value
freq_mp.get(freq + 1).addFirst(new Node(freq + 1, key, value));
mp.put(key, freq_mp.get(freq + 1).getFirst());
}
//set操作函数
private void set(int key, int value) {
//在哈希表中找到key值
if(mp.containsKey(key))
//若是哈希表中有,则更新值与频率
update(mp.get(key), key, value);
else{
//哈希表中没有,即链表中没有
if(size == 0){
//满容量取频率最低且最早的删掉
int oldkey = freq_mp.get(min_freq).getLast().key;
//频率哈希表的链表中删除
freq_mp.get(min_freq).removeLast();
if(freq_mp.get(min_freq).isEmpty())
freq_mp.remove(min_freq);
//链表哈希表中删除
mp.remove(oldkey);
}
//若有空闲则直接加入,容量减1
else
size--;
//最小频率置为1
min_freq = 1;
//在频率为1的双向链表表头插入该键
if(!freq_mp.containsKey(1))
freq_mp.put(1, new LinkedList<Node>());
freq_mp.get(1).addFirst(new Node(1, key, value));
//哈希表key值指向链表中该位置
mp.put(key, freq_mp.get(1).getFirst());
}
}
//get操作函数
private int get(int key) {
int res = -1;
//查找哈希表
if(mp.containsKey(key)){
Node node = mp.get(key);
//根据哈希表直接获取值
res = node.val;
//更新频率
update(node, key, res);
}
return res;
}
}