​LeetCode刷题实战460:LFU 缓存

算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 LFU 缓存,我们先来看题面:
https://leetcode-cn.com/problems/lfu-cache/
 
​LeetCode刷题实战460:LFU 缓存
​LeetCode刷题实战460:LFU 缓存

示例

输入:
[“LFUCache”, “put”, “put”, “get”, “put”, “get”, “get”, “put”, “get”, “get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出:
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释:
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序(最左边的元素是最近的)
LFUCache lFUCache = new LFUCache(2);
lFUCache.put(1, 1); // cache=[1,_], cnt(1)=1
lFUCache.put(2, 2); // cache=[2,1], cnt(2)=1, cnt(1)=1
lFUCache.get(1); // 返回 1
// cache=[1,2], cnt(2)=1, cnt(1)=2
lFUCache.put(3, 3); // 去除键 2 ,因为 cnt(2)=1 ,使用计数最小
// cache=[3,1], cnt(3)=1, cnt(1)=2
lFUCache.get(2); // 返回 -1(未找到)
lFUCache.get(3); // 返回 3
// cache=[3,1], cnt(3)=2, cnt(1)=2
lFUCache.put(4, 4); // 去除键 1 ,1 和 3 的 cnt 相同,但 1 最久未使用
// cache=[4,3], cnt(4)=1, cnt(3)=2
lFUCache.get(1); // 返回 -1(未找到)
lFUCache.get(3); // 返回 3
// cache=[3,4], cnt(4)=1, cnt(3)=3
lFUCache.get(4); // 返回 4
// cache=[3,4], cnt(4)=2, cnt(3)=3


 

解题

https://blog.csdn.net/weixin_44560620/article/details/120254882
思路大致如下:将键值对和使用频率封装成为node对象,使用map记录key和node的映射关系。对于每个使用频率,维护一个linkedSet记录使用的顺序,就可以做到每次删除使用频率最少的并且最近未使用的
 

class LFUCache {

Map<Integer,Node> map=new HashMap();
int size,cap;
int min=1;
Map<Integer,LinkedHashSet<Node>> freq=new HashMap<>();
public LFUCache(int capacity) {
size=0;
cap=capacity;

}

public int get(int key) {
if(!map.containsKey(key))
return -1;
Node node = map.get(key);
freq.get(node.cnt).remove(node);
if(node.cnt==min&&freq.get(min).isEmpty())
min=node.cnt+1;
node.cnt++;
if(!freq.containsKey(node.cnt))
freq.put(node.cnt,new LinkedHashSet<>());
freq.get(node.cnt).add(node);
return node.value;
}

public void put(int key, int value) {
if(cap==0) return;
if(map.containsKey(key))
{
Node node = map.get(key);
freq.get(node.cnt).remove(node);
if(node.cnt==min&&freq.get(min).isEmpty())
min=node.cnt+1;
node.cnt++;
node.value=value;
}else{
if(size==cap)
{
LinkedHashSet<Node> set = freq.get(min);
Node de = set.iterator().next();
set.remove(de);
map.remove(de.key);
size–;
}
Node node=new Node(key,value);
map.put(key,node);
min=1;
size++;
}
Node cur=map.get(key);
if(!freq.containsKey(cur.cnt))
freq.put(cur.cnt,new LinkedHashSet<>());
freq.get(cur.cnt).add(cur);

}
class Node{
int cnt,key,value;
Node(int k,int v)
{
key=k;
value=v;
cnt=1;
}

}
}


好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
上期推文:

LeetCode1-440题汇总,希望对你有点帮助!

LeetCode刷题实战441:排列硬币

LeetCode刷题实战442:数组中重复的数据

LeetCode刷题实战443:压缩字符串

LeetCode刷题实战444:序列重建

LeetCode刷题实战445:两数相加 II

LeetCode刷题实战446:等差数列划分 II – 子序列

LeetCode刷题实战447:回旋镖的数量

LeetCode刷题实战448:找到所有数组中消失的数字

LeetCode刷题实战449:序列化和反序列化二叉搜索树

LeetCode刷题实战450:删除二叉搜索树中的节点

LeetCode刷题实战451:根据字符出现频率排序

LeetCode刷题实战452:用最少数量的箭引爆气球

LeetCode刷题实战453:最小操作次数使数组元素相等

LeetCode刷题实战454:四数相加 II

LeetCode刷题实战455:分发饼干

LeetCode刷题实战456:132 模式

LeetCode刷题实战457:环形数组是否存在循环

LeetCode刷题实战458:可怜的小猪

LeetCode刷题实战459:重复的子字符串

​LeetCode刷题实战460:LFU 缓存

 

本篇文章来源于微信公众号:程序IT圈

原创文章,作者:栈长,如若转载,请注明出处:https://www.cxyquan.com/16467.html

发表评论

登录后才能评论

联系我们

400-800-8888

在线咨询:点击这里给我发消息

邮件:admin@example.com

工作时间:周一至周五,9:30-18:30,节假日休息