Java, LinkedList + Map, 130ms.


  • 0
    K

    class LRUCache {

    private static class Node {
        private final int key;
        private int val;
        private Node next;
        private Node prev;
        
        private Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
    
    private final Node head = new Node(0, 0);
    private final Map<Integer, Node> map = new HashMap<>();
    private final int cap;
    private Node tail;
    
    public LRUCache(int capacity) {
        this.cap = capacity;
        this.tail = null;
    }
    
    public int get(int key) {
        Node node = map.get(key);
        if (node == null) {
            return -1;
        }
        delete(node);
        bringToFront(node);
        return node.val;
    }
    
    public void put(int key, int value) {
        Node node = map.get(key);
        
        if (node != null) {
            node.val = value;    
            delete(node);
        } else {
            node = new Node(key, value);    
            map.put(key, node);            
            
            if (tail == null) {
                tail = node;
            }
        }
        
        bringToFront(node);
        
        if (map.size() > cap) {
            map.remove(tail.key);
    
            tail = tail.prev;
            tail.next = null;
        }
    }
    
    private void delete(Node node) {         
        if (tail == node && node.prev != head) {
            tail = node.prev;
        }
        
        node.prev.next = node.next;
        if (node.next != null) {
            node.next.prev = node.prev;    
        }
    }
    
    private void bringToFront(Node node) { 
        node.next = head.next;
        node.prev = head;
        
        if (head.next != null) {
            head.next.prev = node;    
        }
        head.next = node;
    }
    

    }

    /**

    • Your LRUCache object will be instantiated and called as such:
    • LRUCache obj = new LRUCache(capacity);
    • int param_1 = obj.get(key);
    • obj.put(key,value);
      */

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.