Leetcode LRU Cache

浏览数：30 / 时间：2015年06月20日

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.

这一题主要是要考虑到数据结构，首先我们定义一个双向链表来保存各个节点，并维护一个连表头和链表尾。同时我们用HashMap来保存节点的索引信息，存储key与其相对应的结点的索引。

每当执行get和set方法时，我们都将该结点放于链表头。

将结点移动到表头需要考虑两种情况。

1.该结点已经存在于链表中，此时我们需要先删除该链表中的该结点，然后将该结点添加到表头。

2.该节点是新增结点，在链表中并没有，则直接添加到连表头。

在执行set(key,value)方法时也需要考虑到两种情况。

1.在未超过容量的情况下，直接new一个该结点，并把该结点放置于表头。

2.超过容量的情况下，则首先需要删除链表尾，再将新的结点放于表头。

 1 package LRU.Cache;
 2 
 3 import java.util.HashMap;
 4 import java.util.Map;
 5 
 6 public class LRUCache {
 7     Map <Integer,Node>map;
 8     Node head;
 9     Node tail;
10     int len;
11     int num;
12     class Node{
13         int key;
14         int value;
15         Node next;
16         Node pre;
17         public Node(int key,int value){
18             this.key=key;
19             this.value=value;
20             this.next=null;
21             this.pre=null;
22         }
23     }
24      public LRUCache(int capacity) {
25            map =new HashMap<Integer,Node>(capacity);
26            head=new Node(-1,-1);
27            tail=new Node(-1,-1);
28            head.next=tail;
29            tail.pre=head;
30            len=capacity;
31            num=0;
32         }
33         public void moveToHead(Node n){
34             if(n!=null){
35             if(map.containsKey(n.key)){
36             Node headNext=head.next;
37             Node npre=n.pre;
38             Node nnext=n.next;
39             //remove n
40             npre.next=nnext;
41             nnext.pre=npre;
42             }
43             //put n to head
44             Node headNext1=head.next;
45             n.next=headNext1;
46             headNext1.pre=n;
47             head.next=n;
48             n.pre=head;
49             }else return;
50         }
51         public int removeTail(){
52             Node tailPre=tail.pre;
53             Node prePre=tailPre.pre;
54             prePre.next=tail;
55             tail.pre=prePre;
56             return tailPre.key;
57         }
58         public int get(int key) {
59             if(map.containsKey(key)){
60                 Node obj=map.get(key);
61                 moveToHead(obj);
62                 return obj.value;
63             }else{
64                 return -1;
65             }
66         }
67         
68         public void set(int key, int value) {
69             if(map.containsKey(key)){
70                 Node obj=map.get(key);
71                 obj.value=value;
72                 moveToHead(obj);
73             }else{
74                 Node obj=new Node(key,value);
75                 if(num<len){
76                     moveToHead(obj);
77                     map.put(key, obj);
78                     num++;
79                 }else{
80                     int remove=removeTail();
81                     map.remove(remove);
82                     moveToHead(obj);
83                     map.put(key, obj);
84                 }
85             }
86         }
87 }