题解 | #设计LFU缓存结构#
设计LFU缓存结构
http://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1
如何更新minFre是关键,有两种办法更新,第一种是该元素的本来就是位于最少次数的list的唯一元素,则该元素的fre增加之后,minFre也要跟着变,第二种是有新的元素***来了,minFre要变为1,进行最小访问频率的同步。
两个HashMap,一个用来查找,存放<key,Lfu>,另一个用来维护频率,存放<key,LinkedList<Lfu>>
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
class Lfu{
int key,val,frequency;
public Lfu(int key,int val){
this.key=key;
this.val=val;
this.frequency=0;
}
}
int fre=0;
int minFre=1;
Map<Integer,Lfu> valueMap=new HashMap<>();
Map<Integer,LinkedList<Lfu>>freMap=new HashMap<>();
public void updateFre(Lfu lfu){
if(freMap.containsKey(lfu.frequency)){
LinkedList tmp=freMap.get(lfu.frequency);
tmp.remove(lfu);
if(tmp.isEmpty()&&lfu.frequency==minFre){
minFre++;
}
}
lfu.frequency++;
if(lfu.frequency==1){
minFre=1;
}
if(freMap.containsKey(lfu.frequency)){
freMap.get(lfu.frequency).addFirst(lfu);
}
else{
freMap.put(lfu.frequency,new LinkedList<Lfu>());
freMap.get(lfu.frequency).addFirst(lfu);
}
}
public int get(int key){
if(!valueMap.containsKey(key)){
return -1;
}
Lfu tmp=valueMap.get(key);
updateFre(tmp);
return tmp.val;
}
public void put(Lfu lfu,int k){
int key=lfu.key;
int val=lfu.val;
if(valueMap.containsKey(key)){
Lfu tmp=valueMap.get(key);
tmp.val=val;
updateFre(tmp);
}
else{
if(valueMap.size()<k){
;
}
else{
Lfu tmp=freMap.get(minFre).removeLast();
valueMap.remove(tmp.key);
}
valueMap.put(key,lfu);
updateFre(valueMap.get(key));
}
}
public int[] LFU (int[][] operators, int k) {
// write code here
int n=operators.length;
List<Integer> res=new ArrayList<>();
for(int i=0;i<n;i++){
if(operators[i][0]==1){
put(new Lfu(operators[i][1],operators[i][2]),k);
}
else{
res.add(get(operators[i][1]));
}
}
int[]result=new int[res.size()];
for(int i=0;i<res.size();i++){
result[i]=res.get(i);
}
return result;
}
}