首页 > 代码库 > Leetcode：LRUCache四个版本实现
Leetcode：LRUCache四个版本实现
题目
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.
链接：https://oj.leetcode.com/problems/lru-cache/
分析
1：维护最近最少（LRU）使用的cache
1）使用count计数，每次操作cache时（get、set），该cache的count置0，其余cache的count加1，count最大的为最近最少使用的cache
2）使用链表，每次操作cache时（get、set），将该cache移动至链表头，链表尾的cache为最近最少使用的cache
2：快速查找cache
1）使用stl::unordered_map存储cache地址（内部hashTable）
版本一
使用std::list维护LRU，链表中存储cache实际空间。Runtime: 248ms。
1 #include <list> 2 #include <unordered_map> 3 4 struct KeyValue { 5 KeyValue(int pKey, int pValue):key(pKey), value(pValue) {}; 6 int key; 7 int value; 8 }; 9 10 class LRUCache{11 public:12 LRUCache(int capacity):_capacity(capacity) {};13 14 int get(int key);15 void set(int key, int value);16 17 private:18 std::unordered_map<int, std::list<KeyValue>::iterator> keyToNodeItr;19 std::list<KeyValue> lru;20 21 int _capacity;22 };23 24 void LRUCache::set(int key, int value) {25 auto itr = keyToNodeItr.find(key);26 if (itr != keyToNodeItr.end()) { // set value27 itr->second->value =http://www.mamicode.com/ value;28 KeyValue tmp(itr->second->key, itr->second->value);29 keyToNodeItr.erase(itr->second->key);30 lru.erase(itr->second);31 lru.push_front(tmp);32 } else { // insert value33 if (lru.size() != _capacity) {34 lru.push_front(KeyValue(key, value));35 } else {36 // pop back lru37 if (lru.size() != 0) {38 keyToNodeItr.erase((lru.rbegin())->key);39 lru.pop_back();40 }41 lru.push_front(KeyValue(key, value));42 }43 }44 45 keyToNodeItr.insert(std::pair<int, std::list<KeyValue>::iterator>(key, lru.begin()));46 }47 48 int LRUCache::get(int key) {49 auto itr = keyToNodeItr.find(key);50 if (itr != keyToNodeItr.end()) {51 int value = http://www.mamicode.com/itr->second->value;52 53 KeyValue tmp(itr->second->key, itr->second->value);54 keyToNodeItr.erase(itr->second->key);55 lru.erase(itr->second);56 lru.push_front(tmp);57 keyToNodeItr.insert(std::pair<int, std::list<KeyValue>::iterator>(key, lru.begin()));58 59 return value;60 }61 return -1;62 }
因为链表中存储的为cache的实际空间，因此当需要改变cache的位置时，链表及map都需要改变，开销较大。
版本二
使用std::list维护LRU，链表中存储cache的指针。Runtime：186ms。
1 #include <list> 2 #include <unordered_map> 3 4 struct KeyValue { 5 KeyValue(int pKey, int pValue):key(pKey), value(pValue) {}; 6 int key; 7 int value; 8 }; 9 10 class LRUCache{11 public:12 LRUCache(int capacity):_capacity(capacity) {};13 14 int get(int key);15 void set(int key, int value);16 17 ~LRUCache();18 19 private:20 std::unordered_map<int, std::list<KeyValue*>::iterator> keyToNodeItr;21 std::list<KeyValue*> lru;22 23 int _capacity;24 };25 26 LRUCache::~LRUCache() {27 for (auto itr = lru.begin(); itr != lru.end(); ++itr) {28 delete *itr;29 }30 }31 32 void LRUCache::set(int key, int value) { 33 auto itr = keyToNodeItr.find(key);34 if (itr != keyToNodeItr.end()) { // set value35 KeyValue* tmp = *(itr->second);36 tmp->value =http://www.mamicode.com/ value;37 lru.erase(itr->second);38 lru.push_front(tmp);39 itr->second = lru.begin(); // avoid invalid iterator40 } else { // insert value41 if (lru.size() == _capacity) { // pop back lru42 KeyValue* tmp = *(lru.rbegin());43 keyToNodeItr.erase(tmp->key);44 delete tmp;45 lru.pop_back();46 }47 lru.push_front(new KeyValue(key, value));48 keyToNodeItr.insert(std::pair<int, std::list<KeyValue*>::iterator>(key, lru.begin()));49 }50 }51 52 int LRUCache::get(int key) {53 auto itr = keyToNodeItr.find(key);54 if (itr != keyToNodeItr.end()) {55 KeyValue* kvPtr = *(itr->second);56 lru.erase(itr->second);57 lru.push_front(kvPtr);58 itr->second = lru.begin();59 return kvPtr->value;60 }61 return -1;62 }
需要注意的问题是map中存储的为list的迭代器，因此map中仍需要重新设置key到迭代器的映射，避免迭代器失效。
版本三
似乎std::list太笨重了，so实现轻量级双链表代替std::list。Runtime: 77ms。
1 struct BiListNode { 2 BiListNode() {}; 3 BiListNode(int key, int value):key(key), value(value) {}; 4 int key; 5 int value; 6 BiListNode* pre; 7 BiListNode* next; 8 }; 9 10 class BiList { 11 public: 12 BiList():_count(0) { 13 _head = new BiListNode(); 14 _head->pre = _head; 15 _head->next = _head; 16 } 17 18 void push_front(BiListNode* pNode); 19 20 void move_front(BiListNode* pNode); 21 22 BiListNode* begin() { 23 return _head->next; 24 } 25 26 BiListNode* rbegin() { 27 return _head->pre; 28 } 29 30 void pop_back(); 31 32 int size() { return _count; } 33 34 ~BiList(); 35 36 private: 37 BiListNode* _head; 38 int _count; 39 }; 40 41 void BiList::push_front(BiListNode* pNode) { 42 pNode->next = _head->next; 43 pNode->pre = _head; 44 _head->next->pre = pNode; 45 _head->next = pNode; 46 if (_head->pre == _head) { 47 _head->pre = pNode; 48 } 49 ++_count; 50 } 51 52 void BiList::move_front(BiListNode* pNode) { 53 if (pNode == _head->next) { 54 return; 55 } 56 pNode->pre->next = pNode->next; 57 pNode->next->pre = pNode->pre; 58 59 pNode->next = _head->next; 60 pNode->pre = _head; 61 62 _head->next->pre = pNode; 63 64 _head->next = pNode; 65 } 66 67 void BiList::pop_back() { 68 BiListNode* tailPtr = _head->pre; 69 tailPtr->pre->next = _head; 70 _head->pre = tailPtr->pre; 71 delete tailPtr; 72 --_count; 73 } 74 75 BiList::~BiList() { 76 for (BiListNode* itr = _head->next; itr != _head; itr = itr->next) { 77 delete itr; 78 } 79 delete _head; 80 } 81 82 83 class LRUCache { 84 public: 85 LRUCache(int capacity):_capacity(capacity) {}; 86 87 int get(int key); 88 89 void set(int key, int value); 90 91 private: 92 int _capacity; 93 94 BiList biList; 95 std::unordered_map<int, BiListNode*> keyToNodePtr; 96 }; 97 98 int LRUCache::get(int key) { 99 auto itr = keyToNodePtr.find(key);100 if (itr != keyToNodePtr.end()) {101 biList.move_front(itr->second);102 return itr->second->value;103 }104 return -1;105 }106 107 void LRUCache::set(int key, int value) {108 auto itr = keyToNodePtr.find(key);109 if (itr != keyToNodePtr.end()) { // set value110 itr->second->value =http://www.mamicode.com/ value;111 biList.move_front(itr->second);112 } else { // insert113 if (biList.size() == _capacity) {114 keyToNodePtr.erase((biList.rbegin())->key);115 biList.pop_back();116 }117 biList.push_front(new BiListNode(key, value));118 keyToNodePtr.insert(std::pair<int, BiListNode*>(key, biList.begin()));119 }120 }
自己实现的双链表仅有80行代码，代码运行效率大大提高。
版本四
双链表都自己实现了，就死磕到底，再自己实现个开链哈希表吧。Runtime：66ms。
1 struct BiListNode { 2 BiListNode() {}; 3 BiListNode(int key, int value):key(key), value(value) {}; 4 int key; 5 int value; 6 BiListNode* pre; 7 BiListNode* next; 8 }; 9 10 class BiList { 11 public: 12 BiList():_count(0) { 13 _head = new BiListNode(); 14 _head->pre = _head; 15 _head->next = _head; 16 } 17 18 void push_front(BiListNode* pNode); 19 20 void move_front(BiListNode* pNode); 21 22 BiListNode* begin() { 23 return _head->next; 24 } 25 26 BiListNode* rbegin() { 27 return _head->pre; 28 } 29 30 void pop_back(); 31 32 int size() { return _count; } 33 34 ~BiList(); 35 36 private: 37 BiListNode* _head; 38 int _count; 39 }; 40 41 void BiList::push_front(BiListNode* pNode) { 42 pNode->next = _head->next; 43 pNode->pre = _head; 44 _head->next->pre = pNode; 45 _head->next = pNode; 46 if (_head->pre == _head) { 47 _head->pre = pNode; 48 } 49 ++_count; 50 } 51 52 void BiList::move_front(BiListNode* pNode) { 53 if (pNode == _head->next) { 54 return; 55 } 56 pNode->pre->next = pNode->next; 57 pNode->next->pre = pNode->pre; 58 59 pNode->next = _head->next; 60 pNode->pre = _head; 61 62 _head->next->pre = pNode; 63 64 _head->next = pNode; 65 } 66 67 void BiList::pop_back() { 68 BiListNode* tailPtr = _head->pre; 69 tailPtr->pre->next = _head; 70 _head->pre = tailPtr->pre; 71 delete tailPtr; 72 --_count; 73 } 74 75 BiList::~BiList() { 76 for (BiListNode* itr = _head->next; itr != _head; itr = itr->next) { 77 delete itr; 78 } 79 delete _head; 80 } 81 82 struct hashNode { 83 hashNode(int key, BiListNode* ptr):key(key), ptr(ptr), next(NULL) {}; 84 int key; 85 BiListNode* ptr; 86 hashNode* next; 87 }; 88 89 class HashTable { 90 public: 91 HashTable(int capacity); 92 93 hashNode* find(int key); 94 95 void insert(int key, BiListNode* ptr); 96 97 void erase(int key); 98 99 ~HashTable();100 101 private:102 int _capacity;103 hashNode** hashArray;104 };105 106 HashTable::HashTable(int capacity):_capacity(capacity) {107 hashArray = new hashNode*[capacity];108 for (int i = 0; i < _capacity; ++i) {109 hashArray[i] = NULL;110 }111 }112 113 hashNode* HashTable::find(int key) {114 for (hashNode* itr = hashArray[key % _capacity]; itr != NULL;115 itr = itr->next) {116 if (itr->key == key) {117 return itr;118 }119 }120 return NULL;121 }122 123 void HashTable::insert(int key, BiListNode* ptr) {124 hashNode* tmp = new hashNode(key, ptr);125 126 int relativeKey = key % _capacity;127 128 if (hashArray[relativeKey] == NULL) {129 hashArray[relativeKey] = tmp;130 return;131 }132 133 tmp->next = hashArray[relativeKey];134 hashArray[relativeKey] = tmp;135 }136 137 void HashTable::erase(int key) {138 for (hashNode* pre = hashArray[key % _capacity], *itr = pre;139 itr != NULL; pre = itr, itr = itr->next) {140 if (itr->key == key) {141 if (itr != pre)142 pre->next = itr->next;143 else // head144 hashArray[key % _capacity] = itr->next;145 146 delete itr;147 }148 }149 }150 151 HashTable::~HashTable() {152 for (int i = 0; i < _capacity; ++i) {153 for (hashNode* itr = hashArray[i]; itr != NULL;) {154 hashNode* tmp = itr;155 itr = itr->next;156 delete tmp;157 }158 }159 delete [] hashArray;160 }161 162 class LRUCache {163 public:164 LRUCache(int capacity):_capacity(capacity) {165 hashTable = new HashTable(1024);166 };167 168 int get(int key);169 170 void set(int key, int value);171 172 ~LRUCache() { delete hashTable; }173 174 private:175 int _capacity;176 BiList bilist;177 HashTable* hashTable;178 };179 180 int LRUCache::get(int key) {181 hashNode* tmp = hashTable->find(key);182 if (tmp != NULL) {183 bilist.move_front(tmp->ptr);184 return tmp->ptr->value;185 }186 return -1;187 }188 189 void LRUCache::set(int key, int value) {190 hashNode* tmp = hashTable->find(key);191 if (tmp != NULL) { // set192 bilist.move_front(tmp->ptr);193 tmp->ptr->value =http://www.mamicode.com/ value;194 return;195 }196 197 // insert198 if (bilist.size() == _capacity) {199 hashTable->erase((bilist.rbegin())->key);200 bilist.pop_back();201 }202 203 bilist.push_front(new BiListNode(key, value));204 hashTable->insert(key, bilist.begin());205 }
开链哈希表72行代码
Leetcode：LRUCache四个版本实现
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。