Description
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache. Implement get and put methods with O(1) time complexity. Return the result as an integer.
Examples
Input:
capacity = 2, operations = [put(1,1), put(2,2), get(1), put(3,3), get(2)]Output:
[1,-1]Explanation:
get(1) returns 1 after the first eviction, and get(2) returns -1 because key 2 was evicted, so the result is [1,-1].
Input:
capacity = 1, operations = [put(5,10), put(7,20), get(5), get(7)]Output:
[-1, 20]Explanation:
With capacity 1, key 5 is evicted when key 7 is inserted, so the result is [-1,20].
Input:
capacity = 3, operations = [put(1,100), put(2,200), put(3,300), get(1), put(4,400), get(2), get(3), get(4)]Output:
[100, -1, 300, 400]Explanation:
After inserting keys 1, 2, 3, and 4, key 2 is evicted, so the result is [100,-1,300,400].
Constraints
- •
1 ≤ capacity ≤ 3000 - •
0 ≤ key ≤ 10⁴ - •
0 ≤ value ≤ 10⁵