Java easy understanding solution using HashMap and DoublyLinkedList


  • 1
    C

    Similar but more concise than the top solution. I just swap nodes if current node's count >= next node's count when increase count, in this way, nodes with larger frequency and most recently used can bo moved to the back of doubly linked list.

    public class LFUCache {

    private class Node {
        Node prev;
        Node next;
        int value;
        int key;
        public Node(int key, int value) {
            this.key = key;
            this.value = value;
            this.prev = null;
            this.next = null;
        }
    }
    
    private HashMap<Integer, Node> map;
    private HashMap<Integer, Integer> valueMap;  //used to keep track of count
    private int capacity;
    private Node head = new Node(-1, -1); //dummy
    private Node tail = new Node(-1, -1);
    
    public LFUCache(int capacity) {
        this.map = new HashMap<Integer, Node>();
        this.valueMap = new HashMap<Integer, Integer>();
        this.capacity = capacity;
        tail.prev = head;
        head.next = tail;
        valueMap.put(-1, Integer.MAX_VALUE);
    }
    
    
    public int get(int key) {
        if (map.containsKey(key)) {
            increaseCount(key);
            return map.get(key).value;
        }
        return -1;
    }
    
    public void put(int key, int value) {
        if (capacity == 0 ) return;
        if (map.containsKey(key)) {
            map.get(key).value = value;        
            increaseCount(key);
        } else {
            if (map.size() == capacity) {
                map.remove(head.next.key);
                valueMap.remove(head.next.key);
                head.next = head.next.next;
                head.next.prev = head;
            } 
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            valueMap.put(key, 1);
            addToHead(newNode);
        }
    
    }
    
    private void addToHead(Node newNode) {
        Node tmp = head.next;
        head.next = newNode;
        newNode.prev = head;
        newNode.next = tmp;
        tmp.prev = newNode;
        while(newNode != tail && valueMap.get(newNode.next.key) <= valueMap.get(newNode.key)) {
                swap(newNode);                
        }
    }
    
    private void increaseCount(int key) {
        Node node = map.get(key);
        valueMap.put(key, valueMap.get(node.key) + 1);
        while(node != tail && valueMap.get(node.next.key) <= valueMap.get(key)) {
            swap(node);                
        }
    }
    
    private void swap(Node current) {
        Node tmp = current.next;
        Node p = current.prev;
        Node n = tmp.next;
        
        p.next = tmp;
        tmp.prev = p;
        current.prev = tmp;
        tmp.next = current;
        current.next = n;
        n.prev = current;
    }
    

    }


Log in to reply
 

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