C++ 解法, 执行用时: 83ms, 内存消耗: 12524KB, 提交时间: 2022-04-28
static const auto __ = [] {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
return nullptr;
}();
class Solution {
public:
// [a, b, c] a: 1 set/2 get b, c: key, val
vector<int> LFU(vector<vector<int>>& operators, int capacity) {
LFUCache lfu(capacity);
vector<int> result;
for(auto& op : operators){
if(op[0] == 1){
lfu.put(op[1], op[2]);
}else if(op[0] == 2){
result.push_back(lfu.get(op[1]));
}
}
return result;
}
struct CacheNode {
int key;
int value;
int freq;
// pointer to the node in the list
list<int>::const_iterator it;
};
class LFUCache {
public:
LFUCache(int capacity): capacity_(capacity), min_freq_(0){}
int get(int key) {
auto it = n_.find(key);
if (it == n_.cend()) return -1;
touch(it->second);
return it->second.value;
}
void put(int key, int value) {
if (capacity_ == 0) return;
auto it = n_.find(key);
if (it != n_.cend()) {
// key already exists, updata the value and touch it
it->second.value = value;
touch(it->second);
return;
}
if (n_.size() == capacity_) {
// capacity empty, remove one entry that
// 1. has lowest freq
// 2. least recently used if there are multiple ones
// step 1: rempve the elem from min_freq_ list
const int key_to_evict = l_[min_freq_].back();
l_[min_freq_].pop_back();
// step 2: remove the key from cache;
n_.erase(key_to_evict);
}
// we know new item has freq of 1, thus set min_freq_ to 1
const int freq = 1;
min_freq_ = freq;
// add key to the freq list
l_[freq].push_front(key);
// create a new node
n_[key] = { key, value, freq, l_[freq].cbegin() };
}
private:
void touch(CacheNode& node) {
// step 1: updata the freq
const int prev_freq = node.freq;
const int freq = ++(node.freq);
// step 2: remove the entry from old freq list
l_[prev_freq].erase(node.it);
if (l_[prev_freq].empty() && prev_freq == min_freq_) {
// delete the list
l_.erase(prev_freq);
// increase the min_freq
++min_freq_;
}
// step 4: insert the key to the front of the new freq list
l_[freq].push_front(node.key);
// step 5: update the pointer
node.it = l_[freq].cbegin();
}
int capacity_;
int min_freq_;
// key -> cachenode
unordered_map<int, CacheNode> n_;
// freq -> keys with freq
unordered_map<int, list<int>> l_;
};
};
C++ 解法, 执行用时: 84ms, 内存消耗: 10564KB, 提交时间: 2021-09-07
class Solution {
public:
/**
* lfu design
* @param operators int整型vector<vector<>> ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> LFU(vector<vector<int> >& operators, int k) {
// write code here
vector<int> res;
capacity=k;
minfre=1;
for(vector<int> ope:operators)
{
if(ope[0]==1)
set(ope[1],ope[2]);
else if(ope[0]==2)
res.push_back(get(ope[1]));
}
return res;
}
void init(int k)
{
capacity = k;
minfre=1;
}
void set(int key,int val)
{
auto iter = kvf.find(key);
if(iter == kvf.end())
{
if(kvf.size()==capacity)
{
kvf.erase(frehash[minfre][0]);
frehash[minfre].erase(frehash[minfre].begin());
}
minfre=1;
frehash[minfre].push_back(key);
kvf[key]=make_pair(val,minfre);
}
else
{
int fre = kvf[key].second;
kvf[key] = make_pair(val,fre+1);
frehash[fre].erase(find(frehash[fre].begin(),frehash[fre].end(),key));
frehash[fre+1].push_back(key);
while(frehash[minfre].empty())
++minfre;
}
}
int get(int key)
{
auto iter = kvf.find(key);
if(iter == kvf.end())
return -1;
int val = iter->second.first;
int fre = iter->second.second;
kvf[key] = make_pair(val,fre+1);
frehash[fre].erase(find(frehash[fre].begin(),frehash[fre].end(),key));
frehash[fre+1].push_back(key);
while(frehash[minfre].empty())
++minfre;
return val;
}
private:
unordered_map<int,vector<int> > frehash;
unordered_map<int,pair<int,int> > kvf;
int capacity,minfre;
};
C++ 解法, 执行用时: 85ms, 内存消耗: 10588KB, 提交时间: 2021-09-07
class Solution {
public:
int minfreq; //当前最小的频率
int capacity; //容量
struct Node{
int key,value,freq;
Node(int _key,int _value,int _freq):key(_key),value(_value),
freq(_freq) {}
};
list<Node> l;
unordered_map<int, list<Node>::iterator> key_table;
//记录单个list节点和key的关系
unordered_map<int,list<Node>> freq_table;
//同一个freq下可能有多个list节点，即是个双向链表
void set(int key,int value){
auto it = key_table.find(key);
if(it != key_table.end()){
//如果key已经存在了，
int currfreq = it->second->freq;
freq_table[currfreq].erase(it->second); //删掉该节点
if (freq_table[currfreq].size() == 0) {
freq_table.erase(currfreq);
if (minfreq == currfreq) minfreq += 1;
}
freq_table[currfreq + 1].push_front(Node(key,value,currfreq + 1));
key_table[key] = freq_table[currfreq + 1].begin();
}
else{
//如果key不存在，如果keytable没满
if(key_table.size() >= capacity){
auto it2 = freq_table[minfreq].back();
key_table.erase(it2.key); //清除keytable
freq_table[minfreq].pop_back(); //清除freqtable
//如果空了就全删掉
if (freq_table[minfreq].size() == 0) {
freq_table.erase(minfreq);
}
}
freq_table[1].push_front(Node(key,value,1));
key_table[key] = freq_table[1].begin();
minfreq = 1;
}
}
int get(int key){
if(key_table.empty()){
//如果内存为空
return -1;
}
auto it = key_table.find(key);
if(it == key_table.end()){
//如果it是末尾，即内存中没有这个对
return -1;
}
//内存中有
int currval = it->second->value;
int currfreq = it->second->freq;
//通过freq找到其频率，修改频率
freq_table[currfreq].erase(it->second); //删掉该节点
if (freq_table[currfreq].size() == 0) {
//如果删掉后当前位置链表为空了，就删掉这个对
freq_table.erase(currfreq);
if (minfreq == currfreq) minfreq += 1;
//如果这就是当前最小的频率
//minfreq+1就是等会要新加入的节点的频率
}
//更新两个表的新freq
freq_table[currfreq + 1].push_front(Node(key,currval,currfreq + 1));
key_table[key] = freq_table[currfreq + 1].begin();
return currval; //返回当前值
}
vector<int> LFU(vector<vector<int> >& operators, int k) {
// write code here
capacity = k;
minfreq = 0;
vector<int> res;
for(auto vec: operators){
if(vec[0] == 1){
set(vec[1],vec[2]);
}
else
res.push_back(get(vec[1]));
}
return res;
}
};
C++ 解法, 执行用时: 86ms, 内存消耗: 10476KB, 提交时间: 2022-02-08
class Solution {
public:
vector<int> res;
unordered_map<int,list<vector<int>>> cnt_mp;//调用次数到链表的映射
unordered_map<int,list<vector<int>>::iterator> mp;//键到链表地址的映射
int mi=0;//最小调用次数
int m;//剩余缓存大小
vector<int> LFU(vector<vector<int> >& operators, int k) {
m=k;
int n=operators.size();
for(int i=0;i<n;i++){//遍历操作数组
if(operators[i][0]==1){
set(operators[i][1],operators[i][2]);
}else{
get(operators[i][1]);
}
}
return res;
}
void update(list<vector<int>>::iterator it,int x,int y){//删除节点，并将调用次数+1，插入新节点
int num=(*it)[0];//找到目前调用次数
cnt_mp[num].erase(it);//删除节点
if(cnt_mp[num].size()==0) {
if(mi==num)
mi++;//最小调用次数+1
}
cnt_mp[num+1].push_front({num+1,x,y});//插入调用次数+1的新节点
mp[x]=cnt_mp[num+1].begin();
}
void set(int x,int y){
auto it=mp.find(x);
if(it!=mp.end()){//键存在，则重新赋值
update(it->second,x,y);//更新调用次数
}else{//键不存在
if(m==0){//缓存已满，则删除节点
int key=cnt_mp[mi].back()[1];//找到要删除节点的键
cnt_mp[mi].pop_back();
mp.erase(key);
}else{
m--;//缓存-1
}
mi=1;//最小调用次数置为1
cnt_mp[1].push_front({1,x,y}); //在调用次数为1的链表表头插入该键
mp[x]=cnt_mp[1].begin();
}
}
void get(int x) {
auto it=mp.find(x);
if(it!=mp.end()){//键存在
update(it->second,x,(*(it->second))[2]);//更新操作
res.push_back((*(it->second))[2]);
}else{//键不存在
res.push_back(-1);
}
}
};
C++ 解法, 执行用时: 86ms, 内存消耗: 10504KB, 提交时间: 2021-09-20
struct Node {
int key;
int value;
int fre;
Node* pre;
Node* aft;
Node(int k, int val) {
key=k;
value=val;
fre=1;
pre=aft=nullptr;
}
};
void RemoveFromQueue(Node* root) {
root->pre->aft=root->aft;
root->aft->pre=root->pre;
}
void RemoveLastFre(unordered_map<int,Node*>& frequery, unordered_map<int,Node*>& mp) {
for(int i=1;i<100001;++i) {
if(frequery.count(i)) {
Node *tem=frequery[i]->pre;
RemoveFromQueue(tem);
mp.erase(tem->key);
delete tem;
tem=frequery[i];
if(tem->pre==tem) {
//删除后链表为空
// delete tem;
frequery.erase(i);
}
return ;
}
}
}
void InsertNode(Node* head, Node* tem) {
tem->aft=head->aft;
tem->pre=head;
head->aft=tem;
tem->aft->pre=tem;
}
class Solution {
public:
/**
* lfu design
* @param operators int整型vector<vector<>> ops
* @param k int整型 the k
* @return int整型vector
*/
vector<int> LFU(vector<vector<int> >& operators, int k) {
unordered_map<int,Node*> mp;
unordered_map<int,Node*> frequery;
int count=0;
vector<int> res;
for(vector<int>& cur:operators) {
if(cur[0]==1) {
//set(x,y);
Node* tem=nullptr;
if(mp.count(cur[1])) {
tem=mp[cur[1]];
tem->value=cur[2];
++(tem->fre);
RemoveFromQueue(tem);
} else {
tem=new Node(cur[1],cur[2]);
mp[cur[1]]=tem;
++count;
if(count>k) {
RemoveLastFre(frequery,mp); //删除使用次数最少的
--count;
}
}
if(frequery.count(tem->fre)==0) {
frequery[tem->fre]=new Node(0,0); //头结点
frequery[tem->fre]->pre=frequery[tem->fre]->aft=frequery[tem->fre];
}
InsertNode(frequery[tem->fre],tem);
} else {
if(mp.count(cur[1])==0) {
res.push_back(-1);
} else {
Node *tem=mp[cur[1]];
res.push_back(tem->value);
tem->fre++;
RemoveFromQueue(tem);
if(frequery.count(tem->fre)==0) {
frequery[tem->fre]=new Node(0,0); //头结点
frequery[tem->fre]->pre=frequery[tem->fre]->aft=frequery[tem->fre];
}
InsertNode(frequery[tem->fre],tem);
}
}
}
return res;
}
};
，
)
，空间复杂度是 )