diff options
author | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
---|---|---|
committer | Jack Sangdahl <[email protected]> | 2025-03-10 00:36:13 -0600 |
commit | 7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch) | |
tree | eb7a24ee2067f92245c57bb118e85a1baf15df50 /other/lfu_cache.cpp | |
parent | 5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff) | |
download | leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.tar.gz leetcode-7c60dee83b436e8e8a667bf9f191beced8de4fc3.zip |
chore: move cpp and rust code to directory
Diffstat (limited to 'other/lfu_cache.cpp')
-rw-r--r-- | other/lfu_cache.cpp | 69 |
1 files changed, 69 insertions, 0 deletions
diff --git a/other/lfu_cache.cpp b/other/lfu_cache.cpp new file mode 100644 index 0000000..c0c857a --- /dev/null +++ b/other/lfu_cache.cpp @@ -0,0 +1,69 @@ +// 460. LFU Cache +#include <bits/stdc++.h> +#include <unordered_map> +using namespace std; + +// https://en.wikipedia.org/wiki/Least_frequently_used +// http://dhruvbird.com/lfu.pdf + +struct Node { + int value; + list<int>::iterator itr; +}; + +class LFUCache { +private: + unordered_map<int, Node> umVal; + unordered_map<int, int> umCount; + unordered_map<int, list<int>> umlCountKey; + int lowFreq, maxCap; + +public: + LFUCache(int capacity) { + maxCap = capacity; + lowFreq = 0; + } + int get(int key) { + if (umVal.find(key) == umVal.end() || maxCap <= 0) + return -1; + put(key, umVal[key].value); + return umVal[key].value; + } + void put(int key, int value) { + if (maxCap <= 0) + return; + if (umVal.find(key) == umVal.end()) { + if (umVal.size() == maxCap) { + int del = umlCountKey[lowFreq].back(); + umlCountKey[lowFreq].pop_back(); + if (umlCountKey[lowFreq].empty()) + umlCountKey.erase(lowFreq); + umVal.erase(del); + umCount.erase(del); + } + umVal[key].value = value; + umCount[key] = 0; + lowFreq = 0; + umlCountKey[umCount[key]].push_front(key); + umVal[key].itr = umlCountKey[0].begin(); + } else { + umlCountKey[umCount[key]].erase(umVal[key].itr); + if (umlCountKey[umCount[key]].empty()) { + if (lowFreq == umCount[key]) + lowFreq++; + umlCountKey.erase(umCount[key]); + } + umVal[key].value = value; + umCount[key]++; + umlCountKey[umCount[key]].push_front(key); + umVal[key].itr = umlCountKey[umCount[key]].begin(); + } + } +}; + +int main() { + int capacity, key, value; + LFUCache *obj = new LFUCache(capacity); + int param_1 = obj->get(key); + obj->put(key, value); +} |