My O(1) Java solution with comments beats 84%


  • 0
    T

    class LRUCache {
    class Node {
    public int key;
    public int value;
    public Node next;
    public Node prev;
    public Node (int key, int value) {
    this.key = key;
    this.value = value;
    next = null;
    prev = null;
    }
    }

    HashMap<Integer, Node> map;
    int mCapacity;
    Node head;
    Node tail;
    public LRUCache(int capacity) {
        map = new HashMap<Integer, Node>(capacity);
        this.mCapacity = capacity;
        head = null;
        tail = null;
    }
    
    private void moveNodeToFront(Node node) {
        if (node == head) {
            return;
        }
        
        if (node == tail) {
            tail = node.prev;
            tail.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
    
        node.next = head;
        head.prev = node;
        head = node;
    }
    
    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        
        // Get from the map and update the LRU list.
        Node node = map.get(key);
        moveNodeToFront(node);
        return node.value;
    }
    
    private void addNewNode(Node node) {
        map.put(node.key, node);
        if (head == null) {
            head = node;
            tail = node;
            return;
        }
    
        node.next = head;
        head.prev = node;
        head = node;
    }
    
    private void removeTail() {
        if (tail == null) {
            return;
        }
    
        Node temp = tail;
        if (tail.prev != null) {
            tail = tail.prev;
            tail.next = null;
        } else {
            head = null;
            tail = null;
        }
        map.remove(temp.key);
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            // Move the node to the head;
            Node node = map.get(key);
            node.value = value;
            moveNodeToFront(node);
            return;
        }
    
        Node node = new Node(key, value);
        // Put into HashMap and at the tail of the LRU list.
        if (map.size() < mCapacity) {
            addNewNode(node);
            return;
        }
        
        // Remove the tail from the LRU list and the map.
        removeTail();
    
        // Add the new one to the map and the front of LRU list.
        addNewNode(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.