LRU Cache--LeetCode

快来打我* 2022-08-07 13:51 82阅读 0赞

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这里涉及是用向量记录内存地址，使用Map映射key和相应Key在向量中的映射，最前面的永远都是最新的，如果内存没有使用完，使用新的内存，如果使用完了，从第一个内存更新，然后将第一块内存放到最后一块中，需要注意的是这里需要map的信息。

class LRUCache{
    public:
        LRUCache(int capacity) {
           m_capacity=capacity;
           m_size =0;
           for(int i=0;i<capacity;i++)
           {
             int* temp = (int*)malloc(sizeof(int));
             *temp =0;
             m_cache.push_back(temp);                    
           }
             
        }
        
        int get(int key) {
            map<int,int>::iterator itr=m_hash.find(key);
           
            if(itr == m_hash.end())
              return -1;
            else
              return *(m_cache[itr->second]);
        }
        
        void set(int key, int value) {
           map<int,int>::iterator itr=m_hash.find(key);
           map<int,int>::iterator index;
           if(itr == m_hash.end()) //没有找到 
           {
               if(m_size < m_capacity)
               {
                  *m_cache[m_size] = value;
                  m_hash.insert(pair<int,int>(key,m_size));
                  m_size++;
               }
               else
               {
                  for(index=m_hash.begin();index!=m_hash.end();index++)
                   if(index->second ==0)
                      itr = index;
                   else
                      index->second--;           
                  m_hash.erase(itr);
                  int* temp = m_cache[0];
                  m_cache.erase(m_cache.begin());
                  *temp = value;
                  m_cache.push_back(temp);
                  m_hash.insert(pair<int,int>(key,m_cache.size()-1)); 
               }   
           }
           else
           {
              int* temp = m_cache[itr->second];
              *m_cache[itr->second] = value;
              m_cache.erase(m_cache.begin()+itr->second);
              m_cache.push_back(temp);
              for(index=m_hash.begin();index != m_hash.end();index++)
                 if(index->second > itr->second)
                   index->second--;
              itr->second =  m_cache.size()-1;
           }   
        }
        ~LRUCache()
        {
           for(int i=0;i<m_capacity;i++)
             free(m_cache[i]);
        }
        private:
                int m_capacity;
                int m_size;
                vector<int*> m_cache;
                map<int,int> m_hash;
    };

分析：上面的方法有一定的缺陷，时间复杂度相对都是很高的，对于这种的Cache系统，如果能在O（1）时间复杂度就好了，对于存储对象的数据结构可以使用向量或者链表，链表可以随机插入，向量可以随机获取，那么可以通过hash将两者的优点融合。hash记录节点的位置，这里使用双向链表更好，为了省去一些操作，使用双向循环链表更好。

template <typename T>
    class DList
    {
    public:
           DList()
           {
              pre=NULL;
              next=NULL;
           }
           DList<T>* pre;
           DList<T>* next;
           T value;
           };  
    class LRUCache{
          public:
                 LRUCache(int capacity)
                 {
                    m_size=0;
                    m_capacity = capacity;  
                    first = NULL;
                 }
                 void set(int key,int value)
                 {
                      hash_map<int,DList<int>* >::iterator itr = m_hash.begin();
                      DList<int>* temp;
                      itr = m_hash.find(key);
                      
                      if(itr != m_hash.end()) //找到了  新的放到最后 
                      {
                         temp = itr->second;
                         temp->value = value;
                         if(temp == first)
                           first = first->next;
                         else
                         {
                          temp->pre->next = temp->next;
                          temp->next->pre = temp->pre;
                          temp->next = first;
                          temp->pre = first->pre;
                          first->pre->next = temp;
                          first->pre = temp;
                         }                    
                      }
                      else
                      {                
                          if(m_size < m_capacity) //还有空间 
                          {
                             temp = new DList<int>;
                             temp->value = value;
                             if(first == NULL)
                             {
                                first = temp;
                                first->next = temp;
                                first->pre = temp;
                                temp->next = temp;
                                temp->pre = temp;
                             }
                             else
                             {                                                       
                                 temp->next = first;
                                 temp->pre = first->pre;
                                 first->pre->next = temp;
                                 first->pre = temp;
                             }                        
                             m_size++;                   
                          }
                          else   //没有空间  
                          {
                            first->value = value;
                            first = first->next;
                          }
                      } 
                 }
                 int get(int key)
                 {
                    hash_map<int,DList<int>* >::iterator itr = m_hash.begin();
                    itr = m_hash.find(key);
                    if(itr == m_hash.end())
                      return -1;
                     else
                       return itr->second->value; 
                 }
          private:
                  int m_size;
                  int m_capacity;
                  hash_map<int,DList<int>* > m_hash;
                  DList<int>* first;
    };