leetcode 146 LRU 缓存机制
leetcode 146 LRU 缓存机制
简介
使用了C++自带的实现deque 和 unordered_map
code
class LRUCache {public: unordered_map<int, bool> map; unordered_map<int, int> mapV; deque<int> q; int capacity;
LRUCache(int capacity) { this->capacity = capacity;
}
int get(int key) { if(map[key]){ for(auto it=q.begin(); it != q.end(); it++){ if(*it == key){
q.erase(it); break;
}
} // if(q.size() == capacity) {
// map[q.front()] = false;
// q.pop_front();
// }
q.push_back(key); map[key] = true; return mapV[key];
} return -1;
}
void put(int key, int value) { if(map[key]) {
mapV[key] = value; for(auto it=q.begin(); it != q.end(); it++){ if(*it == key){
q.erase(it); break;
}
}
q.push_back(key);
}else{ if(q.size() == capacity){ map[q.front()] = false;
q.pop_front();
}
q.push_back(key); map[key] = true;
mapV[key] = value;
}
}
};/**
* 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);
*/class LRUCache extends LinkedHashMap<Integer, Integer>{ private int capacity;
public LRUCache(int capacity) { super(capacity, 0.75F, true); this.capacity = capacity;
} public int get(int key) { return super.getOrDefault(key, -1);
} public void put(int key, int value) { super.put(key, value);
} @Override
protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) { return size() > capacity;
}
}java 直接 使用了LinkedHashMap 然后 重载了removeEldestEntry函数, 对于输入的, 如果个数大于设定的容量将会删除.
java这个也太作弊了, 不过一般也很少有人会记住 LinkedHashMap这个名字.
还有removeEldestEntry这个名字.
Hope is a good thing,maybe the best of things,and no good thing ever dies.----------- Andy Dufresne
来源：https://www.cnblogs.com/eat-too-much/p/14778166.html