esign 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即Least Recently Used 近期最少使用算法。
1、使用了HashMap和ArrayList
public class LRUCache {
int size,num;
List<Integer> list ;
Map<Integer,Integer> map;
public LRUCache(int capacity) {
size = capacity;
num = 0;
list = new ArrayList<Integer>();
map = new HashMap<Integer,Integer>();
}
public int get(int key) {
if( map.containsKey(key) ){
list.remove((Integer)key);
list.add(key);
return map.get(key);
}
else
return -1;
}
public void set(int key, int value) {
if( map.containsKey(key) ){
list.remove((Integer)key);
map.put(key,value);
list.add(key);
}else{
if( num == size ){
map.remove(list.get(0));
list.remove((int)0);
map.put(key,value);
list.add(key);
}else{
map.put(key,value);
list.add(key);
num++;
}
}
}
}
2、使用LinkedHashMap.
public class LRUCache {
int size,num;
Map<Integer,Integer> map;
public LRUCache(int capacity) {
size = capacity;
List list =new LinkedList();
map = new LinkedHashMap<Integer,Integer>();
}
public int get(int key) {
if( map.containsKey(key) ){
int value = map.get(key);
map.remove(key);
map.put(key,value);
return value;
}
else
return -1;
}
public void set(int key, int value) {
if( map.containsKey(key) ){
map.remove(key);
map.put(key,value);
}else{
if( num == size ){
int firstKey = map.keySet().iterator().next();
map.remove(firstKey);
map.put(key,value);
}else{
map.put(key,value);
num++;
}
}
}
}
3、可以使用双向链表实现。