Leetcode LRU缓存，数组+结构体实现
siyu1915 人气:2一、算法思路
LRUCache类有以下函数和变量：
- LRUCache(int capacity): capacity是当前对象能够存储的键值对（key，value）最大个数。
- int get(int key): 根据指定的key寻找value值，若没有找到key就返回-1
- void put(int key, int value): 存储一个新的键值对（key，value），如果key已经存在，就更新value，如果当前已达最大容量，就将最近最少使用的键值对替换。
- void show(): 查看当前所有键值对信息。（题目并没有要求书写这个函数，只是为了方便调试）。
- int size: 当前所存储的键值对个数。
- int max_size: 最大键值对个数（对应构造函数的capacity）。
- Node *list：键值对数组。
Node结构体的定义：
typedef struct LRUCacheNode {
int key;
int value;
int count;
} Node;
其中key，value构成了键值对（key，value），count表示已有多久没有使用。当一个键值对节点（Node）被第一次插入、查询或是修改，其count都会被置零，而其他节点的count自增。已达到最大存储量后，插入节点会修改所有节点中count最大的，修改完毕（也就是value值被更新后），count会被置零，而其他节点的count依然会自增。
二、代码演示
LRUCache(int capacity) {
max_size = capacity;
size = 0;
list = new Node[max_size];
}
LRUCache的构造函数仅仅初始化max_size，size和list。三者的定义如下：
private:
int size;
int max_size;
Node *list;
接下来是get函数，比较简单，依次遍历list并寻找符合要求的节点，不要忘记将符合要求的节点的count置零，以及将其他节点的count自增：
int get(int key) {
int value = -1;
for (int i = 0; i < size; ++i) {
Node *tmp = &list[i];
if (tmp->key == key) {
tmp->count = 0;
value = tmp->value;
} else {
tmp->count++;
}
}
return value;
}
接下来说重点——put函数：
void put(int key, int value) {
bool contains = false;
for (int i = 0; i < size; ++i) {
Node *tmp = &list[i];
if (tmp->key == key) {
tmp->count = 0;
tmp->value = value;
contains = true;
} else {
tmp->count++;
}
}
if (contains) { return; }
if (size >= max_size) {
int max_count = -1;
Node *max_node;
for (int i = 0; i < size; ++i) {
Node *tmp = &list[i];
if (tmp->count > max_count) {
max_count = tmp->count;
max_node = tmp;
}
}
max_node->key = key;
max_node->value = value;
max_node->count = 0;
} else {
Node n;
n.key = key;
n.value = value;
n.count = 0;
list[size++] = n;
}
}
put函数首先在list中寻找（key，value）是否存在，是则仅更新节点并返回。如果没有找到节点，接下来判断list是否已满：如果没有满，就将（key，value）存储到list数组；如果已经满了，首先根据count大小，寻找出count最大的节点，将其修改（此步并不需要将其他节点count自增，因为在第一步寻找（key，value）是否存在是已经自增过了）。
接下来是show函数，可以自行调整样式：
void show() {
for (int i = 0; i < size; ++i) {
Node *tmp = &list[i];
cout << tmp->key << "\t" << tmp->value << "\t" << tmp->count << "\n";
}
}
main函数调试：
int main() {
LRUCache cache = LRUCache(2 /* 缓存容量 */ );
cache.put(1, 1);
cache.put(2, 2);
cout << cache.get(1) << "\n"; // 返回 1
cache.put(3, 3); // 该操作会使得密钥 2 作废
cout << cache.get(2) << "\n"; // 返回 -1 (未找到)
cache.put(4, 4); // 该操作会使得密钥 1 作废
cout << cache.get(1) << "\n"; // 返回 -1 (未找到)
cout << cache.get(3) << "\n"; // 返回 3
cout << cache.get(4) << "\n"; // 返回 4
return 0;
}
main函数输出：
1 -1 -1 3 4
三、提交结果
执行用时并不理想，有待优化。
加载全部内容