SHARE
TWEET

Untitled

a guest Oct 17th, 2019 95 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class LRUCache {
  2.     private final int capacity;
  3.     private final Map<Integer, LRUListNode> map;    
  4.     private final LRUListNode head;
  5.     private LRUListNode tail;
  6.     private int size;
  7.     public LRUCache(int capacity) {
  8.         this.capacity = capacity;
  9.         this.map = new HashMap<>();
  10.         this.head = new LRUListNode(Integer.MIN_VALUE, Integer.MIN_VALUE);
  11.         this.tail = head;
  12.         this.size = 0;
  13.     }
  14.    
  15.     public int get(int key) {
  16.         LRUListNode node = map.get(key);
  17.         if (node == null) return -1;
  18.         if (node == tail) tail = node.prev;
  19.         removeNode(node);
  20.         insertFront(node);
  21.        
  22.         // System.out.print(" got " + node.val + " last = " + tail.val);
  23.         // head.print();
  24.         return node.val;
  25.     }
  26.    
  27.     public void put(int key, int value) {
  28.         LRUListNode existingNode = map.get(key);
  29.         if (existingNode != null) {
  30.             get(key);
  31.             existingNode.val = value;
  32.             return;
  33.         }
  34.        
  35.        
  36.         LRUListNode node = new LRUListNode(key,value);
  37.         map.put(key, node);
  38.         insertFront(node);
  39.        
  40.         if(++size > capacity)
  41.             removeLast();
  42.        
  43.         // System.out.print(" Inserted " + key + "=" + value + " last = ");
  44.         // head.print();
  45.     }
  46.    
  47.     private void insertFront(LRUListNode node) {
  48.         if (head == tail) {
  49.             tail = node;
  50.         }
  51.            
  52.        
  53.         node.next = null;
  54.         node.prev = null;
  55.        
  56.         LRUListNode originalNext = head.next;
  57.        
  58.         head.next = node;
  59.        
  60.         node.prev = head;
  61.         node.next = originalNext;
  62.        
  63.         if (originalNext != null)
  64.             originalNext.prev = node;        
  65.     }
  66.    
  67.     private void removeNode(LRUListNode node) {
  68.         LRUListNode left = node.prev;
  69.         LRUListNode right = node.next;
  70.         if (left != null)
  71.             left.next = right;
  72.         if (right != null)
  73.             right.prev = left;
  74.         node.prev = null;
  75.         node.next = null;
  76.     }
  77.    
  78.     private void removeLast() {
  79.         map.remove(tail.key);
  80.         LRUListNode prev = tail.prev;
  81.         removeNode(tail);
  82.         prev.next = null;
  83.         tail = prev;
  84.         size--;
  85.        
  86.     }
  87.    
  88.     class LRUListNode {
  89.         LRUListNode(int key, int val) {
  90.             this.val = val;
  91.             this.key = key;
  92.         }
  93.         LRUListNode prev;
  94.         LRUListNode next;
  95.         int val;
  96.         int key;
  97.         public void print() {
  98.             for (LRUListNode n = this; n != null; n = n.next) {
  99.                 System.out.print("  [" + n.key + "=" + n.val + "]");
  100.             }
  101.             System.out.println(" ");
  102.         }
  103.     }
  104. }
  105.  
  106. /**
  107.  * Your LRUCache object will be instantiated and called as such:
  108.  * LRUCache obj = new LRUCache(capacity);
  109.  * int param_1 = obj.get(key);
  110.  * obj.put(key,value);
  111.  */
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top