Java: 2 HashMap and a Node list can solve it!


  • 0
    U
    class LRUCache {
    	private HashMap<Integer, Integer> keyValue;
    	private HashMap<Integer, Node> keyNode;
    	private static int size;
    	private Node head = null;
    	private Node tail = null;
    	private int capacity;
    	
        public LRUCache(int capacity) {
        	keyValue = new HashMap<Integer, Integer>();
        	keyNode = new HashMap<Integer, Node>();
            this.capacity = capacity;
            size = 0;
        }
        
        public int get(int key) {
            if (keyValue.containsKey(key)) {
            	moveToHead(key);
            	return keyValue.get(key);
            }
            	
            return -1;
        }
        
        public void put(int key, int value) {
        	if (keyValue.containsKey(key)) {		// If exist key, update value and move to head
        		keyValue.replace(key, value);
        		moveToHead(key);
        		return;
        	}
            if (size == capacity) {		// remove last one
            	removeLast();
            }
            
            keyValue.put(key, value);
            addToHead(key);
        }
    
        private Node removeLast() {
        	Node t = tail;
        	
        	if (head == tail) {			// only one node in the list
        		tail = null;
        		head = null;
        	} else {					// more than one node in the list
        		tail = tail.prev;
            	tail.next = null;
        	}
        	
        	keyValue.remove(t.hashMapKey);
        	keyNode.remove(t.hashMapKey);
        	
        	size--;
        	
        	return t;
        }
    
        private void moveToHead(int key) {		// if one node got hit, put it in the front of the list
        	Node node = keyNode.get(key);
        	if (node == head)			// only one node: node = head = tail
        		return;
        	if (node == tail) {			// node is the last node
        		tail = tail.prev;
        		tail.next = null;
        	} else {					// node is in the middle of the list
        		node.prev.next = node.next;
        		node.next.prev = node.prev;
        	}
    		node.next = head;
    		node.prev = null;
    		head.prev = node;
    		head = node;
        }
        
        private void addToHead(int key) {
        	if (head == null) {					// no node in the list
        		head = new Node(key);
        		tail = head;
        	} else {							// insert to the 0 position
        		Node t = new Node(key);
        		t.next = head;
        		head.prev = t;
        		head = t;
        	}
        	
        	keyNode.put(key, head);
        	size++;
        }
        
        
        class Node {
        	int hashMapKey;
        	Node next, prev;
        	Node(int key) {
        		this.hashMapKey = key;
        		this.next = null;
        		this.prev = null;
        	}
        }
    }
    

Log in to reply
 

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