郑州市建设厅网站,网络黄页网址,如何自建网站做外贸,黄页网站是什么例题#xff1a; 分析#xff1a; 这道题可以用两个哈希表来实现#xff0c;一个hash表#xff08;kvMap#xff09;用来存储节点#xff0c;另一个hash表#xff08;freqMap#xff09;用来存储双向链表#xff0c;链表的头节点代表最近使用的元素#xff0c;离头节…例题 分析 这道题可以用两个哈希表来实现一个hash表kvMap用来存储节点另一个hash表freqMap用来存储双向链表链表的头节点代表最近使用的元素离头节点越远的节点代表最近最少使用的节点。 注意freqMap 的 key 为节点的使用频次。 下图是freqMap的结构 这是kvMap 它的key没有什么特殊含义value是储存的节点 题目中调用get方法会增加元素的使用次数freq这时在freqMap中需要将该节点转移到对应的位置上比如该节点使用了两次那就把该节点转移到key为2的位置上去
put方法分为两种情况如果要添加的key不存在说明是新元素放到key为1的位置上如果key存在此时是修改操作改变元素的value值对应的频次1同样放到对应的位置上。
淘汰策略要保证两个hash表中的节点数一致。 代码实现
package leetcode;import java.util.HashMap;//设计LFU缓存
public class LFUCacheLeetcode460 {static class LFUCache {static class Node{Node prev;Node next;int key;int value;int freq 1;public Node(){}public Node(int key, int value) {this.key key;this.value value;}}static class DoublyLinkedList{Node head;Node tail;int size;public DoublyLinkedList(){head tail new Node();head.next tail;tail.prev head;}//头部添加 head-1-2-tail 添加3public void addFirst(Node node){Node oldFirst head.next;oldFirst.prev node;head.next node;node.prev head;node.next oldFirst;size;}//指定节点删除 head-1-2-3-tail 删除2public void remove(Node node){Node prev node.prev;Node next node.next;prev.next next;next.prev prev;size--;}//删除最后一个节点public Node removeLast(){Node last tail.prev;remove(last);return last;}//判断双向链表是否为空public boolean isEmpty(){return size 0;}}private HashMapInteger,Node kvMap new HashMap();private HashMapInteger,DoublyLinkedList freqMap new HashMap();private int capacity;private int minFreq 1;public LFUCache(int capacity) {this.capacity capacity;}/** 获取节点 不存在返回 -1* 存在 增加节点的使用频次将其转移到频次1的链表中* 判断旧节点所在的链表是否为空更新最小频次minFreq* */public int get(int key) {if(!kvMap.containsKey(key)){return -1;}Node node kvMap.get(key);//先删除旧节点DoublyLinkedList list freqMap.get(node.freq);list.remove(node);//判断当前链表是否为空为空可能需要更新最小频次if(list.isEmpty() node.freq minFreq){minFreq;}node.freq;//将新节点放入新位置可能该频次对应的链表不存在不存在需要创建freqMap.computeIfAbsent(node.freq, k - new DoublyLinkedList()).addFirst(node);return node.value;}/** 更新* 将节点的value更新增加节点的使用频次将其转移到频次1的链表中* 新增* 检查是否超过容量若超过淘汰minFreq链表的最后节点* 创建新节点放入kvMap并加入频次为 1 的双向链表* */public void put(int key, int value) {if(kvMap.containsKey(key)){ //更新Node node kvMap.get(key);DoublyLinkedList list freqMap.get(node.freq);list.remove(node);if(list.isEmpty() node.freq minFreq){minFreq;}node.freq;freqMap.computeIfAbsent(node.freq, k - new DoublyLinkedList()).addFirst(node);node.value value;}else{ //新增//先判断容量是否已满if(kvMap.size() capacity){//执行淘汰策略Node node freqMap.get(minFreq).removeLast();kvMap.remove(node.key);}Node node new Node(key, value);kvMap.put(key, node);//加入频次为1的双向链表freqMap.computeIfAbsent(1, k - new DoublyLinkedList()).addFirst(node);minFreq 1;}}}public static void main(String[] args) {LFUCache cache new LFUCache(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.get(1)); // 1 freq2cache.put(3, 3);System.out.println(cache.get(2)); // -1System.out.println(cache.get(3)); // 3 freq2cache.put(4, 4);System.out.println(cache.get(1)); // -1System.out.println(cache.get(3)); // 3 freq3System.out.println(cache.get(4)); // 4 freq2}
}
