Leetcode-LRU Cache

浏览数：21 / 时间：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.

Analysis:

Use double linked list.

Solution:

 1 class Node{
 2     int key;
 3     int val;
 4     Node pre;
 5     Node next;
 6     public Node(int k, int v){
 7         key= k;
 8         val = v;
 9         pre = null;
10         next = null;
11     }
12 }
13 
14 public class LRUCache {
15 
16 
17     Map<Integer,Node> record;
18     Node preHead,end;
19     int maxCapa;
20     int curCapa;
21     
22     public LRUCache(int capacity) {
23         record = new HashMap<Integer,Node>();
24         preHead = new Node(-1,-1);
25         end = null;
26         maxCapa = capacity;
27         curCapa = 0;
28     }
29     
30     public int get(int key) {
31         if (!record.containsKey(key)) return -1;
32         Node cur = record.get(key);
33         if (cur==end) return cur.val;
34 
35         cur.pre.next = cur.next;
36         cur.next.pre = cur.pre;
37         end.next = cur;
38         cur.next = null;
39         cur.pre = end;
40         end = cur;        
41         return cur.val;
42     }
43     
44     public void set(int key, int value) {
45         if (maxCapa==0) return;
46 
47         if (record.containsKey(key)){
48             Node cur = record.get(key);
49             cur.val = value;
50             this.get(key);
51         } else {
52             if (curCapa==maxCapa){
53                 Node cur = preHead.next;
54                 preHead.next = cur.next;
55                 record.remove(cur.key);
56                 curCapa--;                
57             }
58  
59             curCapa++;
60             Node cur = new Node(key,value);
61             record.put(key,cur);
62             if (curCapa==1){
63                 preHead.next = cur;
64                 cur.pre = preHead;
65                 end = cur;
66             } else {
67                 end.next = cur;
68                 cur.pre = end;
69                 end = cur;
70             }            
71         }
72     }
73 }