[leetcode] 146. LRU Cache

[leetcode] 146. LRU Cache

感想

这道题在leetcode是hard的难度，通过率只有21.2%，我记得在某次笔试的时候做到了这一道题，那时候做得不怎么好，我这里把记录一下我以前写的代码，就当复习一下

题目

Design and implement a data structure for ​​Least Recently Used (LRU) cache​​​. It should support the following operations: ​​get​​​ and ​​put​​.

​​get(key)​​​ - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.​​​put(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.

Follow up: Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );cache.put(1, 1);cache.put(2, 2);cache.get(1); // returns 1cache.put(3, 3); // evicts key 2cache.get(2); // returns -1 (not found)cache.put(4, 4); // evicts key 1cache.get(1); // returns -1 (not found)cache.get(3); // returns 3cache.get(4); // returns 4

代码

class LRUCache {private: list> cache; int size; unordered_map>::iterator> hash;public: LRUCache(int capacity) { size=capacity; } int get(int key) { auto it=hash.find(key); if(it==hash.end()) return -1; cache.splice(cache.begin(),cache,it->second); return it->second->second; } void put(int key, int value) { auto it=hash.find(key); if(it!=hash.end()){ it->second->second=value; cache.splice(cache.begin(),cache,it->second); return; } cache.insert(cache.begin(),make_pair(key,value)); hash[key]=cache.begin(); if(cache.size()>size){ hash.erase(cache.back().first); cache.pop_back(); } }};/** * 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); */

analysis

如果来了一个get请求, 我们仍然先去查hash表, 如果key存在hash表中, 那么需要将这个结点在链表的中的位置移动到链表首部.否则返回-1.

另外一个非常关键的降低时间复杂度的方法是在hash中保存那个key在链表中对应的指针, 我们知道链表要查找一个结点的时间复杂度是O(n), 所以当我们需要移动一个结点到链表首部的时候, 如果直接在链表中查询那个key所对于的结点, 然后再移动, 这样时间复杂度将会是O(n), 而一个很好的改进方法是在hash表中存储那个key在链表中结点的指针, 这样就可以在O(1)的时间内移动结点到链表首部.

STL技巧：

1、使用map的find方法来判断key是否已经存在,返回值和map的end迭代器比较；

2、使用unordered_map,它是hash_map,存取时间都是O(1),用它存储元素的position迭代器,是为了方便splice函数调用list.splice(position, list, element_pos)函数作用是把list的element_pos处的元素插入到position位置,本题中为了移动元素到list头部

reference

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。