LRU Cache--LeetCode
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; };
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。