a**********0
发帖数: 422 | 1 代码本身很简单 但是超时 而且test case 不容易复制 因为是cap =2048 然后一长串
操作的
import java.util.*;
public class LRUCache {
int cap;
//hashmap is for Cache's storage
// arraylist is for items' recencies
HashMap myHashMap; // key-value
ArrayList myArrayList; // key
public LRUCache(int capacity) { // this is the constructor
this.cap = capacity;
myHashMap = new HashMap(); // key-value
myArrayList = new ArrayList();// key
}
public int get(int key) {
if(this.myHashMap.get(key) == null)
return -1;
this.myArrayList.remove(new Integer(key));
this.myArrayList.add(key);
return this.myHashMap.get(key).intValue();
}
public void set(int key, int value) {
if(this.myHashMap.size()< this.cap){
if(this.myHashMap.get(key) != null){
this.myHashMap.put(key,value);
this.myArrayList.remove(new Integer(key));
this.myArrayList.add(key);
}else{
this.myHashMap.put(key,value);
this.myArrayList.add(key);
}
}else{
if(this.myHashMap.get(key) != null){
this.myHashMap.put(key,value);
this.myArrayList.remove(new Integer(key));
this.myArrayList.add(key);
}else{
this.myHashMap.remove(myArrayList.get(0));
this.myHashMap.put(key,value);
this.myArrayList.remove(0); // remove entry with index =0
this.myArrayList.add(key);
}
}
}
} |
l*********8
发帖数: 4642 | 2 myArrayList.remove is O(n)
【在 a**********0 的大作中提到】
: 代码本身很简单 但是超时 而且test case 不容易复制 因为是cap =2048 然后一长串
: 操作的
: import java.util.*;
: public class LRUCache {
:
: int cap;
: //hashmap is for Cache's storage
: // arraylist is for items' recencies
: HashMap myHashMap; // key-value
: ArrayList myArrayList; // key
|
a**********0
发帖数: 422 | 3 那怎么办
记录recency的要容易找到头节点 因为有时要删除最老的 也要可以删除random的一个
因为要更新某key的recency
int[] 估计不行 因为删除需要重新调整array的内容
怎么办？
【在 l*********8 的大作中提到】
: myArrayList.remove is O(n)
|
a**********0
发帖数: 422 | 4 网上很多linkedlistHashmap 不用那个有什么解决方法 |
l*********8
发帖数: 4642 | 5 自己写一个double linked list
【在 a**********0 的大作中提到】
: 网上很多linkedlistHashmap 不用那个有什么解决方法
|
a**********0
发帖数: 422 | 6 remove 仍然 O（n）
而且没法根据内容remove （每次get set之后要更新recency）
我建议你简单写几行代码取代原来的arraylist 否则我不太清楚你的思路
【在 l*********8 的大作中提到】
: 自己写一个double linked list
|
l*********8
发帖数: 4642 | 7 http://www.programcreek.com/2013/03/leetcode-lru-cache-java/
【在 a**********0 的大作中提到】
: remove 仍然 O（n）
: 而且没法根据内容remove （每次get set之后要更新recency）
: 我建议你简单写几行代码取代原来的arraylist 否则我不太清楚你的思路
|
a**********0
发帖数: 422 | 8 懒得再在这个上花时间了 我的代码logic是对的 |
w********s
发帖数: 1570 | 9 get的操作不是O(1)，当然超市了
这题很简单，用hashmap记录，用list维护序列
class LRUCache{
public:
unordered_map _map;
unordered_map::iterator> _itmap;
list* _keylist;
int _capacity;
LRUCache(int capacity) {
_keylist = new list(capacity);
_capacity = capacity;
}
int get(int key) {
int value = -1;
if (_map.find(key) != _map.end())
{
value = _map[key];
_keylist->erase(_itmap[key]);
_keylist->push_front(key);
_itmap[key] = _keylist->begin();
}
return value;
}
void set(int key, int value) {
if (_map.find(key) != _map.end())
{
_map[key] = value;
_keylist->erase(_itmap[key]);
_keylist->push_front(key);
_itmap[key] = _keylist->begin();
return;
}
if (_keylist->size() >= _capacity)
{
int k = _keylist->back();
_keylist->pop_back();
_itmap.erase(k);
_map.erase(k);
}
_keylist->push_front(key);
_itmap[key] = _keylist->begin();
_map[key] = value;
}
};
【在 a**********0 的大作中提到】
: 代码本身很简单 但是超时 而且test case 不容易复制 因为是cap =2048 然后一长串
: 操作的
: import java.util.*;
: public class LRUCache {
:
: int cap;
: //hashmap is for Cache's storage
: // arraylist is for items' recencies
: HashMap myHashMap; // key-value
: ArrayList myArrayList; // key
|
w********s
发帖数: 1570 | 10 用hashmap存key->iterator
【在 a**********0 的大作中提到】
: 代码本身很简单 但是超时 而且test case 不容易复制 因为是cap =2048 然后一长串
: 操作的
: import java.util.*;
: public class LRUCache {
:
: int cap;
: //hashmap is for Cache's storage
: // arraylist is for items' recencies
: HashMap myHashMap; // key-value
: ArrayList myArrayList; // key
|
l*********8
发帖数: 4642 | 11 c++是可以这样做。 不知道JAVA可以吗？
【在 w********s 的大作中提到】
: 用hashmap存key->iterator
|
