Open yokostan opened 5 years ago
class LRUCache { class ListNode { public int key, val; public ListNode next; public ListNode(int key, int val) { this.key = key; this.val = val; this.next = null; } } public int capacity, size; public ListNode dummy, tail; public Map<Integer, ListNode> map; public LRUCache(int capacity) { this.capacity = capacity; this.map = new HashMap<Integer, ListNode>(); this.dummy = new ListNode(0, 0); this.tail = this.dummy; } public void moveToTail(int key) { ListNode prev = map.get(key); ListNode curr = prev.next; if (tail == curr) return ; prev.next = prev.next.next; tail.next = curr; if (prev.next != null) { map.put(prev.next.key, prev); } map.put(curr.key, tail); tail = curr; } public int get(int key) { if (!map.containsKey(key)) return -1; moveToTail(key); return tail.val; } public void put(int key, int value) { if (get(key) != -1) { ListNode prev = map.get(key); prev.next.val = value; return ; } if (size < capacity) { size++; ListNode curr = new ListNode(key, value); tail.next = curr; map.put(key, tail); tail = curr; return; } // replace the first node with new key, value ListNode first = dummy.next; map.remove(first.key); first.key = key; first.val = value; map.put(key, dummy); moveToTail(key); } } /** * Your LRUCache object will be instantiated and called as such: * LRUCache obj = new LRUCache(capacity); * int param_1 = obj.get(key); * obj.put(key,value); */