Problem:
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.
Thought:
Use a HashMap along with a doubly linked list to achieve the O(1) running time for both get and set.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118 |
package
leetcode_Java;import java.util.Comparator;import java.util.HashMap;import java.util.PriorityQueue;public class LRUCache { HashMap <Integer, ListEntry> map = new
HashMap<Integer, ListEntry>(); DoublyLinkedList list; public
LRUCache(int
capacity) { list = new
DoublyLinkedList(capacity, map); } public
int get(int key) { ListEntry entry = map.get(key); if(entry == null){ return
-1; }else{ list.MoveToHead(entry); return
entry.value; } } public
void set(int key, int
value) { ListEntry entry = map.get(key); if(entry == null){ ListEntry newEntry = new
ListEntry(null, null, value, key); map.put(key, newEntry); list.Add(newEntry); }else{ entry.value = value; list.MoveToHead(entry); } } }class
DoublyLinkedList{ ListEntry head; ListEntry tail; int
capacity; int
currentSize; HashMap <Integer, ListEntry> map; public
DoublyLinkedList(int
capacity, HashMap <Integer, ListEntry> map){ this.capacity = capacity; this.currentSize = 0; this.map = map; } public
void Add(ListEntry entry){ if(currentSize < capacity){ if(head == null){ head = entry; tail = entry; }else{ head.prev = entry; entry.next = head; head = entry; } currentSize++; }else{ head.prev = entry; entry.next = head; head = entry; //remove tail map.remove(tail.key); tail = tail.prev; tail.next = null; } } //Assume that entry has already existed somewhere in the doubly linked list public
void MoveToHead(ListEntry entry){ if(entry == head){ return; }else
if(entry == tail){ tail = entry.prev; entry.prev.next = null; }else{ // in the middle entry.prev.next = entry.next; entry.next.prev = entry.prev; } head.prev = entry; entry.next = head; entry.prev = null; head = entry; }}// Node type of a doubly linked listclass
ListEntry{ ListEntry prev; ListEntry next; int
value; int
key; public
ListEntry(ListEntry prev, ListEntry next, int
value, int
key) { super(); this.prev = prev; this.next = next; this.value = value; this.key = key; } } |
[Leetcode] LRU cache,布布扣,bubuko.com
原文：http://www.cnblogs.com/Antech/p/3655587.html