菏泽网站网站建设,文案转行做网站编辑,南昌做公司网站哪家好,推荐网站建设题目内容
实现一个 LRUCache 类#xff0c;三个接口#xff1a;
LRUCache(int capacity) 创建一个大小为 capacity 的缓存get(int key) 从缓存中获取键为 key 的键值对的 valueput(int key, int value) 向缓存中添加键值对 (key, value)
要求 get 和 put 的均摊时间复杂度…题目内容
实现一个 LRUCache 类三个接口
LRUCache(int capacity) 创建一个大小为 capacity 的缓存get(int key) 从缓存中获取键为 key 的键值对的 valueput(int key, int value) 向缓存中添加键值对 (key, value)
要求 get 和 put 的均摊时间复杂度为 O ( 1 ) O(1) O(1)
题解
对于 get 操作我们需要快速获取到 key 对应的键值对哈希表可以解决。 对于 put 操作我们需要快速 put 一个键值对也可以用哈希表解决。
但是问题在于我们 get 和 put 时需要维护键值对最近使用的情况。
这部分我们可以用双向链表维护每次操作一个键值对时将其从原来链表的位置中移除重新添加到链表头。定义链表头的数据是最近一次使用的链表尾是最近最少使用的。
对于哈希表键可以为 key 映射到一个链表结点 LRUNode LRUNode 中包括前后链表结点以及当前链表结点的 key 和 value 。 为什么我们要在链表结点中存储 key 呢直接看上去没什么用。 考虑我们需要利用 LRU 策略从缓存中弹出一个最近最少使用的结点。 根据我们的定义链表尾的结点是最近最少使用的除了要将其从链表中移除还需要将其从哈希表中移除而从哈希表中移除需要使用 key 这才是链表结点中存储 key 的原因。 定义LRU中的链表结点 LRUNode 。
struct LRUNode {LRUNode* prev;LRUNode* next;int key;int val;LRUNode(int key, int val): key(key), val(val), prev(nullptr), next(nullptr) {}
};对于 LRUNode 其会从链表中被移除也会被添加到链表所以需要实现这两个方法
void removeLRUNodeFromLinklist(LRUNode* node) {node-prev-next node-next;node-next-prev node-prev;
}void insertLRUNodeToLinklist(LRUNode* node) {node-next head-next;head-next-prev node;head-next node;node-prev head;
}对于 LRUNode 其会从哈希表 key2LRUNode 中被移除也会被添加到哈希表 key2LRUNode所以需要实现这两个方法
void removeLRUNodeFromHashTable(LRUNode* node) {if (!key2LRUNode.count(node-key)) return;key2LRUNode.erase(node-key);
}void insertLRUNodeToHashTable(LRUNode* node) {key2LRUNode[node-key] node;
}接下来实现 get 的逻辑
int get(int key) {// key 不存在if (!key2LRUNode.count(key)) return -1;// 取出 key 对应的 LRUNodeLRUNode* node key2LRUNode[key];// 当前 LRUNode 是最近一次使用的将其放到链表头removeLRUNodeFromLinklist(node);insertLRUNodeToLinklist(node);return node-val;
}继续实现 put 的逻辑
void put(int key, int value) {// 如果不存在 key 则需要新建该键值对if (!key2LRUNode.count(key)) {// 缓存已满要从缓存中通过LRU策略弹出最近最少使用的LRUNodeif (size_ capacity_) {// 链表尾即最近最少使用的LRUNode* node tail-prev;// 从链表中删去removeLRUNodeFromLinklist(node);// 从哈希表中删去removeLRUNodeFromHashTable(node);// 释放 node 的内存空间如果是智能指针就不需要手动释放了delete node;// 释放一个空间size_ - 1;}// 创建一个新的 LRUNodeLRUNode* newLRUNode new LRUNode(key, value);// 添加到链表中insertLRUNodeToLinklist(newLRUNode);// 添加到哈希表中insertLRUNodeToHashTable(newLRUNode);size_ 1;} else {// 获取到 key 对应的已存在于缓存中的 LRUNode 节点LRUNode* node key2LRUNode[key];// 更新键值对的权值node-val value;// 从链表中删去removeLRUNodeFromLinklist(node);// 添加到链表中insertLRUNodeToLinklist(node);// 添加到哈希表中其实这步是不需要的因为哈希表对应的是 LRUNode 的地址insertLRUNodeToHashTable(node);// 这里只是 key 对应的 value 修改了size_ 不变}
}
