r****7
发帖数: 2282 | 1 可以pass所有的test cases，不知道是不是显得比较初级，本人C++比较普通，谢谢指
教！
class LRUCache{
public:
typedef map::iterator> > KVType;
LRUCache(int capacity) {
mCapacity = capacity;
}
int get(int key) {
KVType::iterator it = mKeyValuePair.find(key);
if (it == mKeyValuePair.end()) {
return -1;
}
int result = it->second.first;
list::iterator keysIt = it->second.second;
mKeys.erase(keysIt);
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(result, mKeys.begin());
return result;
}
void set(int key, int value) {
int result = get(key);
// already exists
if (result != -1) {
mKeyValuePair[key].first = value;
return;
}
// doesn't exists and not full
if (mKeys.size() != mCapacity) {
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(value, mKeys.begin());
return;
}
// doesn't exists and full
mKeyValuePair.erase(mKeys.back());
mKeys.pop_back();
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(value, mKeys.begin());
}
private:
list mKeys;
KVType mKeyValuePair;
int mCapacity;
}; | a*****u
发帖数: 1712 | 2 请问你的mKeys，pop_back()和push_front()的时间复杂度多少？如果不是O(1), 可以
考虑换成double linkedlist | a*****u
发帖数: 1712 | 3 查了下，list的操作时间的确是O(1), 那整体设计没啥大问题。至于语言让懂c++的人
看吧 | r****7
发帖数: 2282 | 4 算法应该没啥问题，这个题也没啥算法吧，所以想让高手看看C++怎么写比较
sophisticated
【在 a*****u 的大作中提到】
: 查了下，list的操作时间的确是O(1), 那整体设计没啥大问题。至于语言让懂c++的人
: 看吧
| e***i
发帖数: 231 | 5 looks good! my 2cents in comments:
class LRUCache{ // maybe it's better to be templated key instead of 'int'?
public:
typedef map::iterator> > KVType; // map O(lgn)
vs unordered_map O(n) ??
LRUCache(int capacity) {
mCapacity = capacity;
}
int get(int key) {
KVType::iterator it = mKeyValuePair.find(key); //auto it = ...
if (it == mKeyValuePair.end()) {
return -1;
}
int result = it->second.first;
mKeys.erase(it->second.second); // keysIt used only once, combine
the line above
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(result, mKeys.begin());
return result;
}
void set(int key, int value) {
int result = get(key); //to optimise, maybe copy the first 3 lines
in get() instead of calling get()
// since you're putting the kv on top (push_front) anyway later here.
// already exists
if (result != -1) {
mKeyValuePair[key].first = value;
return;
}
if (mKeys.size() == mCapacity) {
// doesn't exists and full
mKeyValuePair.erase(mKeys.back());
mKeys.pop_back();
}
// doesn't exists and not full
mKeys.push_front(key);
mKeyValuePair[key] = make_pair(value, mKeys.begin());
}
private:
list mKeys;
KVType mKeyValuePair;
int mCapacity; // make it const, and init with ctor; and, unsigned int
};
【在 r****7 的大作中提到】
: 可以pass所有的test cases，不知道是不是显得比较初级，本人C++比较普通，谢谢指
: 教！
: class LRUCache{
: public:
: typedef map::iterator> > KVType;
: LRUCache(int capacity) {
: mCapacity = capacity;
: }
:
: int get(int key) {
|
|
