JAVA extremly clean solution, best performance beat 87%, only 1 doubleLinkedNode, 1 HashMap, 1 LinkedHashMap


  • 0
    class Node{
    Node prev;
    Node next;
    Map<Integer,Integer> nodes;
    int LRUkey;
    public Node(int key, int val){
        nodes = new LinkedHashMap<Integer,Integer> (1,0.75f,true){
            protected boolean removeEldestEntry(Map.Entry eldest) {
                LRUkey = (Integer)eldest.getKey();
                return false;
            }
        };
        nodes.put(key,val);
    }
    }
    
    public class LFUCache {
    private Map<Integer, Node> LRUmap;
    private Node LRUhead; //DummpyHead
    private Node LRUtail; //DummpyTail
    private int capacity;
    private int size;
    public LFUCache(int capacity) {
        LRUmap = new HashMap<Integer,Node>();
        this.capacity = capacity;
        size = 0;
        LRUhead = new Node(Integer.MAX_VALUE,0);
        LRUtail = new Node(Integer.MAX_VALUE,0);
        LRUhead.next = LRUtail;
        LRUtail.prev = LRUhead;
    }
    //move node towards DummpyHead
    public void NodeToHead(Node node){
            node.next = LRUhead.next;
            LRUhead.next.prev = node;
            LRUhead.next = node;
            node.prev = LRUhead;
    }
    //delete node when size>capacity or it is being visited/get
    public void deleteNode(Node node, int key){
            node.nodes.remove(key);
            if(node.nodes.size()>0)
                node.LRUkey = node.nodes.keySet().iterator().next();
            else 
                node.LRUkey = key;
    }
    public void put(int key, int value) {
        if(capacity==0)
            return;
        if(!LRUmap.containsKey(key)){
            if(size==capacity){ //need to delete the LRU node 
            	Node LRUnode = LRUtail.prev;
                if(LRUnode.nodes.size()==0) 
                    LRUnode = LRUmap.get(LRUnode.LRUkey);	
                LRUmap.remove(LRUnode.LRUkey);
                deleteNode(LRUnode, LRUnode.LRUkey);
                size = size - 1;
            } //If there's no need to delete LRU node, we add it to tail.
            if(LRUtail.prev.LRUkey==Integer.MAX_VALUE) //In case of LRUtail.prev is dummy head
                NodeToHead(new Node(key,value));
            else //we add it to tail
                LRUtail.prev.nodes.put(key,value);
            LRUmap.put(key,LRUtail.prev); //updated the LRUmap
            size = size+1;
        }
        else{ //need to update node
            Node currentNode = LRUmap.get(key);
            deleteNode(currentNode, key);
            if(currentNode.prev.LRUkey==Integer.MAX_VALUE){ //In case of currentNode.prev is dummy head
                NodeToHead(new Node(key,value)); //move new node to dummpy LRUhead
                LRUmap.put(key,LRUhead.next); //updated the LRUmap
            }
            else{
                currentNode.prev.nodes.put(key,value);
                LRUmap.put(key,currentNode.prev); //updated the LRUmap
            }
        }
        
    }
    public int get(int key) {
        if(!LRUmap.containsKey(key)){
            return -1;
        }
        else{
            Node currentNode = LRUmap.get(key);
            int value = currentNode.nodes.get(key);
            deleteNode(currentNode, key);
            if(currentNode.prev.LRUkey==Integer.MAX_VALUE){ //currentNode.prev is head
                NodeToHead(new Node(key,value)); //move new node to LRUhead
                LRUmap.put(key,LRUhead.next);
            }
            else{
                currentNode.prev.nodes.put(key,value);
                LRUmap.put(key,currentNode.prev);
            }
            return value;
        }
    }
    }

Log in to reply
 

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