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/lru_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/lru_cache.cpp')
-rw-r--r-- | other/lru_cache.cpp | 60 |
1 files changed, 60 insertions, 0 deletions
diff --git a/other/lru_cache.cpp b/other/lru_cache.cpp new file mode 100644 index 0000000..f8d1656 --- /dev/null +++ b/other/lru_cache.cpp @@ -0,0 +1,60 @@ +// 146. LRU Cache +#include "leetcode.h" + +/* + * design a data structure that follows the constraints of a least recently used + * cache (LRU). implete the 'LRUCache' class. the functions 'get' and 'put' must + * each run in O(1) average time complexity + */ + +class LRUCache { +private: + typedef list<int> li; + typedef pair<int, li::iterator> pii; + typedef unordered_map<int, pii> hipii; + hipii cache; + li used; + int _capacity; + void touch(hipii::iterator i) { + int key = i->first; + used.erase(i->second.second); + used.push_front(key); + i->second.second = used.begin(); + } + +public: + LRUCache(int capacity) { _capacity = capacity; } + int get(int key) { + auto i = cache.find(key); + if (i == cache.end()) + return -1; + touch(i); + return i->second.first; + } + void put(int key, int value) { + auto i = cache.find(key); + if (i != cache.end()) + touch(i); + else { + if (cache.size() == _capacity) { + cache.erase(used.back()); + used.pop_back(); + } + used.push_front(key); + } + cache[key] = {value, used.begin()}; + } +}; + +int main() { + LRUCache *obj = new LRUCache(2); + obj->put(1, 1); + obj->put(2, 2); + printf("%d\n", obj->get(1)); // expect: 1 + obj->put(3, 3); + printf("%d\n", obj->get(2)); // expect: -1 + obj->put(4, 4); + printf("%d\n", obj->get(1)); // expect: -1 + printf("%d\n", obj->get(3)); // expect: 3 + printf("%d\n", obj->get(4)); // expect: 4 +} |