Topic describes

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.

Their thinking

We need to define a bidirectional linked list. We need a calculator to calculate how many numbers are stored in the map. If the number exceeds the capacity, we need to remove the head node.

AC code

Class LRUCache {// Define a bidirectional linked list public class Node{private Node pre; private Node next; private int val; private int key; public Node(int key,int val){ this.key=key; this.val=val; } } private Node head,tail; private int size; private HashMap<Integer,Node> map; private int count; public LRUCache(int capacity) { this.size=capacity; this.map=new HashMap<>(); Enclosing the head = new Node (0, 0); this.tail=head; this.count=0; } private void removeHead(){ map.remove(head.next.key); head.next=head.next.next; if(head.next! =null){ head.next.pre=head; } } private void appendTotail(Node node){ tail.next=node; node.pre=tail; tail=node; } public int get(int key) { if(! map.containsKey(key)){ return -1; } Node node=map.get(key); if(node! =tail){// Delete the Node Node pre=node.pre; pre.next=node.next; pre.next.pre=pre; appendTotail(node); } return node.val; } public void put(int key, int value) { Node cur=new Node(key,value); If (map.containsKey(key)){Node Node =map.get(key); if(node! =tail){// Delete the Node Node pre=node.pre; pre.next=node.next; pre.next.pre=pre; }else{ tail=tail.pre; } }else{ if(count<size){ count++; }else{ removeHead(); } } appendTotail(cur); map.put(key,cur); }}Copy the code

conclusion

The first step is to add a key to the list, so that when deleting the head node, the map can be directly deleted. The second step is to enforce the PUT method