Diseñe e implemente una estructura de datos para la caché de uso menos reciente (LRU), que admita obtener y poner.
Análisis
La clave para resolver este problema es utilizar una lista de doble enlace que nos permite mover nodos rápidamente.
La caché LRU es una tabla hash de claves y nodos de doble enlace. La tabla hash hace que el tiempo de get () sea O (1). La lista de nodos de doble enlace hace que las operaciones de adición / eliminación de nodos sean O (1).
Solución Java
Defina una lista de doble enlace.
class Node{ int key; int value; Node prev; Node next; public Node(int key, int value){ this.key=key; this.value=value; } } |
Al analizar get y put, podemos resumir que hay 2 operaciones básicas: 1) removeNode (Nodo t), 2) offerNode (Nodo t).
class LRUCache { Node head; Node tail; HashMap<Integer, Node> map = null; int cap = 0; public LRUCache(int capacity) { this.cap = capacity; this.map = new HashMap<>(); } public int get(int key) { if(map.get(key)==null){ return -1; } //move to tail Node t = map.get(key); removeNode(t); offerNode(t); return t.value; } public void put(int key, int value) { if(map.containsKey(key)){ Node t = map.get(key); t.value = value; //move to tail removeNode(t); offerNode(t); }else{ if(map.size()>=cap){ //delete head map.remove(head.key); removeNode(head); } //add to tail Node node = new Node(key, value); offerNode(node); map.put(key, node); } } private void removeNode(Node n){ if(n.prev!=null){ n.prev.next = n.next; }else{ head = n.next; } if(n.next!=null){ n.next.prev = n.prev; }else{ tail = n.prev; } } private void offerNode(Node n){ if(tail!=null){ tail.next = n; } n.prev = tail; n.next = null; tail = n; if(head == null){ head = tail; } } } |
