小朋友都能看懂的题解 | #设计LFU缓存结构#
什么是LFU缓存？
想象你有一个小书架，但你的书架只能放几本书。每次你想读一本书，如果书架上已经有这本书，你就直接拿起来读。但如果书架上没有这本书，而书架已经满了，你需要决定哪本书应该被取下来，以便腾出位置放新书。
LFU缓存就是帮助你决定哪本书应该被取下来。它会优先考虑那些很少被读的书，如果有多本书读的次数一样少，那么它会选择最早放在书架上的那本。📚📖
数据结构
- 键值对映射 (
keyValueMap)：这是一个大大的笔记本，用来记录每本书的名字和它的内容。比如，键是书的名字，值是书的内容。 - 键频率映射 (
keyFreqMap)：这是一个小本子，用来记录每本书被读了多少次。 - 频率集合映射 (
freqMap)：这是一个特殊的盒子，用来记录每个频率下有哪些书。这样我们可以快速找到频率最低的书。 - 最小堆 (
minHeap)：这是一个神奇的袋子，用来快速找到频率最低且最旧的书。每个元素是一个小纸条，上面写着书的名字、被读的次数和最后一次读的时间。
导入必要的包
import java.util.*;
这行代码导入了Java标准库中的所有必要类和接口，包括哈希表、集合、优先队列等。
定义 Solution 类和 LFU 方法
public class Solution {
public int[] LFU(int[][] operators, int k) {
Solution类是我们实现的主要类。LFU方法接受两个参数：operators：一个二维数组，表示一系列操作。k：缓存的最大容量。
初始化数据结构
// 初始化我们的大本子和小本子
Map<Integer, Integer> keyValueMap = new HashMap<>();
Map<Integer, Integer> keyFreqMap = new HashMap<>();
Map<Integer, Set<Integer>> freqMap = new HashMap<>();
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> {
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
int timestamp = 0;
List<Integer> results = new ArrayList<>();
keyValueMap：存储键和值的映射。keyFreqMap：存储键和其被访问次数的映射。freqMap：存储每个频率对应的键的集合。minHeap：优先队列，用于快速找到频率最低且最旧的键。每个元素是一个数组[key, frequency, timestamp]。timestamp：用于记录操作的时间。results：存储所有get操作的结果。
处理每个操作
for (int[] operator : operators) {
int opt = operator[0];
int key = operator[1];
- 遍历每个操作
operator。 opt表示操作类型（1 表示set，2 表示get）。key是操作的键。
处理 set 操作
if (opt == 1) { // 放一本书（set）
int value = operator[2];
if (keyValueMap.size() >= k && !keyValueMap.containsKey(key)) {
// 书架已满，需要取下一本最少读的书
while (!minHeap.isEmpty()) {
int[] entry = minHeap.poll();
int evictKey = entry[0];
if (keyFreqMap.get(evictKey) == entry[1]) {
keyValueMap.remove(evictKey);
keyFreqMap.remove(evictKey);
freqMap.get(entry[1]).remove(evictKey);
if (freqMap.get(entry[1]).isEmpty()) {
freqMap.remove(entry[1]);
}
break;
}
}
}
keyValueMap.put(key, value); // 把新书放到书架上
keyFreqMap.put(key, 1); // 记录新书被读了1次
freqMap.computeIfAbsent(1, f -> new HashSet<>()).add(key); // 把新书放进频率盒子里
minHeap.offer(new int[]{key, 1, timestamp++}); // 把新书放进神奇袋子里
- 获取操作的值
value。 - 如果书架已满且新书不在书架上，需要从
minHeap中取出频率最低且最旧的键，并从所有数据结构中删除它。 - 将新书放入
keyValueMap，设置其频率为 1，并更新freqMap和minHeap。
处理 get 操作
} else if (opt == 2) { // 拿一本书（get）
if (keyValueMap.containsKey(key)) {
int value = keyValueMap.get(key); // 找到书的内容
int freq = keyFreqMap.get(key);
keyFreqMap.put(key, freq + 1); // 增加书的阅读次数
freqMap.get(freq).remove(key);
if (freqMap.get(freq).isEmpty()) {
freqMap.remove(freq);
}
freqMap.computeIfAbsent(freq + 1, f -> new HashSet<>()).add(key); // 更新频率盒子
minHeap.remove(new int[]{key, freq, -1});
minHeap.offer(new int[]{key, freq + 1, timestamp++}); // 更新神奇袋子
results.add(value); // 记录结果
} else {
results.add(-1); // 书不在书架上，返回 -1
}
}
- 如果键在
keyValueMap中存在，获取其值并增加其频率。 - 更新
keyFreqMap、freqMap和minHeap。 - 将结果添加到
results列表中。 - 如果键不存在，返回 -1 并记录结果。
返回结果
return results.stream().mapToInt(i -> i).toArray(); // 返回所有结果
}
}
- 将
results列表转换为数组并返回。
完整代码实现
import java.util.*;
public class Solution {
public int[] LFU(int[][] operators, int k) {
// 初始化我们的大本子和小本子
Map<Integer, Integer> keyValueMap = new HashMap<>();
Map<Integer, Integer> keyFreqMap = new HashMap<>();
Map<Integer, Set<Integer>> freqMap = new HashMap<>();
PriorityQueue<int[]> minHeap = new PriorityQueue<>((a, b) -> {
if (a[1] != b[1]) return a[1] - b[1];
return a[2] - b[2];
});
int timestamp = 0;
List<Integer> results = new ArrayList<>();
for (int[] operator : operators) {
int opt = operator[0];
int key = operator[1];
if (opt == 1) { // 放一本书（set）
int value = operator[2];
if (keyValueMap.size() >= k && !keyValueMap.containsKey(key)) {
// 书架已满，需要取下一本最少读的书
while (!minHeap.isEmpty()) {
int[] entry = minHeap.poll();
int evictKey = entry[0];
if (keyFreqMap.get(evictKey) == entry[1]) {
keyValueMap.remove(evictKey);
keyFreqMap.remove(evictKey);
freqMap.get(entry[1]).remove(evictKey);
if (freqMap.get(entry[1]).isEmpty()) {
freqMap.remove(entry[1]);
}
break;
}
}
}
keyValueMap.put(key, value); // 把新书放到书架上
keyFreqMap.put(key, 1); // 记录新书被读了1次
freqMap.computeIfAbsent(1, f -> new HashSet<>()).add(key); // 把新书放进频率盒子里
minHeap.offer(new int[]{key, 1, timestamp++}); // 把新书放进神奇袋子里
} else if (opt == 2) { // 拿一本书（get）
if (keyValueMap.containsKey(key)) {
int value = keyValueMap.get(key); // 找到书的内容
int freq = keyFreqMap.get(key);
keyFreqMap.put(key, freq + 1); // 增加书的阅读次数
freqMap.get(freq).remove(key);
if (freqMap.get(freq).isEmpty()) {
freqMap.remove(freq);
}
freqMap.computeIfAbsent(freq + 1, f -> new HashSet<>()).add(key); // 更新频率盒子
minHeap.remove(new int[]{key, freq, -1});
minHeap.offer(new int[]{key, freq + 1, timestamp++}); // 更新神奇袋子
results.add(value); // 记录结果
} else {
results.add(-1); // 书不在书架上，返回 -1
}
}
}
return results.stream().mapToInt(i -> i).toArray(); // 返回所有结果
}
}
希望这篇文章对你有帮助👍。
#牛客创作赏金赛##题解#小学生都能看懂的算法 文章被收录于专栏
主要面向小白的算法文章。以小学生都能看懂为目标而编写，顺便巩固下自己。
查看20道真题和解析