参考下列结构图和视频
代码解析
#include <stdio.h>
#include <stdlib.h>
/**
* 实现一个简单的 LFU（Least Frequently Used）缓存算法。
*
* @param operators 二维数组，表示操作指令。
* @param operatorsRowLen 操作数组的行数。
* @param operatorsColLen 操作数组的列数。
* @param k 缓存的容量。
* @param returnSize 返回数组的行数。
* @return 返回一个一维数组，表示每次操作的结果。
*/
int* LFU(int** operators, int operatorsRowLen, int* operatorsColLen, int k,
int* returnSize) {
// 分配返回数组，大小为操作数组的行数
int* a = (int*)malloc(sizeof(int) * operatorsRowLen);
// 分配缓存数组，大小为 k，每个缓存项包含 4 个字段
int** t = (int**)malloc(sizeof(int*) * k);
for (int i = 0; i < k; i++) {
t[i] = (int*)malloc(sizeof(int) * 4);
// 初始化缓存项：
// t[i][0]：访问频率，初始为 0
// t[i][1]：键值，初始为 0
// t[i][2]：值，初始为 0
// t[i][3]：时间戳，初始为 0
t[i][0] = 0;
t[i][1] = 0;
t[i][2] = 0;
t[i][3] = 0;
}
// 返回数组的当前长度
int alen = 0;
// 遍历操作数组
for (int i = 0; i < operatorsRowLen; i++) {
// 标记是否找到对应的键
char set = 0;
// 操作类型为 1，表示插入或更新键值对
if (operators[i][0] == 1) {
// 遍历缓存数组，查找是否存在相同的键
for (int j = 0; j < k; j++) {
if (t[j][1] == operators[i][1 ]){ // 找到相同的键
// 更新键对应的值
t[j][2] = operators[i][2];
// 增加访问频率
t[j][0]++;
// 更新时间戳
t[j][3] = i;
// 标记找到
set = 1;
break;
}
}
// 如果缓存中不存在该键
if (set == 0) {
// 初始化最小频率为一个较大的值
int min = 10000;
int p; // 用于记录需要替换的缓存项索引
// 遍历缓存数组，找到访问频率最小的项
for (int j = 0; j < k; j++) {
if (t[j][0] < min) {
min = t[j][0];
p = j;
} else if (t[j][0] == min && t[j][3] < t[p][3]) {
// 如果频率相同，比较戳时间，选择最早插入的项
min = t[j][0];
p = j;
}
}
// 替换访问频率最小的缓存项
t[p][1] = operators[i][1]; // 更新键
t[p][2] = operators[i][2]; // 更新值
t[p][0] = 1; // 初始化访问频率为 1
t[p][3] = i; // 更新时间戳
}
}
else { // 操作类型为 2表示，查询键值
// 遍历缓存数组，查找是否存在相同的键
for (int j = 0; j < k; j++) {
if (t[j][1] == operators[i][1]) { // 找到相同的键
// 将键对应的值添加到返回数组中
a[alen++] = t[j][2];
// 增加访问频率
t[j][0]++;
// 更新时间戳
t[j][3] = i;
// 标记找到
set = 1;
break;
}
}
// 如果缓存中不存在该键
if (set == 0) {
// 将 -1 添加到返回数组中，表示查询失败
a[alen++] = -1;
}
}
}
// 设置返回数组的大小
*returnSize = alen;
// 返回结果数组
return a;
}
代码结构和实现原理
LFU缓存算法的核心思想是根据访问频率来决定缓存项的淘汰顺序。频率最低的缓存项最先被淘汰。
函数定义
int* LFU(int** operators, int operatorsRowLen, int* operatorsColLen, int k, int* returnSize) {
int* a = (int*)malloc(sizeof(int) * operatorsRowLen); // 用于存储每次操作的结果
// 分配缓存数组，大小为 k，每个缓存项包含 4 个字段
int** t = (int**)malloc(sizeof(int*) * k);
for (int i = 0; i < k; i++) {
t[i] = (int*)malloc(sizeof(int) * 4);
t[i][0] = 0; // 访问频率，初始为 0
t[i][1] = 0; // 键值，初始为 0
t[i][2] = 0; // 值，初始为 0
t[i][3] = 0; // 时间戳，初始为 0
}
int alen = 0; // 返回数组的当前长度
变量说明：
a: 返回数组，用于存储每次操作的结果。t: 缓存数组，大小为k，每个缓存项有四个字段：t[i][0]: 访问频率（初始为 0）t[i][1]: 键值（初始为 0）t[i][2]: 值（初始为 0）t[i][3]: 时间戳（初始为 0）
插入操作
if (operators[i][0] == 1) {
// 查找是否存在相同的键
for (int j = 0; j < k; j++) {
if (t[j][1] == operators[i][1]) { // 找到相同的键
t[j][2] = operators[i][2]; // 更新值
t[j][0]++; // 增加访问频率
t[j][3] = i; // 更新时间戳
set = 1; // 标记为已找到
break;
}
}
// 如果缓存中不存在该键
if (set == 0) {
int min = 10000; // 初始化最小频率为一个较大的值
int p; // 用于记录需要替换的缓存项索引
// 遍历缓存数组，找到访问频率最小的项
for (int j = 0; j < k; j++) {
if (t[j][0] < min) {
min = t[j][0];
p = j;
} else if (t[j][0] == min && t[j][3] < t[p][3]) {
// 如果频率相同，比较戳时间，选择最早插入的项
min = t[j][0];
p = j;
}
}
// 替换访问频率最小的缓存项
t[p][1] = operators[i][1]; // 更新键
t[p][2] = operators[i][2]; // 更新值
t[p][0] = 1; // 初始化访问频率为 1
t[p][3] = i; // 更新时间戳
}
}
插入操作步骤：
- 查找缓存：遍历缓存数组，如果找到对应的键，更新其值、访问频率和时间戳。
- 替换缓存：如果缓存中没有对应的键，找到访问频率最小的缓存项进行替换。若频率相同，则替换最早插入的缓存项。
查询操作
else { // 操作类型为 2表示，查询键值
for (int j = 0; j < k; j++) {
if (t[j][1] == operators[i][1]) { // 找到相同的键
a[alen++] = t[j][2]; // 将键对应的值添加到返回数组中
t[j][0]++; // 增加访问频率
t[j][3] = i; // 更新时间戳
set = 1; // 标记为已找到
break;
}
}
// 如果缓存中不存在该键
if (set == 0) {
a[alen++] = -1; // 将 -1 添加到返回数组中，表示查询失败
}
}
查询操作步骤：
- 查找缓存：遍历缓存数组，如果找到对应的键，返回其值，并更新其访问频率和时间戳。
- 未找到键：如果缓存中没有找到对应的键，返回 -1 表示查询失败。
代码注释
变量初始化
// 分配返回数组，大小为操作数组的行数
int* a = (int*)malloc(sizeof(int) * operatorsRowLen);
// 分配缓存数组，大小为 k，每个缓存项包含 4 个字段
int** t = (int**)malloc(sizeof(int*) * k);
for (int i = 0; i < k; i++) {
t[i] = (int*)malloc(sizeof(int) * 4);
t[i][0] = 0; // 访问频率，初始为 0
t[i][1] = 0; // 键值，初始为 0
t[i][2] = 0; // 值，初始为 0
t[i][3] = 0; // 时间戳，初始为 0
}
a数组用于存储每次操作的返回结果。t是缓存数组，存储缓存项的详细信息，包括访问频率、键值、值和时间戳。
插入操作逻辑
if (operators[i][0] == 1) {
// 遍历缓存数组，查找是否存在相同的键
for (int j = 0; j < k; j++) {
if (t[j][1] == operators[i][1]) { // 找到相同的键
t[j][2] = operators[i][2]; // 更新值
t[j][0]++; // 增加访问频率
t[j][3] = i; // 更新时间戳
set = 1; // 标记为已找到
break;
}
}
// 如果缓存中不存在该键
if (set == 0) {
int min = 10000; // 初始化最小频率为一个较大的值
int p; // 用于记录需要替换的缓存项索引
// 找到访问频率最小的缓存项
for (int j = 0; j < k; j++) {
if (t[j][0] < min) {
min = t[j][0];
p = j;
} else if (t[j][0] == min && t[j][3] < t[p][3]) {
min = t[j][0];
p = j;
}
}
// 替换缓存项
t[p][1] = operators[i][1]; // 更新键
t[p][2] = operators[i][2]; // 更新值
t[p][0] = 1; // 访问频率设为 1
t[p][3] = i; // 更新时间戳
}
}
查询操作逻辑
else { // 操作类型为 2表示，查询键值
for (int j = 0; j < k; j++) {
if (t[j][1] == operators[i][1]) { // 找到相同的键
a[alen++] = t[j][2]; // 返回对应的值
t[j][0]++; // 增加访问频率
t[j][3] = i; // 更新时间戳
set = 1; // 标记为已找到
break;
}
}
// 如果缓存中没有该键，返回 -1
if (set == 0) {
a[alen++] = -1; // 查询失败
}
}
总结
LFU缓存算法的核心是维护缓存项的访问频率并使用最小频率来决定淘汰策略。通过此算法，我们可以有效地管理缓存，保证最常用的缓存项不会被替换。这题还是比LRU简单点。而且采用数组，没有完全使用链表，简单很多。不想是LRU一个系统，这题本质上是一个函数，一个里面套着俩函数。插入和查找。