题解 | #设计LFU缓存结构#
设计LFU缓存结构
https://www.nowcoder.com/practice/93aacb4a887b46d897b00823f30bfea1
纯Map实现（纯粹是因为链表太长了不想看），在LRU的基础上改的，仅供参考。
/**
* @param {number} capacity
*/
var Solution = function(capacity) {
// write code here
this.max = capacity;
this.map = new Map();//保存数据的map
this.nummap = new Map();//记录次数的map
};
/**
* @param {number} key
* @return {number}
*/
Solution.prototype.get = function(key) {
// write code here
if(!this.map.has(key)) return -1;
else {
let value = this.map.get(key);
let cnt = this.nummap.get(key)+1;
//每访问一次重新加入，方便后续次数相同的情况找到最早访问的
this.nummap.delete(key);
this.nummap.set(key,cnt);
return value;
}
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
Solution.prototype.set = function(key, value) {
// write code here
if(this.map.has(key)){
this.map.set(key,value);
this.nummap.set(key,this.nummap.has(key)?this.nummap.get(key)+1:1);
}
else{
if(this.map.size == this.max){
let keys = Array.from(this.nummap.keys());
let cnt = Infinity,tmp;
//找到次数最小并且访问最早的
for(let item of keys){
if(this.nummap.get(item)<cnt){cnt=this.nummap.get(item);tmp=item;}
}
//同时删掉两个map中该key的数据
this.map.delete(tmp);
this.nummap.delete(tmp);
this.map.set(key,value);
this.nummap.set(key,this.nummap.has(key)?this.nummap.get(key)+1:1);
}else{
this.map.set(key,value);
this.nummap.set(key,this.nummap.has(key)?this.nummap.get(key)+1:1);
}
}
};
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
function LFU( operators , k ) {
// write code here
let obj = new Solution(k);
let res = [];
for(let i=0;i<operators.length;i++){
let op = operators[i];
//进行set
if(op[0]==1){
obj.set(op[1],op[2]);
}
//进行get
else{
res.push(obj.get(op[1]));
}
}
return res;
}
module.exports = {
LFU : LFU
};
