1. 全栈程序员必看首页

LFU模拟

全栈程序员-站长 • • 未分类 • 阅读 2

LFU模拟DESC 请你为最不经常使用 LFU 缓存算法设计并实现数据结构 实现 LFUCache 类 LFUCache intcapacity 用数据结构的容量 capacity 初始化对象 intget intkey 如果键存在于缓存中 则获取键的值 否则返回 1 voidput intkey intvalue 如果键已存在 则变更其值 如果键不存在 请插入键值对 当缓存达到其容量时 则应该在插入新项之前 使最不经常使用的项无效 在此问

DESC: 

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

 

示例：

 

提示：

 
CODE:
    JAVA:

     

class LFUCache { private int capacity, minFreq; private Map 
   
     keyMap; private Map 
    
      > freqMap; public LFUCache(int capacity) { this.minFreq = 0; this.capacity = capacity; this.keyMap = new HashMap(); this.freqMap = new HashMap(); } public int get(int key) { if (capacity == 0) { return -1; } if (!keyMap.containsKey(key)) { return -1; } else { Node node = keyMap.get(key); LinkedList 
     
       freqList = freqMap.get(node.freq); freqList.remove(node); if (freqList.size() == 0) { if (node.freq == this.minFreq) { this.minFreq += 1; } } node.freq += 1; keyMap.put(key, node); freqList = freqMap.getOrDefault(node.freq, new LinkedList<>()); freqList.offerFirst(node); freqMap.put(node.freq, freqList); return node.val; } } public void put(int key, int value) { if (capacity == 0) { return; } if (keyMap.containsKey(key)) { Node node = keyMap.get(key); LinkedList 
      
        freqList = freqMap.get(node.freq); freqList.remove(node); if (freqList.isEmpty()) { if (node.freq == this.minFreq) { this.minFreq++; } } node.val = value; node.freq += 1; // keyMap.put(key, node); freqList = freqMap.getOrDefault(node.freq, new LinkedList 
       
         ()); freqList.offerFirst(node); freqMap.put(node.freq, freqList); } else { if (keyMap.size() == capacity) { LinkedList 
        
          list = freqMap.get(this.minFreq); Node node = list.pollLast(); keyMap.remove(node.key); if (list.size() == 0) { this.minFreq += 1; } } Node node = new Node(key, value, 1); keyMap.put(key, node); this.minFreq = 1; LinkedList 
         
           list = freqMap.getOrDefault(node.freq, new LinkedList<>()); list.offerFirst(node); freqMap.put(node.freq, list); } } class Node { private int freq, key, val; public Node() {} public Node(int key, int val, int freq) { this.key = key; this.val = val; this.freq = freq; } } } / * Your LFUCache object will be instantiated and called as such: * LFUCache obj = new LFUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */

 

 
    PYTHON:

           

 
NOTES:

      （Java版）

 

版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请联系我们举报，一经查实，本站将立刻删除。

发布者：全栈程序员-站长，转载请注明出处：https://javaforall.net/223265.html原文链接：https://javaforall.net

赞 (0)
0 0

关于作者

全栈程序员-站长的头像

全栈程序员-站长

133.5K 文章
3 粉丝
本网站汇聚当前互联网主流语音，持续更新，欢迎关注公众号“全栈程序员社区”
上一篇 2026年3月17日 下午2:28
下一篇 2026年3月17日 下午2:29


相关推荐

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注

关注全栈程序员社区公众号