首页 > 代码库 > LeetCode: LRU Cache [146]
LeetCode: LRU Cache [146]
【题目】
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get
and set
.
get(key)
- Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value)
- Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
【题意】
实现LRU策略取相应的key-value
插入key-value是,需要删除LRU的item
【思路】
维护一个Map记录对应的<key, value>对为了模拟key的访问先后关系,需要维护一个访问次序列表,越靠后的节点,访问时间距当前时间越短
而在insert或者访问key的时候,需要从列表中找到对应的key,并把它调整到列表为。
这里遇到两个问题,一个是查找,另一个是移动到末尾
如果使用顺序表,查找O(n),移动O(n),在cache规模很大时时间代价过高
因此这里使用双向链表来处理
【代码】
struct Node{ int key; int val; Node*prev; Node*next; Node(int k, int v): key(k), val(v){ prev=NULL; next=NULL; } }; class LRUCache{ private: Node* head; Node* tail; int capacity; map<int, Node*>cache; public: LRUCache(int capacity) { this->head = NULL; this->tail = NULL; this->capacity = capacity; } void move2tail(Node* node){ if(node==tail)return; if(node==head){ head = node->next; head->prev=NULL; tail->next=node; node->prev=tail; tail=node; tail->next=NULL; } else{ node->prev->next = node->next; node->next->prev = node->prev; tail->next=node; node->prev=tail; tail=node; tail->next=NULL; } } int get(int key) { if(this->cache.find(key)==this->cache.end())return -1; move2tail(this->cache[key]); return this->cache[key]->val; } void set(int key, int value) { if(this->cache.find(key)==this->cache.end()){//cache中还没有 if(this->capacity==0){//cache已经满了 //删除头结点 this->cache.erase(head->key); head=head->next; if(head)head->prev=NULL; else tail=NULL; } else{//cache还没满 this->capacity--; } //添加新节点 Node* newNode=new Node(key, value); this->cache[key]=newNode; if(tail){ tail->next=newNode; newNode->prev=tail; tail=newNode; tail->next=NULL; } else{ head=tail=newNode; } } else{//cache中已经有了 this->cache[key]->val = value; move2tail(this->cache[key]); } } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。