Ac solution code


  • 1

    Explanation

    The basic idea is using HashMap to pair key with node in a doubly linked list. Once get or set function is invoked, the corresponding node will be moved to the tail, so that keep the head of the LinkedList is the least recently used node. And if the linkedList reaches its capacity limit, remove the head of the linkedList. The trick in this solution is adopting dummy head and dummy tail to avoid edge cases.
    (Dummy head and tail are the boundaries of the linkedList, but are excluded from the linkedList.)

    dummyHead |.......LinkedList.....| dummyTail
    

    The node can be gotten or set directly, so the time complexity is O(1). As the following:

    public class LRUCache {
        int capacity;
        HashMap<Integer, Node> map; //<key, Node>
        Node dummyHead = new Node(-1, -1);
        Node dummyTail = new Node(-1, -1);
    
    public LRUCache(int capacity) {
        map = new HashMap<Integer, Node>();
        this.capacity = capacity;
        dummyHead.next = dummyTail;// Dummy head, tail
        dummyTail.pre = dummyHead;
    }
    
    public int get(int key) {
    	if (map.containsKey(key)) {
    		moveToTail(key);// Access the node, and move it to the tail
    		return map.get(key).val;
    	}
    	return -1;
    }
    
    public void set(int key, int value) {
       if (get(key) != -1) {// Move the node to tail by invoking get function if it exists
    	  map.get(key).val = value; 
    	  return;
      }
    
      if (capacity == map.size()) {// Reached the capacity limit, then remove the head.
     	 map.remove(dummyHead.next.key);
    	 dummyHead.next = dummyHead.next.next;   	  
    	 dummyHead.next.pre = dummyHead;
      }
      
      map.put(key, new Node(key, value));    	        
      moveToTail(key);
    }
    
    void moveToTail(int key) {
    	Node node = map.get(key);    	    	
    	// Remove node from the list
    	if (node.pre != null) node.pre.next = node.next;
    	if (node.next != null)node.next.pre = node.pre;
    	
    	// Add node before dummyTail
    	dummyTail.pre.next = node;
    	node.pre  = dummyTail.pre; 
    	dummyTail.pre = node;
    	node.next  = dummyTail;    	
    }
    
    // Node helper class
    class Node {
    	public Node next;
    	public Node pre; 
    	public int key; 
    	public int val;	
    	public Node(int key,  int val) {
    		this.key = key;
    		this.val = val;
    	}	
    }// Node 
    
    }// LRUCache

Log in to reply
 

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