460. LFU Cache O(1)算法 C++

2019-11-10 22:38:51

字體：大中小

來源：轉載

供稿：網友

LeetCode 460.LFU Cache的解法，算法時間復雜度為O(1).實際在Leetcode平臺跑所耗時間為126ms，基本上超越96%吧主要使用了雙重鏈表和hash表的數據結構來實現，hash用于快速查找，雙重鏈表用于替換策略和存儲。#include <list>#include <unordered_map>struct Node{ int key; int value; std::list<struct FreqList>::iterator parent;};struct FreqList{ std::list<struct Node> FList; int Freq;};class LFUCache{public: LFUCache(int capacity); ~LFUCache(); void put(int key, int value); int get(int key);PRivate: std::list<struct FreqList> CacheList; std::unordered_map<int,std::list<struct Node>::iterator > hash_map; int capacity; int size;};using namespace std;LFUCache::LFUCache(int capacity):capacity(capacity),size(0){ struct FreqList flst; flst.Freq = 1; CacheList.push_front(flst);}LFUCache::~LFUCache(){}void LFUCache::put(int key, int value){ if(capacity <= 0) return; unordered_map<int, list<struct Node>::iterator>::iterator got; list<struct FreqList>::reverse_iterator clst_rit; list<struct FreqList>::iterator clst_it; list<struct Node>::iterator nd_it; struct Node nd; nd.key = key; nd.value = value; //在cache存在記錄，先插入，后刪除，最后更新hash_table got = hash_map.find(key); if (got != hash_map.end()) { //比較大小，看是重新建立一個還是使用上一個FreqList int current_freq, pre_freq; nd_it = hash_map[key]; clst_it = nd_it->parent; current_freq = clst_it->Freq; list<struct FreqList>::iterator current_clst_it; current_clst_it = clst_it; if (clst_it != CacheList.begin()) { --clst_it; } pre_freq = clst_it->Freq; //刪除記錄 current_clst_it->FList.erase(nd_it); if (pre_freq == current_freq + 1)//前一個剛好是后一個+1的關系，直接插入到前一個的頭部即可 { nd.parent = clst_it; clst_it->FList.push_front(nd); } else //否則需要在當前的CacheList節點前重新建立一個FreqList節點 { struct FreqList flst_nd; flst_nd.Freq = current_freq + 1; clst_it = CacheList.insert(current_clst_it,flst_nd); nd.parent = clst_it; clst_it->FList.push_front(nd); } //若為空則刪除CacheList的節點 if (current_clst_it->FList.size() == 0) { CacheList.erase(current_clst_it); } //更新hash表 hash_map[key] = clst_it->FList.begin(); } //在Cache中不存在記錄，且Cache未滿,直接插入即可 else if (size < capacity) { clst_rit = CacheList.rbegin(); //假如最后一個Freq不是1，則創建一個 if (clst_rit->Freq != 1) { struct FreqList flst_tmp; flst_tmp.Freq = 1; CacheList.push_back(flst_tmp); clst_rit = CacheList.rbegin(); } nd.parent = CacheList.end(); nd.parent--; clst_rit->FList.push_front(nd); //更新hash_table hash_map[key] = clst_rit->FList.begin(); size++; } else//Cache中不存在，且Cache已滿，尋找合適位置替換即可 { //根據hash記錄需要刪除的條目 list<struct FreqList>::reverse_iterator flst_last_rit; list<struct Node>::reverse_iterator nd_last_rit; flst_last_rit = CacheList.rbegin(); nd_last_rit = flst_last_rit->FList.rbegin(); int delete_key = nd_last_rit->key; //添加，刪除,同步hash表 //1.添加 clst_rit = CacheList.rbegin(); //假如最后一個Freq不是1，則創建一個 if (clst_rit->Freq != 1) { struct FreqList flst_tmp; flst_tmp.Freq = 1; CacheList.push_back(flst_tmp); clst_rit = CacheList.rbegin(); } nd.parent = CacheList.end(); nd.parent--; clst_rit->FList.push_front(nd); //2.刪除 list<struct FreqList>::iterator parent; list<struct Node>::iterator nd_delete_it; nd_delete_it = hash_map[delete_key]; parent = nd_delete_it->parent; parent->FList.erase(nd_delete_it); hash_map.erase(delete_key); //FreqList大小為0，刪除該節點 if (parent->FList.size() == 0) { CacheList.erase(parent); } //3.同步hash表 hash_map[key] = clst_rit->FList.begin(); }}int LFUCache::get(int key){ if(capacity <= 0) return -1; struct Node nd; int ret = -1; unordered_map<int, list<struct Node>::iterator>::iterator got; list<struct Node>::iterator nd_it; list<struct FreqList>::iterator clst_it; got = hash_map.find(key); if (got != hash_map.end()) { nd_it = hash_map[key]; ret = nd_it->value; clst_it = nd_it->parent; nd.key = key; nd.value = nd_it->value; //修改使用頻率，修改，刪除，同步 //比較大小，看是重新建立一個還是使用上一個FreqList int current_freq, pre_freq; current_freq = clst_it->Freq; list<struct FreqList>::iterator current_clst_it; current_clst_it = clst_it; if (clst_it != CacheList.begin()) { --clst_it; } pre_freq = clst_it->Freq; //刪除記錄 current_clst_it->FList.erase(nd_it); if (pre_freq == current_freq + 1)//前一個剛好是后一個+1的關系，直接插入到前一個的頭部即可 { nd.parent = clst_it; clst_it->FList.push_front(nd); } else //否則需要在當前的CacheList節點前重新建立一個FreqList節點 { struct FreqList flst_nd; flst_nd.Freq = current_freq + 1; clst_it = CacheList.insert(current_clst_it, flst_nd); nd.parent = clst_it; clst_it->FList.push_front(nd); } if (current_clst_it->FList.size() == 0) { CacheList.erase(current_clst_it); } hash_map[key] = clst_it->FList.begin(); } return ret;}

上一篇：2012年第三屆藍橋杯C/C++組真題訓練（二）（2017.2.8）

下一篇：codeforces-34B-B. Sale( C++ && greedy && sortings )