公主岭网站开发,北海 做网站 英文,汽车之家网站是谁做的,seo是指什么职位leetCode#xff1a;146. LRU 缓存
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类#xff1a;
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中#x…leetCode146. LRU 缓存
题目描述
请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。示例输入
[LRUCache, put, put, get, put, get, put, get, get, get]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]解释
LRUCache lRUCache new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {11}
lRUCache.put(2, 2); // 缓存是 {11, 22}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4
提示1 capacity 3000
0 key 10000
0 value 105
最多调用 2 * 105 次 get 和 put
题目解读
LRU 缓存淘汰算法就是一种常用策略。LRU 的全称是 Least Recently Used也就是说我们认为最近使用过的数据应该是是「有用的」很久都没用过的数据应该是无用的内存满了就优先删那些很久没用过的数据。
题目实现
只使用HashMap实现
算法设计
要让 put 和 get 方法的时间复杂度为 O(1)我们可以总结出 cache 这个数据结构必要的条件
1、显然 cache 中的元素必须有时序以区分最近使用的和久未使用的数据当容量满了之后要删除最久未使用的那个元素腾位置。
2、我们要在 cache 中快速找某个 key 是否已存在并得到对应的 val
3、每次访问 cache 中的某个 key需要将这个元素变为最近使用的也就是说 cache 要支持在任意位置快速插入和删除元素。
那么什么数据结构同时符合上述条件呢哈希表查找快但是数据无固定顺序链表有顺序之分插入删除快但是查找慢。所以结合一下形成一种新的数据结构哈希链表 LinkedHashMap。
LRU 缓存算法的核心数据结构就是哈希链表双向链表和哈希表的结合体。这个数据结构长这样 如果我们每次默认从链表尾部添加元素那么显然越靠尾部的元素就是最近使用的越靠头部的元素就是最久未使用的。
2、对于某一个 key我们可以通过哈希表快速定位到链表中的节点从而取得对应 val。
3、链表显然是支持在任意位置快速插入和删除的改改指针就行。只不过传统的链表无法按照索引快速访问某一个位置的元素而这里借助哈希表可以通过 key 快速映射到任意一个链表节点然后进行插入和删除。
代码实现
import java.util.*;// LRUCache 类实现了一个基于 LRU 策略的缓存
public class LRUCache {// 缓存的最大容量private final int capacity;// 使用 HashMap 存储键值对便于快速查找private final MapInteger, Node cacheMap;// 使用 LinkedList 作为双向链表维护元素的访问顺序private final LinkedListNode lruList;// 构造函数初始化缓存容量public LRUCache(int capacity) {this.capacity capacity;this.cacheMap new HashMap(capacity);this.lruList new LinkedList();}// 根据键获取值如果存在则更新访问顺序public int get(int key) {if (cacheMap.containsKey(key)) { // 如果键存在moveToHead(cacheMap.get(key)); // 移动节点到链表头部return cacheMap.get(key).val; // 返回值}return -1; // 键不存在返回 -1}// 插入或更新键值对如果超过容量则淘汰最不常用的项public void put(int key, int value) {if (cacheMap.containsKey(key)) { // 如果键已存在moveToHead(cacheMap.get(key)); // 移动节点到链表头部cacheMap.get(key).val value; // 更新值} else { // 键不存在if (cacheMap.size() capacity) { // 如果缓存已满evict(); // 淘汰最不常用的项}Node newNode new Node(key, value); // 创建新节点cacheMap.put(key, newNode); // 添加到缓存映射lruList.addFirst(newNode); // 添加到链表头部}}// 将指定节点移到链表头部private void moveToHead(Node node) {lruList.remove(node); // 从链表中移除节点lruList.addFirst(node); // 将节点添加到链表头部}// 淘汰最不常用的项private void evict() {Node nodeToRemove lruList.pollLast(); // 获取链表尾部的节点cacheMap.remove(nodeToRemove.key); // 从缓存映射中移除节点}// 内部类 Node 表示链表中的一个节点包含键、值以及指向前后节点的引用static class Node {int key;int val;Node next;Node prev;public Node(int key, int val) {this.key key;this.val val;}}
} 使用LinkedHashMap实现
算法设计
LinkedHashMap内部已经使用了LinkedList
代码实现
import java.util.LinkedHashMap;//leetcode submit region begin(Prohibit modification and deletion)
class LRUCache {LinkedHashMapInteger, Integer cache new LinkedHashMap();int capacity;public LRUCache(int capacity) {this.capacity capacity;}public int get(int key) {//不包含if (!cache.containsKey(key)) {return -1;}// 将 key 变为最近使用makeRecently(key);return cache.get(key);}public void put(int key, int value) {if (cache.containsKey(key)) {makeRecently(key);} else {if (cache.size() capacity) {//删除头结点cache.remove(cache.keySet().iterator().next());}}cache.put(key, value);}/*** 将 key 移动到队尾** param key*/private void makeRecently(int key) {int val cache.get(key);// 删除 key重新插入到队尾cache.remove(key);cache.put(key, val);}}继承LinkedHashMap实现(最简洁)
算法设计
LinkedHashMap.afterNodeInsertion()
void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.EntryK,V first;if (evict (first head) ! null removeEldestEntry(first)) {K key first.key;removeNode(hash(key), key, null, false, true);}
}
afterNodeInsertion() 可能会删除老元素但需要满足3个条件: evict 为 true; (first head) ! null双向链表的头结点不能为 null换句话说双向链表中必须有老元素(没有老元素还删个锤锤); removeEldestEntry(first) 方法返回为 true。 其中removeEldestEntry方法是『移除最老的元素』默认为false即不删除 因此我们需要复写removeEldestEntry方法即可
代码实现
class LRUCache extends LinkedHashMapInteger, Integer {int capacity0;public LRUCache(int capacity) {super(capacity, 0.75F, true);this.capacitycapacity;}public int get(int key) {return (int) super.getOrDefault(key, -1);}public void put(int key, int value) {super.put(key, value);}/*** 判断元素个数是否超过缓存容量*/protected boolean removeEldestEntry(Map.EntryInteger, Integer eldest) {return size() capacity;}
}其他
算法用途
手机管家-后台程序管理
相关
现在你应该理解 LRULeast Recently Used策略了。当然还有其他缓存淘汰策略比如不要按访问的时序来淘汰而是按访问频率LFU 策略来淘汰等等各有应用场景 详见 LeetCode 160 LFU
