Leetcode: LRU Cache

转自:http://blog.csdn.net/doc_sgl/article/details/15378513

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.


模拟的方法:Time Limit Exceeded

[cpp]  view plain copy print ?
  1. struct node{  
  2.         int key;  
  3.         int value;  
  4.         int time;  
  5.         node():key(0),value(0),time(0){};  
  6.         node(int k, int v):key(k),value(v),time(0){};  
  7.     };  
  8.   
  9.     class LRUCache{  
  10.         map<intint> mp;//mp<key, index>  
  11.         vector<node> lru; //= new vector<node>(100);  
  12.         vector<int> v(int); //= new vector<int>(1000);  
  13.         int size;  
  14.         int capacity;  
  15.     public:  
  16.     LRUCache(int c) {  
  17.         if(c < 1)return;  
  18.         //vector<node> lru(c);  
  19.         lru.clear();  
  20.         mp.clear();  
  21.         size = 0;  
  22.         capacity = c;  
  23.         //cout<<"capacity:"<<capacity<<endl;  
  24.     }  
  25.       
  26.     int get(int k) {  
  27.         map<intint>::iterator it = mp.find(k);  
  28.         if(it != mp.end())  
  29.             return lru[(*it).second].value;  
  30.         else  
  31.             return -1;  
  32.     }  
  33.       
  34.     void set(int k, int val) {  
  35.         if(capacity < 1)return;  
  36.         map<intint>::iterator it = mp.find(k);  
  37.         if(it != mp.end())//find  
  38.         {  
  39.             lru[(*it).second].value = val;  
  40.             lru[(*it).second].time = 0;  
  41.             for(int i = 0; i < size; i++)  
  42.                 if(lru[i].key != k)  
  43.                     lru[i].time ++;  
  44.         }else{//not find  
  45.             if(size < capacity){//size < capacity  
  46.                 node* tmp = new node(k,val);  
  47.                 lru.push_back(*tmp);  
  48.                 /*lru[size].key = k; 
  49.                 lru[size].value = val; 
  50.                 lru[size].time = 0;*/  
  51.                 for(int i = 0; i < size; i++)  
  52.                     lru[i].time++;  
  53.                 mp[k] = size;  
  54.                 size++;  
  55.             }else{//size >= capacity  
  56.                 int mxtime = lru[0].time;  
  57.                 int mxtimeindex = 0;  
  58.                 for(int i = 0; i < size; i++){  
  59.                     if(lru[i].time > mxtime)  
  60.                         mxtimeindex = i;  
  61.                     lru[i].time++;  
  62.                 }  
  63.                 it = mp.find(lru[mxtimeindex].key);  
  64.                 mp.erase(it);  
  65.                 lru[mxtimeindex].key = k;  
  66.                 lru[mxtimeindex].value = val;  
  67.                 lru[mxtimeindex].time = 0;  
  68.                 mp[k] = mxtimeindex;  
  69.             }  
  70.         }  
  71.     }  
  72. };  

改进Accepted

使用map+双向链表,复杂度是O(logN)

链表头部的表示刚刚访问过的,链表尾部的表示很久之前访问的

每次get(key),先在map中找到这个节点,然后把这个节点放到链表头部。

每次set(key, value),现在map中找这个节点,如果有的话就把这个节点放到链表头部,如果没有就看看cache空间是否已经满了,size>=capacity,如果未满,就生成一个新的节点放到链表头部,如果满了,就生成一个新的节点放到链表头部并且删除链表尾部的一个节点。

[cpp]  view plain copy print ?
  1. struct node {  
  2.     node* pre;  
  3.     int key;  
  4.     int value;  
  5.     node* next;  
  6.     node(int k, int v):key(k),value(v),pre(NULL),next(NULL) {};  
  7. };  
  8.   
  9. class LRUCache {  
  10.     map<int, node*> mp;  
  11.     node* head;  
  12.     node* tail;  
  13.     int size;  
  14.     int capacity;  
  15. public:  
  16.     LRUCache(int c) {  
  17.         if (c < 1)return;  
  18.         head = new node(0, 0);  
  19.         tail = new node(0, 0);  
  20.         head->next = tail;  
  21.         tail->pre = head;  
  22.         mp.clear();  
  23.         size = 0;  
  24.         capacity = c;  
  25.     }  
  26.   
  27.     int get(int k) {  
  28.         map<int, node*>::iterator it = mp.find(k);  
  29.         if (it != mp.end()) {  
  30.             node* cur = (*it).second;  
  31.             cur->pre->next = cur->next;  
  32.             cur->next->pre = cur->pre;  
  33.             putToHead(cur);  
  34.             return cur->value;  
  35.         } else  
  36.             return -1;  
  37.     }  
  38.   
  39.     void set(int k, int val) {  
  40.         if (capacity < 1)return;  
  41.         map<int, node*>::iterator it = mp.find(k);  
  42.         if (it != mp.end()) {//find  
  43.             node* cur = (*it).second;  
  44.             cur->pre->next = cur->next;  
  45.             cur->next->pre = cur->pre;  
  46.             cur->value = val;  
  47.             putToHead(cur);  
  48.         } else {//not find  
  49.             node* tmp = new node(k,val);  
  50.             putToHead(tmp);  
  51.             mp[k] = tmp;  
  52.             if (size < capacity) {//size < capacity  
  53.                 size++;  
  54.             } else {//size >= capacity  
  55.                 node* deltmp = tail->pre;  
  56.                 tail->pre = deltmp->pre;  
  57.                 deltmp->pre->next = tail;  
  58.                 it = mp.find(deltmp->key);  
  59.                 mp.erase(it);  
  60.                 delete deltmp;  
  61.             }  
  62.         }  
  63.     }  
  64.     void putToHead(node* cur)  
  65.     {  
  66.         cur->next = head->next;  
  67.         cur->pre = head;  
  68.         cur->next->pre = cur;  
  69.         head->next = cur;  
  70.     }  
  71.   
  72. };  

Hash+双向链表O(1):

[cpp]  view plain copy print ?
  1. struct node{  
  2.     node* pre;  
  3.     int key;  
  4.     int value;  
  5.     node* next;  
  6.     node(int k, int v):key(k),value(v),pre(NULL),next(NULL){};  
  7. };  
  8.   
  9. class LRUCache{  
  10.     unordered_map<int, node*> mp;  
  11.     int capacity;  
  12.     int size;  
  13.     node* head;  
  14.     node* tail;  
  15. public:  
  16. LRUCache(int c){  
  17.     if(c<0)return;  
  18.     head = new node(-1,-1);  
  19.     tail = new node(-1,-1);  
  20.     head->next = tail;  
  21.     tail->pre = head;  
  22.     mp.clear();  
  23.     capacity = c;  
  24.     size = 0;  
  25. }  
  26.       
  27. int get(int k) {  
  28.     unordered_map<int, node*>::iterator it = mp.find(k);  
  29.     if(it != mp.end()){  
  30.         node* p = it->second;  
  31.         p->pre->next = p->next;  
  32.         p->next->pre = p->pre;  
  33.         putToHead(p);  
  34.         return p->value;  
  35.     }  
  36.     else  
  37.         return -1;  
  38. }  
  39.       
  40. void set(int k, int val) {  
  41.     if(capacity < 1) return;   
  42.     unordered_map<int, node*>::iterator it = mp.find(k);  
  43.     if(it != mp.end()){  
  44.         node* p = it->second;  
  45.         p->pre->next = p->next;  
  46.         p->next->pre = p->pre;  
  47.         putToHead(p);  
  48.         p->value = val;  
  49.     }else{  
  50.         node* p = new node(k, val);  
  51.         putToHead(p);  
  52.         mp[k] = p;  
  53.         size++;  
  54.         if(size>capacity){  
  55.             p = tail->pre;  
  56.             tail->pre = p->pre;  
  57.             p->pre->next = tail;  
  58.             it = mp.find(p->key);  
  59.             mp.erase(it);  
  60.             delete p;  
  61.         }  
  62.     }  
  63. }  
  64.   
  65. void putToHead(node* p)  
  66. {  
  67.     p->next = head->next;  
  68.     p->pre = head;  
  69.     head->next->pre = p;  
  70.     head->next = p;  
  71. }  
  72. };  

你可能感兴趣的