网站建设及维护包括范围,国际俄罗斯乌克兰,医疗营销的网站怎么做,网站备案用户名忘了怎么办LFU算法 Least Frequently Used#xff08;最不频繁使用#xff09; Leetcode有原题#xff0c;之前手写过LRU#xff0c;数据结构还是习惯于用java实现#xff0c;实现是copy的评论题解。 题解注释写的很清楚
大致就是说LFUCache类维护一个存放node的map#xff0c;同… LFU算法 Least Frequently Used最不频繁使用 Leetcode有原题之前手写过LRU数据结构还是习惯于用java实现实现是copy的评论题解。 题解注释写的很清楚
大致就是说LFUCache类维护一个存放node的map同时维护两个双向链表注意这个双向链表里面又包含了两个双向链表访问的频率是first最大last最小。其余的就是正常的双向链表的操作了(插入删除)
import java.util.HashMap;
import java.util.Map;class LFUCache {MapInteger, Node cache; // 存储缓存的内容Node中除了value值外还有key、freq、所在doublyLinkedList、所在doublyLinkedList中的postNode、所在doublyLinkedList中的preNode具体定义在下方。DoublyLinkedList firstLinkedList; // firstLinkedList.post 是频次最大的双向链表DoublyLinkedList lastLinkedList; // lastLinkedList.pre 是频次最小的双向链表满了之后删除 lastLinkedList.pre.tail.pre// 这个Node即为频次最小且访问最早的Nodeint size;int capacity;public LFUCache(int capacity) {cache new HashMap(capacity);firstLinkedList new DoublyLinkedList();lastLinkedList new DoublyLinkedList();firstLinkedList.post lastLinkedList; // 是按照倒序排列的最大的是firstlastLinkedList.pre firstLinkedList;this.capacity capacity;}public int get(int key) {Node node cache.get(key);if (node null) {return -1;}// 该key访问频次1freqInc(node);return node.value;}public void put(int key, int value) {if (capacity 0) {return;}Node node cache.get(key);// 若key存在则更新value访问频次1if (node ! null) {node.value value;freqInc(node);} else {// 若key不存在if (size capacity) {// 如果缓存满了删除lastLinkedList.pre这个链表即表示最小频次的链表中的tail.pre这个Node即最小频次链表中最先访问的Node如果该链表中的元素删空了则删掉该链表。cache.remove(lastLinkedList.pre.tail.pre.key);lastLinkedList.removeNode(lastLinkedList.pre.tail.pre);size--;if (lastLinkedList.pre.head.post lastLinkedList.pre.tail) {removeDoublyLinkedList(lastLinkedList.pre);}}// cache中put新Key-Node对儿并将新node加入表示freq为1的DoublyLinkedList中若不存在freq为1的DoublyLinkedList则新建。Node newNode new Node(key, value);cache.put(key, newNode);if (lastLinkedList.pre.freq ! 1) {DoublyLinkedList newDoublyLinedList new DoublyLinkedList(1);addDoublyLinkedList(newDoublyLinedList, lastLinkedList.pre);newDoublyLinedList.addNode(newNode);} else {lastLinkedList.pre.addNode(newNode);}size;}}/*** node的访问频次 1*/void freqInc(Node node) {// 将node从原freq对应的双向链表里移除, 如果链表空了则删除链表。DoublyLinkedList linkedList node.doublyLinkedList;DoublyLinkedList preLinkedList linkedList.pre;linkedList.removeNode(node);if (linkedList.head.post linkedList.tail) {removeDoublyLinkedList(linkedList);}// 将node加入新freq对应的双向链表若该链表不存在则先创建该链表。node.freq;if (preLinkedList.freq ! node.freq) {DoublyLinkedList newDoublyLinedList new DoublyLinkedList(node.freq);addDoublyLinkedList(newDoublyLinedList, preLinkedList);newDoublyLinedList.addNode(node);} else {preLinkedList.addNode(node);}}/*** 增加代表某1频次的双向链表*/void addDoublyLinkedList(DoublyLinkedList newDoublyLinedList, DoublyLinkedList preLinkedList) {newDoublyLinedList.post preLinkedList.post;newDoublyLinedList.post.pre newDoublyLinedList;newDoublyLinedList.pre preLinkedList;preLinkedList.post newDoublyLinedList;}/*** 删除代表某1频次的双向链表*/void removeDoublyLinkedList(DoublyLinkedList doublyLinkedList) {doublyLinkedList.pre.post doublyLinkedList.post;doublyLinkedList.post.pre doublyLinkedList.pre;}}class Node {int key;int value;int freq 1;Node pre; // Node所在频次的双向链表的前继NodeNode post; // Node所在频次的双向链表的后继NodeDoublyLinkedList doublyLinkedList; // Node所在频次的双向链表public Node() {}public Node(int key, int value) {this.key key;this.value value;}}class DoublyLinkedList {int freq; // 该双向链表表示的频次DoublyLinkedList pre; // 该双向链表的前继链表pre.freq this.freqDoublyLinkedList post; // 该双向链表的后继链表 (post.freq this.freq)Node head; // 该双向链表的头节点新节点从头部加入表示最近访问Node tail; // 该双向链表的尾节点删除节点从尾部删除表示最久访问public DoublyLinkedList() {head new Node();tail new Node();head.post tail;tail.pre head;}public DoublyLinkedList(int freq) {head new Node();tail new Node();head.post tail;tail.pre head;this.freq freq;}void removeNode(Node node) {node.pre.post node.post;node.post.pre node.pre;}void addNode(Node node) {node.post head.post;head.post.pre node;head.post node;node.pre head;node.doublyLinkedList this;}}
