Least Recent Used Cache
用意
每次要重新熟悉或者学习一个新语言,我都会重新重新做一下这道题。因为这道题需要自己对语言如何自定义对象以及各种collection有一定的了解。 Leetcode link
C++ 解法
解法一: 构造一个tuple 用于保存在linkedlist里面,这种解法需要熟悉splice用法,我这里也用了emplace 相当于用了右值构造提速,避免反复创建销毁对象造成的额外开销。
static const auto s = [](){
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class LRUCache {
private:
typedef pair<int, int> Tuple; // <key, value>
typedef list< Tuple > List;
typedef unordered_map< int, List::iterator > HashMap;
int capacity;
List dbList;
HashMap dbMap;
// touch helps update it posisition
void touch(HashMap::iterator it){
auto listIt = it->second;
int key = listIt->first;
int value = listIt->second;
// Implementation 1
dbList.splice(dbList.begin(), dbList, listIt);
}
public:
LRUCache(int capacity): capacity(capacity) {
}
int get(int key) {
auto record = dbMap.find(key);
if (record == dbMap.end()){
return -1;
}
touch(record);
return record->second->second;
}
void put(int key, int value) {
auto record = dbMap.find(key);
if (record != dbMap.end()){
// just need to update
touch(record);
record->second->second = value;
return;
}
if (dbMap.size() == capacity){
// need to purge first
auto tuple = dbList.back();
dbMap.erase(tuple.first);
dbList.pop_back();
}
dbList.emplace_front(Tuple(key, value));
dbMap[key] = dbList.begin();
return;
}
};
解法二: 也是用了tuple(pair),不过这里是map里存的对象,tuple first 为 key, tuple second 为对应list里的iterator。我个人其实觉得第一种解法更加好理解。
static const auto s = []() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class LRUCache {
private:
typedef list<int> List;
typedef pair<int, List::iterator> Tuple;
typedef unordered_map<int, Tuple> Cache;
Cache dbMap;
List dbList;
int capacity;
void moveToFront(Cache::iterator it){
// update list
int key = it->first;
dbList.erase(it->second.second);
dbList.push_front(key);
// update location
it->second.second = dbList.begin();
return;
}
public:
LRUCache(int capacity): capacity(capacity) {
}
int get(int key) {
auto record = dbMap.find(key);
if (record == dbMap.end()){
return -1;
}
moveToFront(record);
return record->second.first;
}
void put(int key, int value) {
auto record = dbMap.find(key);
if (record != dbMap.end()){
// we just need to update
moveToFront(record);
// Implementation 1:
record->second.first = value;
// Implementation 2:
// dbMap[key] = { value, dbList.begin() };
return;
}
if (dbMap.size() == capacity){
// need to remove first
dbMap.erase(dbList.back());
dbList.pop_back();
}
dbList.push_front(key);
dbMap[key] = { value, dbList.begin() };
}
};
/**
* Your LRUCache object will be instantiated and called as such:
* LRUCache* obj = new LRUCache(capacity);
* int param_1 = obj->get(key);
* obj->put(key,value);
*/
Go 解法
Golang需要使用container/list 这个库,一般人也不会去碰吧。
type LRUCache struct {
dbMap map[int]*list.Element
dbList *list.List
capacity int
}
type tuple struct{
key int
value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
dbMap: make(map[int]*list.Element),
dbList: list.New(),
capacity: capacity,
}
}
func (this *LRUCache) Get(key int) int {
var ele *list.Element
var ok bool
if ele, ok = this.dbMap[key]; !ok{
return -1
}
this.dbList.MoveToFront(ele)
res := ele.Value.(tuple)
return res.value
}
func (this *LRUCache) Put(key int, value int) {
var ele *list.Element
var ok bool
t := tuple{key: key, value: value}
if ele, ok = this.dbMap[key]; ok{
// ele is in map
ele.Value = t
this.dbList.MoveToFront(ele)
return
}
ele = this.dbList.PushFront(t)
this.dbMap[key] = ele
if this.dbList.Len() > this.capacity{
removeEle := this.dbList.Back()
this.dbList.Remove(removeEle)
t := removeEle.Value.(tuple)
delete(this.dbMap, t.key)
}
return
}