东莞网站建设(信科网络),网站域名实名认证官网,烟台网站建设找三硕科技,网站营销的定义请你为 最不经常使用#xff08;LFU#xff09;缓存算法设计并实现数据结构。
实现 LFUCache 类#xff1a;
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象int get(int key) - 如果键 key 存在于缓存中#xff0c;则获取键的值#xff0c;否则返回 -1…
请你为 最不经常使用LFU缓存算法设计并实现数据结构。
实现 LFUCache 类
LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象int get(int key) - 如果键 key 存在于缓存中则获取键的值否则返回 -1 。void put(int key, int value) - 如果键 key 已存在则变更其值如果键不存在请插入键值对。当缓存达到其容量 capacity 时则应该在插入新项之前移除最不经常使用的项。在此问题中当存在平局即两个或更多个键具有相同使用频率时应该去除 最久未使用 的键。
为了确定最不常使用的键可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作使用计数器的值将会递增。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例
输入
[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 lfu new LFUCache(2);
lfu.put(1, 1); // cache[1,_], cnt(1)1
lfu.put(2, 2); // cache[2,1], cnt(2)1, cnt(1)1
lfu.get(1); // 返回 1// cache[1,2], cnt(2)1, cnt(1)2
lfu.put(3, 3); // 去除键 2 因为 cnt(2)1 使用计数最小// cache[3,1], cnt(3)1, cnt(1)2
lfu.get(2); // 返回 -1未找到
lfu.get(3); // 返回 3// cache[3,1], cnt(3)2, cnt(1)2
lfu.put(4, 4); // 去除键 1 1 和 3 的 cnt 相同但 1 最久未使用// cache[4,3], cnt(4)1, cnt(3)2
lfu.get(1); // 返回 -1未找到
lfu.get(3); // 返回 3// cache[3,4], cnt(4)1, cnt(3)3
lfu.get(4); // 返回 4// cache[3,4], cnt(4)2, cnt(3)3 提示
1 capacity 1040 key 1050 value 109最多调用 2 * 105 次 get 和 put 方法 其中 cnt 表示缓存使用的频率time 表示缓存的使用时间key 和 value 表示缓存的键值。
题解比较直观的想法就是我们用哈希表 key_table 以键 key 为索引存储缓存建立一个平衡二叉树 S 来保持缓存根据 (cnttime) 双关键字。还有一道类似的题LRU:146. LRU 缓存机制-CSDN博客
code:
class LFUCache {// 缓存容量时间戳int capacity, time;MapInteger, Node key_table;TreeSetNode S;public LFUCache(int capacity) {this.capacity capacity;this.time 0;key_table new HashMapInteger, Node();S new TreeSetNode();}public int get(int key) {if (capacity 0) {return -1;}// 如果哈希表中没有键 key返回 -1if (!key_table.containsKey(key)) {return -1;}// 从哈希表中得到旧的缓存Node cache key_table.get(key);// 从平衡二叉树中删除旧的缓存S.remove(cache);// 将旧缓存更新cache.cnt 1;cache.time time;// 将新缓存重新放入哈希表和平衡二叉树中S.add(cache);key_table.put(key, cache);return cache.value;}public void put(int key, int value) {if (capacity 0) {return;}if (!key_table.containsKey(key)) {// 如果到达缓存容量上限if (key_table.size() capacity) {// 从哈希表和平衡二叉树中删除最近最少使用的缓存key_table.remove(S.first().key);S.remove(S.first());}// 创建新的缓存Node cache new Node(1, time, key, value);// 将新缓存放入哈希表和平衡二叉树中key_table.put(key, cache);S.add(cache);} else {// 这里和 get() 函数类似Node cache key_table.get(key);S.remove(cache);cache.cnt 1;cache.time time;cache.value value;S.add(cache);key_table.put(key, cache);}}
}class Node implements ComparableNode {int cnt, time, key, value;Node(int cnt, int time, int key, int value) {this.cnt cnt;this.time time;this.key key;this.value value;}public boolean equals(Object anObject) {if (this anObject) {return true;}if (anObject instanceof Node) {Node rhs (Node) anObject;return this.cnt rhs.cnt this.time rhs.time;}return false;}public int compareTo(Node rhs) {return cnt rhs.cnt ? time - rhs.time : cnt - rhs.cnt;}public int hashCode() {return cnt * 1000000007 time;}
}
