22ms Java Solution


  • 0
    H

    import java.util.*;

    public class LRUCache {

    private HashMap<Integer,Node> hashmap ;
    private int capacity;
    private DoublyLinkedList queue;
    static class Node {
    	
    	int key ;
    	int value;
    	Node prev;
    	Node next;
    	
    	
    }
    static class DoublyLinkedList
    {
    	Node head ;
    	Node tail ;
    	
    	public DoublyLinkedList()
    	{
    		head = null;
    		tail = null;
    	}
    	
    	public Node dequeue(){
    		
    		Node temp=null;
    		if(head !=null)
    		{
    			temp = head;
    			head = head.next;
    		}
    		
    		return temp;
    	}
    	public void enqueue(Node n)
    	{
    		if (head == null)
    		{
    			head = n;
    			tail = n;
    			n.prev = null;
    			
    		}
    		else
    		{
    			n.prev = tail;
    			tail.next = n;
    			tail = n;			
    		}
    		n.next = null;
    	}
    	
    	public void moveToEnd(Node n)
    	{
    		if(head == n && tail != n)
    		{
    			head = n.next;
    			tail.next = n;
    			n.prev = tail;
    		}
    		else if (tail != n)
    		{
    			n.prev.next = n.next;
    			n.next.prev = n.prev;
    			n.prev = tail;
    			tail.next = n;
    			
    		}
    		n.next = null;
    	    tail =  n;
    	}
    	
    }
    
    public LRUCache(int capacity)
    {
    	this.capacity = capacity;
    	hashmap = new HashMap<Integer,Node>();
    	queue = new DoublyLinkedList();
    	
    }
    
    public int get(int key)
    {
    	if(hashmap.containsKey(key))
    	{
    		//move this node to the end and return the value
    		queue.moveToEnd(hashmap.get(key));
    		return hashmap.get(key).value;
    	}
    	else return -1;
    }
    
    public void set(int key, int value)
    {
    	if (hashmap.containsKey(key)){
    		//move the node to the end and overwrite the value
    		
    		queue.moveToEnd(hashmap.get(key));
    		hashmap.get(key).value = value;
    	}
    	else{
    		
    		if (hashmap.size() == this.capacity)
    		{
    			// remove the item from the front of the queue, update the head and delete the key from hashmap
    			// create a new node and add it to the end of the queue
    			Node temp = queue.dequeue();
    			hashmap.remove(temp.key);
    			// System.out.println("Removed : Key = " + temp.key + " Value : " + temp.value);
    			Node n = new Node();
    			n.key = key;
    			n.value = value;
    			hashmap.put(key, n);
    			queue.enqueue(n);
    		}
    		else
    		{
    			// create a new node and addd it to the queue
    			Node n = new Node();
    			n.key = key;
    			n.value = value;
    			hashmap.put(key, n);
    			queue.enqueue(n);
    		}
    	}
    		
    	
    	
    }
    

    }


Log in to reply
 

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