一、算法思路
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
三、提交结果
执行用时并不理想,有待优化。