Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement the LRUCache class with get(key) and put(key, value) methods. Both operations must run in O(1) average time complexity. Return the result as a string.
Examples
Input:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]Output:
[null, null, null, 1, null, -1, null, -1, 3, 4]Explanation:
Cache capacity is 2. Operations demonstrate LRU eviction.
Input:
["LRUCache", "put", "put", "put", "get", "put", "get", "get", "put", "get", "get"] [[3], [5, 50], [6, 60], [7, 70], [5], [8, 80], [6], [7], [9, 90], [5], [8]]Output:
[null, null, null, null, 50, null, -1, 70, null, -1, 80]Explanation:
With capacity 3, the access pattern evicts key 6 and later key 5, so the result is [null,null,null,null,50,null,-1,70,null,-1,80].
Input:
["LRUCache", "put", "get", "put", "get", "get", "put", "get", "get"] [[1], [10, 100], [10], [20, 200], [10], [20], [30, 300], [20], [30]]Output:
[null, null, 100, null, -1, 200, null, -1, 300]Explanation:
With capacity 1, each new put evicts the previous key, so the result is [null,null,100,null,-1,200,null,-1,300].
Constraints
- •
1 ≤ capacity ≤ 3000 - •
0 ≤ key ≤ 10⁴ - •
0 ≤ value ≤ 10⁵