LFU缓存

题目要求实现LFULeast Frequently Used最不经常使用缓存逻辑使用频次计数器进行淘汰。后续更新附代码class LFUCache { // 双向链表节点 private static class Node { int key, value; int freq 1; // 访问频次 Node prev, next; Node(int key, int value) { this.key key; this.value value; } } // 频次链表相同频次的节点组成一个双向链表 private static class FreqList { int freq; Node sentinel; int size; // 当前频次链表的节点数量 FreqList prev, next; FreqList(int freq) { this.freq freq; this.sentinel new Node(0, 0); this.sentinel.prev this.sentinel; this.sentinel.next this.sentinel; this.size 0; } // 判断当前频次链表是否为空 boolean isEmpty() { return size 0; } // 在链表头部添加节点 void addFirst(Node node) { node.prev sentinel; node.next sentinel.next; sentinel.next.prev node; sentinel.next node; size; } // 从链表中移除节点 void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; size--; } // 移除最后一个节点 Node removeLast() { if (isEmpty()) return null; Node last sentinel.prev; removeNode(last); return last; } } private final int capacity; private final MapInteger, Node keyToNode new HashMap(); private final MapInteger, FreqList freqToFreqList new HashMap(); private FreqList headFreqList; // 最小频次链表头 public LFUCache(int capacity) { this.capacity capacity; this.headFreqList new FreqList(0); } public int get(int key) { if (!keyToNode.containsKey(key)) { return -1; } Node node keyToNode.get(key); updateFreq(node); return node.value; } public void put(int key, int value) { if (capacity 0) return; if (keyToNode.containsKey(key)) { Node node keyToNode.get(key); node.value value; updateFreq(node); return; } // 容量已满淘汰最不常使用的节点 if (keyToNode.size() capacity) { removeLeastFrequent(); } // 创建新节点 Node node new Node(key, value); keyToNode.put(key, node); // 将节点放入频次为1的链表 FreqList freqList freqToFreqList.computeIfAbsent(1, k - new FreqList(1)); freqList.addFirst(node); // 如果1不是最小频次更新最小频次链表头 if (headFreqList.freq ! 1) { // 插入到headFreqList之后 freqList.next headFreqList.next; if (headFreqList.next ! null) { headFreqList.next.prev freqList; } headFreqList.next freqList; freqList.prev headFreqList; } } // 更新节点的访问频次 private void updateFreq(Node node) { int oldFreq node.freq; int newFreq oldFreq 1; node.freq newFreq; // 从旧频次链表中移除节点 FreqList oldList freqToFreqList.get(oldFreq); oldList.removeNode(node); // 将节点放入新频次链表 FreqList newList freqToFreqList.computeIfAbsent(newFreq, k - new FreqList(newFreq)); newList.addFirst(node); // 如果旧链表变空从频次映射中移除并更新链表连接 if (oldList.isEmpty()) { freqToFreqList.remove(oldFreq); removeFreqList(oldList); } // 更新最小频次链表头 if (headFreqList.next null || headFreqList.next.freq newFreq) { // 不需要更新因为新频次更大 } if (headFreqList.next null || headFreqList.next.freq newFreq) { // 保持最小频次 } } // 从双向频次链表中移除一个空的频次链表 private void removeFreqList(FreqList freqList) { freqList.prev.next freqList.next; if (freqList.next ! null) { freqList.next.prev freqList.prev; } } // 淘汰最不常使用的节点最小频次且最久未使用 private void removeLeastFrequent() { if (headFreqList.next null) return; // 找到最小频次链表headFreqList.next 第一个非空的有效链表 FreqList minFreqList headFreqList.next; while (minFreqList ! null minFreqList.isEmpty()) { minFreqList minFreqList.next; } if (minFreqList null) return; // 移除该链表的最后一个节点最久未使用的 Node removed minFreqList.removeLast(); if (removed ! null) { keyToNode.remove(removed.key); } // 如果链表变空移除该链表 if (minFreqList.isEmpty()) { removeFreqList(minFreqList); freqToFreqList.remove(minFreqList.freq); } } // 获取当前缓存大小 public int size() { return keyToNode.size(); } }ACM模式import java.util.*; class LFUCache { // 双向链表节点 private static class Node { int key, value; int freq 1; // 访问频次 Node prev, next; Node(int key, int value) { this.key key; this.value value; } } // 频次链表相同频次的节点组成一个双向链表 private static class FreqList { int freq; Node sentinel; int size; // 当前频次链表的节点数量 FreqList prev, next; FreqList(int freq) { this.freq freq; this.sentinel new Node(0, 0); this.sentinel.prev this.sentinel; this.sentinel.next this.sentinel; this.size 0; } // 判断当前频次链表是否为空 boolean isEmpty() { return size 0; } // 在链表头部添加节点 void addFirst(Node node) { node.prev sentinel; node.next sentinel.next; sentinel.next.prev node; sentinel.next node; size; } // 从链表中移除节点 void removeNode(Node node) { node.prev.next node.next; node.next.prev node.prev; size--; } // 移除最后一个节点 Node removeLast() { if (isEmpty()) return null; Node last sentinel.prev; removeNode(last); return last; } } private final int capacity; private final MapInteger, Node keyToNode new HashMap(); private final MapInteger, FreqList freqToFreqList new HashMap(); private FreqList headFreqList; // 最小频次链表头 public LFUCache(int capacity) { this.capacity capacity; this.headFreqList new FreqList(0); } public int get(int key) { if (!keyToNode.containsKey(key)) { return -1; } Node node keyToNode.get(key); updateFreq(node); return node.value; } public void put(int key, int value) { if (capacity 0) return; if (keyToNode.containsKey(key)) { Node node keyToNode.get(key); node.value value; updateFreq(node); return; } // 容量已满淘汰最不常使用的节点 if (keyToNode.size() capacity) { removeLeastFrequent(); } // 创建新节点 Node node new Node(key, value); keyToNode.put(key, node); // 将节点放入频次为1的链表 FreqList freqList freqToFreqList.computeIfAbsent(1, k - new FreqList(1)); freqList.addFirst(node); // 如果1不是最小频次更新最小频次链表头 if (headFreqList.freq ! 1) { // 插入到headFreqList之后 freqList.next headFreqList.next; if (headFreqList.next ! null) { headFreqList.next.prev freqList; } headFreqList.next freqList; freqList.prev headFreqList; } } // 更新节点的访问频次 private void updateFreq(Node node) { int oldFreq node.freq; int newFreq oldFreq 1; node.freq newFreq; // 从旧频次链表中移除节点 FreqList oldList freqToFreqList.get(oldFreq); oldList.removeNode(node); // 将节点放入新频次链表 FreqList newList freqToFreqList.computeIfAbsent(newFreq, k - new FreqList(newFreq)); newList.addFirst(node); // 如果旧链表变空从频次映射中移除并更新链表连接 if (oldList.isEmpty()) { freqToFreqList.remove(oldFreq); removeFreqList(oldList); } // 更新最小频次链表头 if (headFreqList.next null || headFreqList.next.freq newFreq) { // 不需要更新因为新频次更大 } if (headFreqList.next null || headFreqList.next.freq newFreq) { // 保持最小频次 } } // 从双向频次链表中移除一个空的频次链表 private void removeFreqList(FreqList freqList) { freqList.prev.next freqList.next; if (freqList.next ! null) { freqList.next.prev freqList.prev; } } // 淘汰最不常使用的节点最小频次且最久未使用 private void removeLeastFrequent() { if (headFreqList.next null) return; // 找到最小频次链表headFreqList.next 第一个非空的有效链表 FreqList minFreqList headFreqList.next; while (minFreqList ! null minFreqList.isEmpty()) { minFreqList minFreqList.next; } if (minFreqList null) return; // 移除该链表的最后一个节点最久未使用的 Node removed minFreqList.removeLast(); if (removed ! null) { keyToNode.remove(removed.key); } // 如果链表变空移除该链表 if (minFreqList.isEmpty()) { removeFreqList(minFreqList); freqToFreqList.remove(minFreqList.freq); } } // 获取当前缓存大小 public int size() { return keyToNode.size(); } } public class Main { public static void main(String[] args) { Scanner scanner new Scanner(System.in); int n scanner.nextInt(); LFUCache lfu null; ListString output new ArrayList(); for (int i 0; i n; i) { String op scanner.next(); switch (op) { case LFUCache: int capacity scanner.nextInt(); lfu new LFUCache(capacity); output.add(null); break; case put: int key scanner.nextInt(); int value scanner.nextInt(); lfu.put(key, value); output.add(null); break; case get: int getKey scanner.nextInt(); int result lfu.get(getKey); output.add(String.valueOf(result)); break; case size: output.add(String.valueOf(lfu.size())); break; default: output.add(unknown); } } // 输出结果 for (int i 0; i output.size(); i) { System.out.print(output.get(i)); if (i output.size() - 1) { System.out.print( ); } } scanner.close(); } }