leetcode
leetcode 101 ~ 150
LRU 缓存

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); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
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

代码结果

运行时间: 196 ms, 内存: 23.4 MB

/*
 * 思路：Java Stream不能直接操作类数据结构的操作。使用类似于Java代码的双向链表和HashMap实现。
 */
 
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;
 
class LRUCache {
    private final int capacity;
    private final Map<Integer, Integer> cache;
 
    public LRUCache(int capacity) {
        this.capacity = capacity;
        this.cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > capacity;
            }
        };
    }
 
    public int get(int key) {
        return cache.getOrDefault(key, -1);
    }
 
    public void put(int key, int value) {
        cache.put(key, value);
    }
}

解释

方法:

该题解采用哈希表和双向链表实现了一个 LRU 缓存机制。哈希表用于存储每个节点的引用，以便快速定位节点并在 O(1) 时间内完成删除或更新。双向链表用于按照访问的顺序存储节点，使得最近访问的节点总是移动到链表末尾，而最久未访问的节点位于链表头部。当缓存容量满时，链表头部的节点（即最久未访问的节点）被删除。

时间复杂度:

O(1)

空间复杂度:

O(capacity)

代码细节讲解

🦆
为什么选择双向链表而不是单向链表来实现LRU缓存的底层结构？
▷
双向链表能够提供前驱和后继节点的直接访问，这使得节点的添加和删除操作可以在O(1)时间内完成。在LRU缓存中，需要频繁地移除最老的节点（位于链表头部）以及移动最近访问的节点到链表尾部。使用双向链表，可以直接通过节点的前驱和后继链接进行快速的删除和添加，而无需像单向链表那样需要从头遍历到特定位置，这显著提高了效率。
🦆
当缓存达到最大容量并且需要移除最老元素时，此时如何高效地识别并删除最久未使用的节点？
▷
在LRU缓存的实现中，双向链表的头部始终指向最久未使用的节点。因此，当缓存达到最大容量需要移除最老元素时，可以直接访问链表的头部节点（头结点的下一个节点），并利用双向链表的结构特性，在O(1)时间内删除该节点。同时，使用哈希表记录节点的键与链表中对应节点的映射，也可以快速从哈希表中移除该节点的键。
🦆
在put操作中，如果键已经存在于缓存中，为什么需要先删除旧的键值对再添加新的键值对，直接更新值是否可行？
▷
虽然直接更新节点值在某些情况下是可行的，但在LRU缓存机制中，除了更新值，还需要将对应节点移动到链表的末尾表示最近使用过。如果仅仅更新值而不移动节点，那么节点的位置将不正确地反映其最近一次的访问顺序。因此，通常的做法是将旧节点从链表中移除并重新添加到链表末尾，这样可以保证节点顺序的正确性和访问的最新性。
🦆
哈希表和双向链表的结合使用中，存在哪些潜在的同步问题，尤其是在多线程环境下？
▷
在多线程环境下，当多个线程同时操作LRU缓存时，可能会引发数据竞争和一致性问题。例如，一个线程在读取某个节点的同时，另一个线程可能正在修改或删除该节点，这可能导致不一致的状态或程序崩溃。为了解决这些问题，需要引入锁机制或者其他同步工具来确保每次只有一个线程可以修改链表和哈希表，从而保证操作的原子性和数据的一致性。

相关问题

LFU 缓存

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。

实现 LFUCache 类：

  • LFUCache(int capacity) - 用数据结构的容量 capacity 初始化对象
  • int get(int key) - 如果键 key 存在于缓存中，则获取键的值，否则返回 -1 。
  • void put(int key, int value) - 如果键 key 已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量 capacity 时，则应该在插入新项之前，移除最不经常使用的项。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最久未使用 的键。

为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。

当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

 

示例：

输入：
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
输出：
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

解释：
// cnt(x) = 键 x 的使用计数
// cache=[] 将显示最后一次使用的顺序（最左边的元素是最近的）
LFUCache lfu = new LFUCache(2);
lfu.put(1, 1);   // cache=[1,_], cnt(1)=1
lfu.put(2, 2);   // cache=[2,1], cnt(2)=1, cnt(1)=1
lfu.get(1);      // 返回 1
                 // cache=[1,2], cnt(2)=1, cnt(1)=2
lfu.put(3, 3);   // 去除键 2 ，因为 cnt(2)=1 ，使用计数最小
                 // cache=[3,1], cnt(3)=1, cnt(1)=2
lfu.get(2);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,1], cnt(3)=2, cnt(1)=2
lfu.put(4, 4);   // 去除键 1 ，1 和 3 的 cnt 相同，但 1 最久未使用
                 // cache=[4,3], cnt(4)=1, cnt(3)=2
lfu.get(1);      // 返回 -1（未找到）
lfu.get(3);      // 返回 3
                 // cache=[3,4], cnt(4)=1, cnt(3)=3
lfu.get(4);      // 返回 4
                 // cache=[3,4], cnt(4)=2, cnt(3)=3

 

提示：

  • 1 <= capacity <= 104
  • 0 <= key <= 105
  • 0 <= value <= 109
  • 最多调用 2 * 105 次 get 和 put 方法

设计内存文件系统

设计内存文件系统

迭代压缩字符串

迭代压缩字符串
二叉树的后序遍历对链表进行插入排序