首页 > 代码库 > 【Leetcode】LRU Cache
【Leetcode】LRU Cache
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.
双向链表 + hash map
1 class LRUCache{ 2 public: 3 LRUCache(int capacity) { 4 this->capacity = capacity; 5 } 6 7 int get(int key) { 8 if (cache_map.find(key) != cache_map.end()) { 9 cache_list.splice(cache_list.begin(), cache_list, cache_map[key]);10 cache_map[key] = cache_list.begin();11 return cache_map[key]->value;12 } else {13 return -1;14 }15 }16 17 void set(int key, int value) {18 if (cache_map.find(key) != cache_map.end()) {19 cache_list.splice(cache_list.begin(), cache_list, cache_map[key]);20 cache_map[key] = cache_list.begin();21 cache_map[key]->value =http://www.mamicode.com/ value;22 } else {23 if (cache_list.size() == capacity) {24 cache_map.erase(cache_list.back().key);25 cache_list.pop_back();26 }27 cache_list.push_front(cacheNode(key, value));28 cache_map[key] = cache_list.begin();29 }30 }31 private:32 struct cacheNode {33 int key;34 int value;35 cacheNode(int key, int value) : key(key), value(value) {}36 };37 38 int capacity;39 unordered_map<int, list<cacheNode>::iterator> cache_map;40 list<cacheNode> cache_list;41 };
【Leetcode】LRU Cache
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。