From 7c60dee83b436e8e8a667bf9f191beced8de4fc3 Mon Sep 17 00:00:00 2001 From: Jack Sangdahl Date: Mon, 10 Mar 2025 00:36:13 -0600 Subject: chore: move cpp and rust code to directory --- other/lru_cache.cpp | 60 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 60 insertions(+) create mode 100644 other/lru_cache.cpp (limited to 'other/lru_cache.cpp') 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 li; + typedef pair pii; + typedef unordered_map 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 +} -- cgit v1.2.3