Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.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.
Solution0 (Time limit exceeded)
package leetcode; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; /** * Created by linxuan on 3/11/16. */ public class LRUCache { LinkedList<Integer> list; Map<Integer,Integer> map; int capacity; public LRUCache(int capacity) { this.list= new LinkedList<Integer>(); this.map = new HashMap<Integer, Integer>(); this.capacity = capacity; } public int get(int key) { if(map.get(key) != null){ list.removeFirstOccurrence(key); list.addFirst(key); return map.get(key); } else { return -1; } } public void set(int key, int value) { if(list.size() < capacity){ list.addFirst(key); map.put(key,value); } else { if(map.get(key) != null){ map.put(key,value); } else { map.remove(list.getLast()); list.removeLast(); list.addFirst(key); map.put(key,value); } } } }
之所以出现Time limit exceeded，原因是 list.removeFirstOccurrence(key); 这句的时间复杂度是O(n)。虽然Java中的LinkedList实现方式是双向链表 (double linked list)，但是所有的remove操作的时间复杂度都是O(n)。以下是Java中LinkedList的remove的代码
1 public boolean remove(Object o) { 2 if (o == null) { 3 for (Node<E> x = first; x != null; x = x.next) { 4 if (x.item == null) { 5 unlink(x); 6 return true; 7 } 8 } 9 } else { 10 for (Node<E> x = first; x != null; x = x.next) { 11 if (o.equals(x.item)) { 12 unlink(x); 13 return true; 14 } 15 } 16 } 17 return false; 18 }
由第10行看出，remove操作的时间负责度是O(n)。导致代码提交后出现Time limit exceeded。那么解决办法就是自己实现双向链表。如下代码。
Solution1 (Accepted)
1 class DLinkedNode { 2 int key; 3 int value; 4 DLinkedNode pre; 5 DLinkedNode post; 6 } 7 8 /** 9 * Always add the new node right after head; 10 */ 11 private void addNode(DLinkedNode node){ 12 node.pre = head; 13 node.post = head.post; 14 15 head.post.pre = node; 16 head.post = node; 17 } 18 19 /** 20 * Remove an existing node from the linked list. 21 */ 22 private void removeNode(DLinkedNode node){ 23 DLinkedNode pre = node.pre; 24 DLinkedNode post = node.post; 25 26 pre.post = post; 27 post.pre = pre; 28 } 29 30 /** 31 * Move certain node in between to the head. 32 */ 33 private void moveToHead(DLinkedNode node){ 34 this.removeNode(node); 35 this.addNode(node); 36 } 37 38 // pop the current tail. 39 private DLinkedNode popTail(){ 40 DLinkedNode res = tail.pre; 41 this.removeNode(res); 42 return res; 43 } 44 45 private Hashtable<Integer, DLinkedNode> 46 cache = new Hashtable<Integer, DLinkedNode>(); 47 private int count; 48 private int capacity; 49 private DLinkedNode head, tail; 50 51 public LRUCache(int capacity) { 52 this.count = 0; 53 this.capacity = capacity; 54 55 head = new DLinkedNode(); 56 head.pre = null; 57 58 tail = new DLinkedNode(); 59 tail.post = null; 60 61 head.post = tail; 62 tail.pre = head; 63 } 64 65 public int get(int key) { 66 67 DLinkedNode node = cache.get(key); 68 if(node == null){ 69 return -1; // should raise exception here. 70 } 71 72 // move the accessed node to the head; 73 this.moveToHead(node); 74 75 return node.value; 76 } 77 78 79 public void set(int key, int value) { 80 DLinkedNode node = cache.get(key); 81 82 if(node == null){ 83 84 DLinkedNode newNode = new DLinkedNode(); 85 newNode.key = key; 86 newNode.value = value; 87 88 this.cache.put(key, newNode); 89 this.addNode(newNode); 90 91 ++count; 92 93 if(count > capacity){ 94 // pop the tail 95 DLinkedNode tail = this.popTail(); 96 this.cache.remove(tail.key); 97 --count; 98 } 99 }else{ 100 // update the value. 101 node.value = value; 102 this.moveToHead(node); 103 } 104 105 }
Solution2 (Accepted)
1 import java.util.LinkedHashMap; 2 import java.util.Map; 3 4 public class LRUCache extends LinkedHashMap<Integer, Integer> { 5 private int capacity; 6 7 public LRUCache(int capacity) { 8 super(16, 0.75f, true); 9 this.capacity = capacity; 10 } 11 //重写父类get，为null时范围-1 12 public Integer get(Object key) { 13 Integer v = super.get(key); 14 if (v != null) 15 return v; 16 else 17 return -1; 18 } 19 //重写父类方法，当超过缓存容量时，就删除最老的 20 public boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { 21 return size() > capacity; 22 } 23 24 public void set(int key, int value) { 25 super.put(key, value); 26 } 27 }
上面最神奇的代码是removeEldestEntry(Map.Entry<Integer, Integer> eldest) 函数。这个函数在LinkedHashMap中什么地方被使用了呢？是在addEntry中，如下代码。
1 void addEntry(int hash, K key, V value, int bucketIndex) { 2 super.addEntry(hash, key, value, bucketIndex); 3 4 // Remove eldest entry if instructed 5 Entry<K,V> eldest = header.after; 6 if (removeEldestEntry(eldest)) { 7 removeEntryForKey(eldest.key); 8 } 9 }
(完)
原文：http://www.cnblogs.com/lin-xuan/p/5270997.html