首页 > 代码库 > 【leetcode】LRU Cache
【leetcode】LRU Cache
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.
1 st （ 15tries）
class LRUCache{public: int capacity; int length; struct Node { int key; int value; Node *next; Node *pre; }; Node *head; Node *tail; class HashTable { public: unordered_map<int,Node*> innertable; Node *get(int key) { if( innertable.count(key) ) return innertable[key]; return NULL; } bool del(int key) { unordered_map<int,Node*>::iterator iter; iter = innertable.find(key); if(iter != innertable.end()) { innertable.erase(iter); return true; } return false; } bool add(int key,Node *node) { if( !innertable.count(key) ) { innertable[key] = node; return true; } return false; } }; HashTable hashtable; LRUCache(int capacity) { this->capacity = capacity; length = 0; head = new Node(); tail = new Node(); head->next = tail; head->pre = NULL; tail->next = NULL; tail->pre = head; } int get(int key) { Node *tmp = hashtable.get(key); if(tmp == NULL) return -1; else { tmp->pre->next = tmp->next; tmp->next->pre = tmp->pre; tmp->next = head->next; head->next->pre = tmp; head->next = tmp; tmp->pre = head; return tmp->value; } } void set(int key, int value) { Node *tmp = hashtable.get(key); if(tmp != NULL) { tmp->pre->next = tmp->next; tmp->next->pre = tmp->pre; tmp->next = head->next; head->next->pre = tmp; head->next = tmp; tmp->pre = head; tmp->value = http://www.mamicode.com/value;>
2nd （ 11 tries）
class LRUCache{public: struct ListNode { int key; int value; ListNode *pre; ListNode *next; ListNode(int k,int v) { key = k; value = http://www.mamicode.com/v;>
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。