首页 > 代码库 > [Leetcode][JAVA] LRU Cache
[Leetcode][JAVA] LRU Cache
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.
LRU cache, 采用“如果满则淘汰最近未使用的项目“的策略,所以需要一个序列,每次插入的项目放入序列首,被查找的项目也移至序列首。如果超过数量上限则删除序列最后的项目。查找,插入操作都需要O(1)的时间复杂度,否则超时通不过。所以这个序列可以是链表,并且为了查找快捷,需要结合HashMap。由于涉及到转移项目操作,需要双向链表。
HashMap用于把查找键key和具体项目联系起来,这样就能直接获得项目,然后将其移至链表首位。
需要注意的是set操作中,如果set的key已经存在了,那就相当于一次查找操作加上修改其值和HashMap的操作。
代码如下:
1 class Node 2 { 3 int key; 4 int value; 5 Node next; 6 Node front; 7 Node(int k, int v) 8 { 9 key=k;10 value=http://www.mamicode.com/v;11 next=null;12 front=null;13 }14 }15 16 private HashMap<Integer, Node> hs;17 private Node head;18 private Node tail;19 private int cap;20 public LRUCache(int capacity) {21 hs = new HashMap<Integer, Node>();22 head = null;23 cap = capacity;24 tail = null;25 }26 27 public int get(int key) {28 Node re = hs.get(key);29 if(re==null)30 return -1;31 if(re.front==null)32 return re.value;33 re.front.next = re.next;34 if(re.next!=null)35 re.next.front = re.front;36 else37 tail = re.front;38 re.front = null;39 re.next = head;40 head.front = re;41 head = re;42 return re.value;43 }44 45 public void set(int key, int value) {46 Node temp = hs.get(key);47 if(temp!=null)48 {49 get(key);50 head.value =http://www.mamicode.com/ value;51 hs.put(key,head);52 }53 else54 {55 temp = new Node(key, value);56 temp.next = head;57 if(head!=null)58 head.front = temp;59 head = temp;60 if(hs.size()==0)61 tail = temp;62 hs.put(key, temp);63 if(hs.size()>cap)64 {65 hs.remove(tail.key);66 tail.front.next = null;67 tail = tail.front;68 }69 }70 }
[Leetcode][JAVA] LRU Cache