My solution using map and linked list.


  • 0
    W
    public class LRUCache {
    
    private static class LinkedListNode{
    	public int value=-1;
    	public int key=-1;
    	public LinkedListNode prev=null;
    	public LinkedListNode next=null;
    }
    
    
    
    private int capacity=0;
    private int size=0;
    private LinkedListNode head;
    private LinkedListNode tail;
    private Deque<Integer> keys=new LinkedList<Integer>();
    private Map<Integer,LinkedListNode> cache=new HashMap<Integer,LinkedListNode>();
    
    public LRUCache(int capacity) {
        this.capacity=capacity;
    }
    
    public int get(int key) {
        if(!cache.containsKey(key)){
            return -1;
        }
        LinkedListNode node=cache.get(key);
        int value=node.value;
        
        if(node.prev==null&&node.next==null){
            return value;
            
            
        }
        else if(node.prev==null&&node.next!=null){
            head=head.next;
            head.prev=null;
            
            tail.next=node;
            node.prev=tail;
            tail=node;
            tail.next=null;
        }
        else if(node.prev!=null&&node.next==null){
            tail=tail.prev;
            tail.next=null;
            
            tail.next=node;
            node.prev=tail;
            tail=node;
            tail.next=null;
        }
        else{
            node.prev.next=node.next;
            node.next.prev=node.prev;
            
            tail.next=node;
            node.prev=tail;
            tail=node;
            tail.next=null;
        }
        return value;        
    
    }
    
    public void set(int key, int value) {
        if(!cache.containsKey(key)&&size==capacity){
        	LinkedListNode newNode=new LinkedListNode();
        	newNode.key=key;
        	newNode.value=value;
        	tail.next=newNode;
        	newNode.prev=tail;
        	tail=newNode;
        	tail.next=null;
        	cache.put(key, newNode);
        	int lastkey=head.key;
        	head=head.next;
        	head.prev=null;
            cache.remove(lastkey);
        	
        }
        else if(cache.containsKey(key)){
        	LinkedListNode node=cache.get(key);
            node.value=value;
            if(node.prev==null&&node.next==null){
            }
            else if(node.prev==null&&node.next!=null){
                head=head.next;
                head.prev=null;
            
                tail.next=node;
                node.prev=tail;
                tail=node;
                tail.next=null;
            }
            else if(node.prev!=null&&node.next==null){
                tail=tail.prev;
                tail.next=null;
            
                tail.next=node;
                node.prev=tail;
                tail=node;
                tail.next=null;
            }
            else{
                node.prev.next=node.next;
                node.next.prev=node.prev;
            
                tail.next=node;
                node.prev=tail;
                tail=node;
                tail.next=null;
            }
            cache.put(key, node);
        }
        else {
    
        	LinkedListNode newNode=new LinkedListNode();
        	newNode.key=key;
        	newNode.value=value;
        	if(head==null&&tail==null){
                head=newNode;
                tail=newNode;
                newNode.next=null;
                newNode.prev=null;
            }
            else{
        	    tail.next=newNode;
        	    newNode.prev=tail;
        	    tail=newNode;
        	    tail.next=null;
            }
    
        	cache.put(key, newNode);
            size++;
        }
    }
    

    }


Log in to reply
 

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