濮阳微信网站建设,服务品牌策划方案,网络服务提供者不得为未满多少岁开展工作,wordpress动漫网站LFU 缓存【LC460】 请你为 最不经常使用#xff08;LFU#xff09;缓存算法设计并实现数据结构。 实现 LFUCache 类#xff1a; LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象int get(int key) - 如果键 key 存在于缓存中#xff0c;则获取键的值#x…LFU 缓存【LC460】 请你为 最不经常使用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) 的平均时间复杂度运行。 错误答案 class LFUCache {// 注意PriorityQueue要插入(删除)数据顺序会发生改变如果仅仅是修改已经稳定队列的值或内容而不进行插入或者删除那么这个顺序是不会变的。// 使用Node存储每个key对应的value以及该key的操作次数、最近操作时间// 小顶堆存储每个元素 以使用次数及最近使用时间降序排序int capacity;PriorityQueueNode pq;MapInteger, Node map;int time;public LFUCache(int capacity) {this.capacity capacity;this.pq new PriorityQueue((o1, o2) - o1.freq o2.freq ? o1.time - o2.time : o1.freq - o2.freq);this.map new HashMap();this.time 0;}public int get(int key) {if (!map.containsKey(key)) return -1;Node node map.get(key);node.freq 1;node.time time;return node.val;}public void put(int key, int value) {if (map.containsKey(key)){Node node map.get(key);node.val value;node.freq 1;node.time time;}else{Node node new Node(key, value, time, 1);if (pq.size() capacity){Node node1 pq.poll();map.remove(node1.key);}pq.add(node);map.put(key, node);}}
}
class Node{int key;int val;int time;int freq;public Node(){this.freq 0;}public Node(int key, int val, int time, int freq){this.key key;this.val val;this.time time;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);*/思路 LFU和LRU不同之处 LRU移除元素时移除最近最久未使用的元素LFU移除元素时移除使用频率最少的最近最久未使用的元素 因此LFU实现可以仿照LRU使用哈希表记录每个频率下的节点相同频率下的各个节点以双向链表的形式组织 每次移除元素时移除频率最小的最久未使用的元素每操作一次元素需要修改节点频率至相应链表链表的首部存放最新操作的元素为了快速找到某个节点在链表中的位置可以使用哈希表存储每个key对应的节点为了快速找到最小频率维护一个int变量记录最小频率 实现 class LFUCache {private static class Node {int key, value, freq 1; // 新书只读了一次Node prev, next;Node(int key, int value) {this.key key;this.value value;}}private final int capacity;private final MapInteger, Node keyToNode new HashMap();private final MapInteger, Node freqToDummy new HashMap();private int minFreq;public LFUCache(int capacity) {this.capacity capacity;}public int get(int key) {Node node getNode(key);return node ! null ? node.value : -1;}public void put(int key, int value) {Node node getNode(key);if (node ! null) { // 有这本书node.value value; // 更新 valuereturn;}if (keyToNode.size() capacity) { // 书太多了Node dummy freqToDummy.get(minFreq);Node backNode dummy.prev; // 最左边那摞书的最下面的书keyToNode.remove(backNode.key);remove(backNode); // 移除if (dummy.prev dummy) { // 这摞书是空的freqToDummy.remove(minFreq); // 移除空链表}}node new Node(key, value); // 新书keyToNode.put(key, node);pushFront(1, node); // 放在「看过 1 次」的最上面minFreq 1;}private Node getNode(int key) {if (!keyToNode.containsKey(key)) { // 没有这本书return null;}Node node keyToNode.get(key); // 有这本书remove(node); // 把这本书抽出来Node dummy freqToDummy.get(node.freq);if (dummy.prev dummy) { // 抽出来后这摞书是空的freqToDummy.remove(node.freq); // 移除空链表if (minFreq node.freq) { // 这摞书是最左边的minFreq;}}pushFront(node.freq, node); // 放在右边这摞书的最上面return node;}// 创建一个新的双向链表private Node newList() {Node dummy new Node(0, 0); // 哨兵节点dummy.prev dummy;dummy.next dummy;return dummy;}// 在链表头添加一个节点把一本书放在最上面private void pushFront(int freq, Node x) {Node dummy freqToDummy.computeIfAbsent(freq, k - newList());x.prev dummy;x.next dummy.next;x.prev.next x;x.next.prev x;}// 删除一个节点抽出一本书private void remove(Node x) {x.prev.next x.next;x.next.prev x.prev;}
}
