题目链接：https://leetcode.cn/problems/lru-cache/
这道题超出时间限制了，原因应该是时间复杂度是O(n)不是O(1)，用list保存缓存的key列表，调换list里面元素的顺序比较慢。
等我看官方题解更新吧。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
// 正确版本 class DListNode { public: DListNode* prev; DListNode* next; int _key; int _value; DListNode(): _key(0), _value(0), prev(nullptr), next(nullptr) {} DListNode(int key, int value): _key(key), _value(value), prev(nullptr), next(nullptr) {} }; class LRUCache { public: int cap; int size; unordered_map<int, DListNode*> cache; DListNode* head; DListNode* tail; LRUCache(int capacity) { cap = capacity; head = new DListNode(); tail = new DListNode(); head->next = tail; tail->prev = head; size = 0; } int get(int key) { // hint if (cache.count(key) > 0) { moveToHead(cache[key]); return cache[key]->_value; } // miss return -1; } void put(int key, int value) { // update if (cache.count(key) > 0) { DListNode* node = cache[key]; node->_value = value; moveToHead(node); return; } // insert ++size; if (size > cap) { int key = tail->prev->_key; removeNode(cache[key]); cache.erase(key); --size; } DListNode* node = new DListNode(key, value); cache[key] = node; addToHead(node); } void removeNode(DListNode* node) { node->prev->next = node->next; node->next->prev = node->prev; } void addToHead(DListNode* node) { node->next = head->next; head->next->prev = node; node->prev = head; head->next = node; } void moveToHead(DListNode* node) { removeNode(node); addToHead(node); } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */ |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 |
// 时间复杂度过高版本 class LRUCache { public: int cap; unordered_map<int, int> cache; list<int> l; LRUCache(int capacity) { cap = capacity; } int get(int key) { if (cache.count(key) > 0) { l.remove(key); l.push_front(key); return cache[key]; } return -1; } void put(int key, int value) { l.remove(key); l.push_front(key); while (l.size() > cap) { if (cache.count(key) == 0) { cache.erase(l.back()); } l.pop_back(); } cache[key] = value; } }; /** * Your LRUCache object will be instantiated and called as such: * LRUCache* obj = new LRUCache(capacity); * int param_1 = obj->get(key); * obj->put(key,value); */ |
