Implement an LRU Cache

Complete the function below. The function receives the full standard input as a single string and must return the exact standard output lines for the described problem. Implement an LRU (Least Recently Used) cache that supports: LRUCache(capacity): initialize the cache with the given positive capacity. get(key): return the value if the key exists and mark it as most recently used; otherwise return -1. put(key, value): insert or update the key with the value and mark it as most recently used; if the cache exceeds capacity, evict the least recently used entry. Requirements: Target time complexity: O(1) per get/put. Constraints Number of operations: 1 ≤ N ≤ 2 * 10⁵ key, value are 32-bit integers Input: capacity=2 put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4) Output: 1 -1 -1 3 4 Input: capacity=1 put(1,1) put(2,2) get(1) get(2) Output: -1 2 Input: capacity=2 put(1,1) put(1,10) get(1) Output: 10 Input: capacity=3 get(42) Output: -1 Input: capacity=2 put(1,1) put(2,2) put(3,3) get(1) get(2) get(3) Output: -1 2 3 Example Input capacity=2 put(1,1) put(2,2) get(1) put(3,3) get(2) put(4,4) get(1) get(3) get(4) Output 1 -1 3 4 Function Description Complete solveLRUCacheOperations. It has one parameter, String input, containing the full stdin payload. Return the stdout payload as an array of lines, without trailing newline characters.

Constraints

Use the limits and requirements stated in the prompt.

Example 1

Input:

input = "capacity=2\nput(1,1)\nput(2,2)\nget(1)\nput(3,3)\nget(2)\nput(4,4)\nget(1)\nget(3)\nget(4)"

Output:

["1", "-1", "-1", "3", "4"]

Explanation: The returned string array must match the expected standard output lines for the sample input.

Source erratum: The first multi-step example omits the -1 returned by get(1) after put(4,4). The repeated Example 1 appended later lists all five results, and replaying with the same LRU rule also gives 1, -1, -1, 3, 4.

输入格式

The first line is capacity=N (a positive integer); each following line is one put(key,value) or get(key) operation.

输出格式

Output one line for each get; put produces no output.

样例 1

输入：

capacity=2
put(1,1)
put(2,2)
get(1)
put(3,3)
get(2)
put(4,4)
get(1)
get(3)
get(4)

输出：

1
-1
-1
3
4

样例 2

输入：

capacity=1
put(1,1)
put(2,2)
get(1)
get(2)

输出：

-1
2

样例 3

输入：

capacity=2
put(1,1)
put(1,10)
get(1)

输出：

10

样例 4

输入：

capacity=3
get(42)

输出：

-1

样例 5

输入：

capacity=2
put(1,1)
put(2,2)
put(3,3)
get(1)
get(2)
get(3)

输出：

-1
2
3

样例说明

Maintain the order from least recently used to most recently used. A get hit and any put (including an update to an existing key) move that key to the most recent end; when over capacity, delete the least recently used key. The first example in the statement omits one -1; the output of the repeated Example 1 in the statement and the step-by-step state both confirm the corrected value.