Problem
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache
class:
LRUCache(int capacity)
Initialize the LRU cache with positive sizecapacity
.int get(int key)
Return the value of thekey
if the key exists, otherwise return-1
.void put(int key, int value)
Update the value of thekey
if thekey
exists. Otherwise, add thekey-value
pair to the cache. If the number of keys exceeds thecapacity
from this operation, evict the least recently used key.
The functions get
and put
must each run in O(1)
average time complexity.
Example 1:
1 | Input |
Constraints:
1 <= capacity <= 3000
0 <= key <= 104
0 <= value <= 105
- At most 2
* 105
calls will be made toget
andput
.
Analysis
这题要求实现一个LRU Cache,有一些基本的要求。首先是get
和put
的时间复杂度都要求是$O(1)$,所以这里很明显就要用到hashmap了。然后LRU一个最主要的特点就是,当缓存满了之后,需要淘汰到最少使用的一个key,因此这里我选用了list,主要是维护一个顺序。
list的选用比较简单,只需要记录一个pair<int,int>
,包含key和value;hashmap的选用就需要仔细思考了,因为要通过key获取到,所以key肯定就是用户传入的key,但是value就不能是用户传入的value。因为在用户访问key的时候,需要调整list的顺序,所以这里要存的是iterator,可以直接访问到list中相对应的位置。
对get
方法,先在hashmap中查询key是否存在,如果不存在直接返回-1,如果存在的话就返回value,同时利用iterator调整在list中的位置,把对应的value调整到list中第一个位置。
对于put
方法,先在hashmap中查询key是否存在,如果存在则先从list中删掉,然后统一添加到队头。此时需要更新hashmap中的迭代器,因为是插入到队头,所以只需要去第一个元素的迭代器即可。这里还需要处理超出cache大小的情况,因为要淘汰掉list末尾的元素,所以只需要删除掉最后一个元素,并且在hashmap中删除对应的key即可。
Solution
无
Code
1 | class LRUCache { |
Summary
这道题目是一道非常经典的面试题,首先LRU本身就是一个很基础的算法,同时在实现过程中考察到了list、hashmap的使用。这道题目的分享到这里,感谢你的支持!