f**********e
发帖数: 288 | 1 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.
这道小伙伴们都用int, 但是问题又没明说是用int. 该怎么样理解呢.generic? | x*******1
发帖数: 28835 | 2 就是个simulator. 选java，给的test case都是int。 | f**********e
发帖数: 288 | 3 多谢, 兄台.
【在 x*******1 的大作中提到】
: 就是个simulator. 选java，给的test case都是int。
| s**x
发帖数: 7506 | | w****3
发帖数: 110 | 5 我贴一个，另外可以直接用linkedhashmap做，设为accessOnly直接用
removeeldestentry，只要几行就能写完。下面的是自己用doubleLinkedList做的。
public class LRUCache {
HashMap data = new HashMap
DoubleLinkedListNode>();
int cap;
int count = 0;
DoubleLinkedListNode head = null;
DoubleLinkedListNode helper;
public LRUCache(int capacity) {
cap = capacity;
helper = new DoubleLinkedListNode(-1,-1);
head = helper;
}
public int get(int key) {
if (data.containsKey(key)) {
//move double LinkedList to head
DoubleLinkedListNode n = data.get(key);
if (!(n == head)) { // if it is the head, do nothing
n.pre.next = n.next;
n.next.pre = n.pre;
head.next = n;
n.pre = head;
n.next = null;
head = n;
}
return n.val;
}
return -1;
}
public void set(int key, int value) {
if (data.containsKey(key)) {
//move double LinkedList to head
DoubleLinkedListNode n = data.get(key);
if (!(n == head)) { // if it is the head, do nothing
n.pre.next = n.next;
n.next.pre = n.pre;
head.next = n;
n.pre = head;
n.next = null;
head = n;
}
n.val = value;
}
else {
if (count == cap) { // remove the tail
data.remove(helper.next.key);
if (helper.next == head) {// if only one element;
head = helper;
helper.next = null;
}
else {
helper.next = helper.next.next;
helper.next.pre = helper;
}
count--;
}
DoubleLinkedListNode n = new DoubleLinkedListNode(key, value);
data.put(key, n);
head.next = n;
n.pre = head;
head = n;
count++;
}
}
public class DoubleLinkedListNode {
DoubleLinkedListNode pre;
DoubleLinkedListNode next;
int key;
int val;
public DoubleLinkedListNode(int k, int v) {
key = k;
val = v;
pre = null;
next = null;
}
}
} | s**x
发帖数: 7506 | 6 java 不熟， but I suspect you need to use next/pre etc for doublelinkedlist,
that is like C, not even c++.
【在 w****3 的大作中提到】
: 我贴一个，另外可以直接用linkedhashmap做，设为accessOnly直接用
: removeeldestentry，只要几行就能写完。下面的是自己用doubleLinkedList做的。
: public class LRUCache {
: HashMap data = new HashMap: DoubleLinkedListNode>();
: int cap;
: int count = 0;
: DoubleLinkedListNode head = null;
: DoubleLinkedListNode helper;
: public LRUCache(int capacity) {
| f**********e
发帖数: 288 | 7 我也贴一个, 但最复杂的case没过, 有空在查查. 请大家指正.
public class LRUCache {
int capacity;
LinkedList list = new LinkedList();
HashMap map = new HashMap();
public LRUCache(int capacity) {
this.capacity = capacity;
}
public int get(int key) {
if(!map.containsKey(key))
return -1;
CacheEntry c = map.get(key);
int val = c.val;
moveToHead(c);
return val;
}
public void set(int key, int value) {
CacheEntry c = new CacheEntry(key, value);
if(map.containsKey(key)){
moveToHead(c);
} else{
if(list.size() == capacity){
list.remove(capacity - 1);
map.remove(key);
setHead(key, c);
} else {
setHead(key, c);
}
}
}
public void moveToHead(CacheEntry c){
list.remove(c);
list.add(0, c);
}
public void setHead(int key, CacheEntry c){
list.add(0, c);
map.put(key, c);
}
public class CacheEntry{
int val;
int key;
public CacheEntry(int val, int key){
this.val = val;
this.key = key;
}
}
} | w****3
发帖数: 110 | 8 额，那应该怎么实现呢？似乎java里面没有已经写好的doubly linked list？
doublelinkedlist,
【在 s**x 的大作中提到】
: java 不熟， but I suspect you need to use next/pre etc for doublelinkedlist,
: that is like C, not even c++.
|
|
