全球军事局势最新消息,惠州seo整站优化,wordpress文章归档,成都效果图制作公司排行榜题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类#xff1a; LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中#xff0c;则返回关键字的值#xff0c;否则…题目描述 请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。 实现 LRUCache 类 LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存 int get(int key) 如果关键字 key 存在于缓存中则返回关键字的值否则返回 -1 。 void put(int key, int value) 如果关键字 key 已经存在则变更其数据值 value 如果不存在则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity 则应该 逐出 最久未使用的关键字。 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。
示例 示例 输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 输出 [null, null, null, 1, null, -1, null, -1, 3, 4]
解释 LRUCache lRUCache new LRUCache(2); lRUCache.put(1, 1); // 缓存是 {11} lRUCache.put(2, 2); // 缓存是 {11, 22} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 该操作会使得关键字 2 作废缓存是 {11, 33} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 该操作会使得关键字 1 作废缓存是 {44, 33} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4
解题思想 1、使用双向链表 2、使用HashMap 将最近使用的放到链表头部如果超过容量就将最尾部的删除掉。
代码
class LRUCache {
public://定义双向链表struct Node {int key, val;Node* next, * prev;Node(): key(0), val(0), prev(nullptr), next(nullptr){};Node(int _key,int _val):key(_key),val(_val), prev(nullptr), next(nullptr) {};};//链表的首尾节点Node* head, *tail;//key和结点的映射关系unordered_mapint, Node* umap;int capacity,size; //容量大小和已经使用的大小LRUCache(int capacity) {//初始化this-capacity capacity;this-size 0;head new Node();tail new Node();head-next tail;tail-prev head;}int get(int key) {//如果不存在返回-1if (!umap.count(key))return -1;Node* node umap[key];removeNode(node);addNodeToHead(node);return node-val;}void put(int key, int value) {//如果链表中key存在,就修改value的值,然后再插入到表头if (umap.count(key)) {Node* node umap[key];node-val value;removeNode(node);addNodeToHead(node);}//如果不存在else {//如果容量不够,就先删除最久未使用的然后再创建一个新的结点if (capacity size) {Node* removed tail-prev;//从哈希表中删除最久未访问的umap.erase(removed-key);//从链表中也删除removeNode(removed);size--;}//新创建一个节点Node* node new Node(key, value);addNodeToHead(node);umap[key] node;size;}}//删除当前节点void removeNode(Node* node) {node-prev-next node-next;node-next-prev node-prev;}//添加到表头void addNodeToHead(Node* node) {node-prev head;node-next head-next;head-next-prev node;head-next node;}
};
