[146. LRU Cache] #leetcode

146_1009.java

class LRUCache {
    private LinkedHashMap<Integer, Integer> map;
    private final int CAPACITY;
    
    public LRUCache(int capacity) {
        CAPACITY = capacity;
        map = new LinkedHashMap<Integer, Integer>(CAPACITY, 0.75f, true){
            protected boolean removeEldestEntry(Map.Entry eldest) {
                return size() > CAPACITY;
            }
        };
    }
    
    public int get(int key) {
        return map.getOrDefault(key, -1);
    }
    
    public void put(int key, int value) {
        map.put(key, value);
    }
}

/**
 * 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);
 */

class LRUCache {
    private static class Node {
        int key, value;
        Node prev, next;
        Node(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }
    
    private final int capacity;
    private int count;
    private Node head, tail;
    private Map<Integer, Node> map;
    
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>();
        head = new Node(0, 0);
        tail = new Node(0, 0);
        head.next = tail;
        tail.prev = head;
    }
    
    public int get(int key) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            moveToEnd(node);
            return node.value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (map.containsKey(key)) {
            Node node = map.get(key);
            moveToEnd(node);
            node.value = value;
        } else {
            if (capacity >= 1 && map.size() == capacity) {
                Node node = head.next;
                remove(node);
                map.remove(node.key);
            }
            Node node = new Node(key, value);
            addLast(node);
            map.put(key, node);
        }
    }
    
    private void moveToEnd(Node node) {
        remove(node);
        addLast(node);
    }
    
    private void remove(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        node.next = null;
        node.prev = null;
    }
    
    private void addLast(Node node) {
        Node prev = tail.prev;
        prev.next = node;
        node.prev = prev;
        
        node.next = tail;
        tail.prev = node;
    }
    
    private void print() {
        Node dummy = head;
        while (dummy != null) {
            System.out.print(dummy.key + ": " + dummy.value + ", ");
            dummy = dummy.next;
        }
        System.out.println();
        System.out.print("{");
        for (int key : map.keySet()) {
            System.out.print(key + ": " + map.get(key) + ", ");
        }
        System.out.println("}");
    }
}

/**
 * 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);
 */