HashMap, TreeMap, DoubleLinkedList solution


  • 1
    class DDLNode{
    int key;
    int value;
    int freq;
    DDLNode pre;
    DDLNode post;
    public DDLNode(int key,int value){
    	this.key=key;
    	this.value=value;
    	this.freq=1;
    }
    

    }

    public class LFUCache {
    HashMap<Integer,DDLNode> map;
    TreeMap<Integer,DDLNode[]> tree;
    int capacity;
    
    public LFUCache(int capacity) {
    	this.map=new HashMap<>();
    	this.tree =new TreeMap<>();
    	this.capacity=capacity;    
    }
    
    public int get(int key) {
    	if(!map.containsKey(key)){
    		return -1;
    	}
    
    	DDLNode curr=map.get(key);
        //we hit it, delete it from current TreeNode, increment its frequency by 1, and insert to the right TreeNode
    	delete(curr);
    	curr.freq++;
    	insert(curr);
    	return curr.value;
    }
    
    public void set(int key, int value) {
        if(capacity==0){
            return;
        }
    	if(!map.containsKey(key)){
                //need to remove one since we reach capacity
    		if(map.size()==capacity){
    			Integer smallest=tree.firstKey();
    			DDLNode[] tmp=tree.get(smallest);
    			delete(tmp[1].pre);
    		}
    		DDLNode tmp=new DDLNode(key,value);
    		insert(tmp);
    	}else{
    		DDLNode curr=map.get(key);
    		curr.value=value;
    		delete(curr);
    		curr.freq++;
    		insert(curr);
    	}
    
    
    }
    // remove the DDLNode, from both the map and the tree
    public void delete(DDLNode node){
    	map.remove(node.key);
    	node.pre.post=node.post;
    	node.post.pre=node.pre;
    	
    	DDLNode[] res=tree.get(node.freq);
    	if(res[0].post==res[1]){
    		tree.remove(node.freq);
    	}
    }
    //insert a new DLLNode,to both map and tree
    public void insert(DDLNode node){
    	if(!map.containsKey(node.key)){
    		map.put(node.key,node);
    	}
    
    	if(!tree.containsKey(node.freq)){
    		DDLNode head=new DDLNode(0,0);
    		DDLNode tail=new DDLNode(0,0);
    		head.post=tail;
    		tail.pre=head;
    		tree.put(node.freq,new DDLNode[]{head,tail});
    	}
    
    	DDLNode t1=tree.get(node.freq)[0];
    	DDLNode t2=t1.post;
    	node.post=t2;
    	t2.pre=node;
    	node.pre=t1;
    	t1.post=node;
    
    }
    

    }


Log in to reply
 

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