clean java code using hashmap and doubly linkedlist


  • 1
    M
    public class AllOne {
    	private Bucket head=new Bucket(0);
    	private Bucket tail=new Bucket(Integer.MAX_VALUE);
    	Map<Integer,Bucket> bucketMap=new HashMap<>();
    	Map<String,Integer> keyMap=new HashMap<>();
    	class Bucket{
    	    int val;
    	    Bucket prev;
    	    Bucket next;
    	    Set<String> keySet;
    	    public Bucket(int val){
    		    this.val=val;
    		    keySet=new HashSet<>();
            }
        }
    
    	public AllOne() {
    		head.next=tail;
    		tail.prev=head;
    	}
    
    	public void inc(String key) {
    		if(!keyMap.containsKey(key)){
    			keyMap.put(key,1);
    			if(!bucketMap.containsKey(1)){
    				Bucket bucket=new Bucket(1);
    				insert(head,bucket);
    			}
    			bucketMap.get(1).keySet.add(key);
    		}else{
    			int val=keyMap.get(key);
    			keyMap.put(key,val+1);
    			Bucket curr=bucketMap.get(val);
    			Bucket next=bucketMap.get(val+1);
    			if(next==null){
    				next=new Bucket(val+1);
    				insert(curr,next);
    			}
    			next.keySet.add(key);
    			curr.keySet.remove(key);
    			if(curr.keySet.isEmpty()){
    				delete(curr);
    			}
    		}
    	}
    
    	public void dec(String key) {
    		if(keyMap.containsKey(key)){
    			int val=keyMap.get(key);
    			Bucket curr=bucketMap.get(val);
    			if(val==1){
    				keyMap.remove(key);
    			}else{
    			    keyMap.put(key,val-1);
    				Bucket prev=bucketMap.get(val-1);
    				if(prev==null){
    					prev=new Bucket(val-1);
    					insert(curr.prev,prev);
    				}
    				prev.keySet.add(key);
    			}
    			curr.keySet.remove(key);
    			if(curr.keySet.isEmpty()){
    				delete(curr);
    			}
    		}
    	}
    
    	public String getMaxKey() {
    		return tail.prev==head?"":tail.prev.keySet.iterator().next();
    	}
    
    	public String getMinKey() {
    		return head.next==tail?"":head.next.keySet.iterator().next();
    	}
    		
    	public void insert(Bucket prev,Bucket bucket){
    		bucketMap.put(bucket.val, bucket);
    		bucket.prev=prev;
    		bucket.next=prev.next;
    		prev.next.prev=bucket;
    		prev.next=bucket;
    	}
    		
    	public void delete(Bucket bucket){
    		bucketMap.remove(bucket.val);
    		bucket.prev.next=bucket.next;
    		bucket.next.prev=bucket.prev;
    	}
    }
    

Log in to reply
 

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