Topic describes

This is the “146. LRU caching mechanism” on LeetCode with “medium” difficulty.

Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:

  • LRUCache(int capacity) The LRU cache is initialized using a positive integer as capacity

  • Int get(int key) Returns the value of the key if it exists in the cache, otherwise -1 is returned.

  • Void put(int key, int value) If the keyword already exists, change its data value. If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values.

Advanced: Can you do both in time complexity?

Example:

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] LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4Copy the code

Tip:

  • 1 <= capacity <= 3000

  • 0 <= key <= 3000

  • 0 <= value <=

  • Get and PUT are called up to 3 * times

Fundamental analysis

LRU is a very common page replacement algorithm.

To translate LRU into plain English, when data has to be weeded out (usually when capacity is full), select the data that has not been used for the longest time.

They want us to implement a fixed volume LRUCache. If the container is found to be full when data is inserted, a data will be eliminated according to LRU rules, and then new data will be inserted, where “insert” and “query” are counted as a “use”.

It can be understood by 🌰. Assuming we have LRUCache and test key pair [1-2, 2-2-3] of capacity, insert & query them in order:

  • Insert 1-1, at which point the latest used data is 1-1

  • Insert 2-2, and the latest data changes to 2-2

  • Query 1-1. In this case, the latest used data is 1-1

  • Insert 3-3. Since the container has reached its capacity, the existing data needs to be eliminated before insertion. In this case, data 2-3 will be eliminated to become the latest used data

For key-value pair storage, we can use “hash tables” to ensure that the insert and query complexity is.

We also need to maintain an additional “order of use” sequence.

We expect that when “new data is inserted” or “key-value pair query occurs”, the current key-value pair will be placed at the head of the sequence so that when LRU elimination is triggered, only data will be deleted from the tail of the sequence.

Looking to adjust the position of a node in a sequence within complexity, it is natural to think of a bidirectional linked list.

Two-way linked list

Specifically, we use a hash table to store “key-value pairs”. The Key of the key-value pair is used as the Key of the hash table, and the Value of the hash table uses our own encapsulated Node class, which is also used as the Node of the bidirectional linked list.

  • Insert: checks whether the current key-value pair already exists in the hash table:

  • Below capacity: Insert the hash table and reset the Node corresponding to the current key pair to the head of the list (refresh operation)

  • Reached capacity: First find the element to be deleted from the end of the list and delete it (delete operation), then insert the hash table and reset the Node corresponding to the current key pair to the head of the list (refresh operation).

  • If there is, the key-value pair is updated and the Node corresponding to the current key-value pair is adjusted to the head of the list (refresh operation)

  • If not, check whether the hash table has reached its capacity:

  • Query: if the Key is not found in the hash table, return directly; If the Key exists, the corresponding value is returned and the Node corresponding to the current Key value pair is adjusted to the head of the list (refresh operation)

Some details:

  • In order to reduce the “nulling” operation of the left and right nodes of the bidirectional linked list, two “sentinels” nodes are established in advancehead 和 tail.

Code:

class LRUCache { class Node { int k, v; Node l, r; Node(int _k, int _v) { k = _k; v = _v; } } int n; Node head, tail; Map<Integer, Node> map; public LRUCache(int capacity) { n = capacity; map = new HashMap<>(); head = new Node(-1, -1); tail = new Node(-1, -1); head.r = tail; tail.l = head; } public int get(int key) { if (map.containsKey(key)) { Node node = map.get(key); refresh(node); return node.v; } return -1; } public void put(int key, int value) { Node node = null; if (map.containsKey(key)) { node = map.get(key); node.v = value; } else { if (map.size() == n) { Node del = tail.l; map.remove(del.k); delete(del); } node = new Node(key, value); map.put(key, node); } refresh(node); } // Refresh is a two-step operation: // 1. Delete the current node from the bidirectional list (if the node itself exists in the bidirectional list) // 2. Void refresh(Node Node) {delete(Node); node.r = head.r; node.l = head; head.r.l = node; head.r = node; } // Delete: // If node.l is not empty, Void delete(node node) {if (node.l! = null) { Node left = node.l; left.r = node.r; node.r.l = left; }}}Copy the code

  • Time complexity: For all operations

  • Space complexity:

The last

This is No.146 of our “Brush through LeetCode” series, which started on 2021/01/01. As of the start date, there are 1916 questions on LeetCode, some of which have lock questions.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.