|
| 1 | +/* |
| 2 | +Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set. |
| 3 | +
|
| 4 | +get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. |
| 5 | +set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. |
| 6 | + */ |
| 7 | + |
| 8 | +importjava.util.HashMap; |
| 9 | +importjava.util.Map; |
| 10 | + |
| 11 | +publicclassLRUCache { |
| 12 | + |
| 13 | +classListNode { |
| 14 | +intval; |
| 15 | +ListNodeprev,next; |
| 16 | +publicListNode(intval) { |
| 17 | +this.val =val; |
| 18 | + } |
| 19 | + } |
| 20 | + |
| 21 | +intsize =0; |
| 22 | +intcapacity; |
| 23 | +ListNodehead,tail; |
| 24 | +Map<Integer,ListNode>map; |
| 25 | + |
| 26 | +publicLRUCache(intcapacity) { |
| 27 | +head =newListNode(-1); |
| 28 | +tail =newListNode(-1); |
| 29 | +head.next =tail; |
| 30 | +tail.prev =head; |
| 31 | +map =newHashMap<>(); |
| 32 | +this.capacity =capacity; |
| 33 | + } |
| 34 | + |
| 35 | +publicintget(intkey) { |
| 36 | +ListNodenode =map.getOrDefault(key,head); |
| 37 | +if(node.val != -1)moveToHead(node); |
| 38 | +returnnode.val; |
| 39 | + } |
| 40 | + |
| 41 | +publicvoidset(intkey,intvalue) { |
| 42 | +if(map.getOrDefault(key,head).val != -1) { |
| 43 | +moveToHead(map.get(key)); |
| 44 | +map.get(key).val =value; |
| 45 | + }else { |
| 46 | +ListNodenewNode =newListNode(value); |
| 47 | +addNode(newNode); |
| 48 | +if(++size >capacity) { |
| 49 | +removeNode(tail.prev); |
| 50 | + --size; |
| 51 | + } |
| 52 | +map.put(key,newNode); |
| 53 | + } |
| 54 | + } |
| 55 | + |
| 56 | +privatevoidmoveToHead(ListNodenode) { |
| 57 | +if(node ==head ||node.prev ==head) { |
| 58 | +System.out.println("head: " +head.val); |
| 59 | +return; |
| 60 | + } |
| 61 | +detachNode(node); |
| 62 | +addNode(node); |
| 63 | + } |
| 64 | + |
| 65 | +privatevoidaddNode(ListNodenewNode) { |
| 66 | +newNode.next =head.next; |
| 67 | +head.next.prev =newNode; |
| 68 | +head.next =newNode; |
| 69 | +newNode.prev =head; |
| 70 | + } |
| 71 | + |
| 72 | +privatevoidremoveNode(ListNodenode) { |
| 73 | +detachNode(node); |
| 74 | +node.val = -1; |
| 75 | + } |
| 76 | + |
| 77 | +privatevoiddetachNode(ListNodenode) { |
| 78 | +node.prev.next =node.next; |
| 79 | +node.next.prev =node.prev; |
| 80 | +node.next =node.prev =null; |
| 81 | + } |
| 82 | + |
| 83 | +publicstaticvoidmain(String[]args) { |
| 84 | +intcapacity =2; |
| 85 | +LRUCachelru =newLRUCache(capacity); |
| 86 | +lru.set(2,1); |
| 87 | +lru.set(1,1); |
| 88 | +System.out.println(lru.get(2)); |
| 89 | +lru.set(4,1); |
| 90 | +System.out.println(lru.get(2)); |
| 91 | +System.out.println(lru.get(1)); |
| 92 | +} |
| 93 | +} |