A cache keeps a small number of items so that you can read them fast. When the cache is full and a new item arrives, it must throw out one item. In a Least Recently Used (LRU) cache, the item that was used longest ago is thrown out.
Build the class LRUCache:
LRUCache(int capacity) creates a cache that can hold capacity keys. The capacity is positive.int get(int key) returns the value stored for key, or -1 if the key is not in the cache. Reading a key counts as using it.void put(int key, int value) stores the pair. If the key already exists, update its value. If the cache then holds more keys than capacity, remove the least recently used key.
Both get and put must run in O(1) average time.
Examples
Example 1:
Input
["LRUCache","put","put","get","put","get","get"]
[[2],[5,50],[6,60],[5],[7,70],[6],[7]]
Output
[null,null,null,50,null,-1,70]
Explanation
LRUCache cache = new LRUCache(2);
cache.put(5, 50); // cache: {5=50}
cache.put(6, 60); // cache: {5=50, 6=60}
cache.get(5); // returns 50, key 5 is now the most recently used
cache.put(7, 70); // the cache is full, so the least recently used key 6 is removed
cache.get(6); // returns -1
cache.get(7); // returns 70
Example 2:
Input
["LRUCache","put","put","put","put","get","get"]
[[2],[1,1],[2,2],[1,100],[3,3],[2],[1]]
Output
[null,null,null,null,null,-1,100]
Explanation
Updating key 1 with put(1, 100) counts as using it. So when key 3 arrives, key 2 is the one that is removed.