aboutsummaryrefslogtreecommitdiff
path: root/other/lru_cache.cpp
diff options
context:
space:
mode:
authorJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
committerJack Sangdahl <[email protected]>2025-03-10 00:36:13 -0600
commit7c60dee83b436e8e8a667bf9f191beced8de4fc3 (patch)
treeeb7a24ee2067f92245c57bb118e85a1baf15df50 /other/lru_cache.cpp
parent5d7cdc215e4ba1ec4cbb24c084cccb5e5e641468 (diff)
downloadleetcode-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.cpp60
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
+}