越秀网站建设公司,网站备案登陆,县科协微网站建设,php如何自己做网站【问题描述】
LFU
运用你所掌握的数据结构#xff0c;设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作#xff1a; 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中#xff0c;则获取密钥的值#xff08;总是正数设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作 获取数据 get 和 写入数据 put 。获取数据 get(key) - 如果密钥 (key) 存在于缓存中则获取密钥的值总是正数否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在则写入其数据值。当缓存容量达到上限时它应该在写入新数据之前删除最久未使用的数据值从而为新的数据值留出空间。进阶:你是否可以在 O(1) 时间复杂度内完成这两种操作示例:LRUCache cache new LRUCache( 2 /* 缓存容量 */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cache.get(2); // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cache.get(1); // 返回 -1 (未找到)
cache.get(3); // 返回 3
cache.get(4); // 返回 4
【解答思路】
1. 缓存是有限的在缓存满的时候删除哪些元素就有不同的缓存删除策略。
LRU Least Recently Used缓存机制
在缓存满的时候删除缓存里最久未使用的数据然后再放入新元素数据的访问时间很重要访问时间距离现在最近就最不容易被删除。
时间复杂度O(1) 空间复杂度O(N)
import java.util.Map;public class LRUCache {private MapInteger, ListNode map;/*** 双链表结点类*/private class ListNode {private Integer key;private Integer value;/*** 前驱结点 precursor*/private ListNode pre;/*** 后继结点 successor写成 next 是照顾单链表的表示习惯*/private ListNode next;public ListNode() {}public ListNode(Integer key, Integer value) {this.key key;this.value value;}}private int capacity;/*** 虚拟头结点没有前驱*/private ListNode dummyHead;/*** 虚拟尾结点没有后继*/private ListNode dummyTail;public LRUCache(int capacity) {map new HashMap(capacity);this.capacity capacity;dummyHead new ListNode(-1, -1);dummyTail new ListNode(-1, -1);// 初始化链表为 head - taildummyHead.next dummyTail;dummyTail.pre dummyHead;}/*** 如果存在把当前结点移动到双向链表的头部** param key* return*/public int get(int key) {if (map.containsKey(key)) {ListNode node map.get(key);int val node.value;// 把当前 node 移动到双向链表的头部moveNode2Head(key);return val;} else {return -1;}}/*** 如果哈希表的容量满了就要删除一个链表末尾元素然后在链表头部插入新元素** param key* param value*/public void put(int key, int value) {if (map.containsKey(key)) {// 1、更新 valuemap.get(key).value value;// 2、把当前 node 移动到双向链表的头部moveNode2Head(key);return;}// 放元素的操作是一样的if (map.size() capacity) {// 如果满了ListNode oldTail removeTail();// 设计 key 就是为了在这里删除map.remove(oldTail.key);}// 然后添加元素ListNode newNode new ListNode(key, value);map.put(key, newNode);addNode2Head(newNode);}// 为了突出主干逻辑下面是 3 个公用的方法/*** 删除双链表尾部结点*/private ListNode removeTail() {ListNode oldTail dummyTail.pre;ListNode newTail oldTail.pre;// 两侧结点建立连接newTail.next dummyTail;dummyTail.pre newTail;// 释放引用oldTail.pre null;oldTail.next null;return oldTail;}/*** 把当前 key 指向的结点移到双向链表的头部** param key*/private void moveNode2Head(int key) {// 1、先把 node 拿出来ListNode node map.get(key);// 2、原来 node 的前驱和后继接上node.pre.next node.next;node.next.pre node.pre;// 3、再把 node 放在末尾addNode2Head(node);}/*** 在双链表的头部新增一个结点** param newNode*/private void addNode2Head(ListNode newNode) {// 1、当前头结点ListNode oldHead dummyHead.next;// 2、末尾结点的后继指向新结点oldHead.pre newNode;// 3、设置新结点的前驱和后继newNode.pre dummyHead;newNode.next oldHead;// 4、更改虚拟头结点的后继结点dummyHead.next newNode;}public static void main(String[] args) {LRUCache cache new LRUCache(2);cache.put(1, 1);cache.put(2, 2);System.out.println(cache.map.keySet());int res1 cache.get(1);System.out.println(res1);cache.put(3, 3);int res2 cache.get(2);System.out.println(res2);int res3 cache.get(3);System.out.println(res3);cache.put(4, 4);System.out.println(cache.map.keySet());int res4 cache.get(1);System.out.println(res4);int res5 cache.get(3);System.out.println(res5);int res6 cache.get(4);System.out.println(res6);}
}作者liweiwei1419
链接https://leetcode-cn.com/problems/lru-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiw-2/
【总结】
1.缓存删除机制
LRU Least Recently Used缓存机制[第146题]LFU Least Frequently Used最不经常使用缓存机制[第460 题] 时间空间tradeoff 存取数据时间性能最好 - 哈希表 访问某个数据时间优先级得提前删除末尾结点的需求头尾访问数据最快 - 双向链表 LinkedList 双向链表 本题需要定制化操作
参考链接https://leetcode-cn.com/problems/lru-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiw-2/
