leetcode

commit c926f8287222d08199836081520b25db1c3c058c
parent fcbe5a5631c5a8bd65ff903744f1595198996e66
Author: Dimitrije Dobrota <mail@dimitrijedobrota.com>
Date:   Tue, 18 Jul 2023 23:00:49 +0200

Daily Problem

Diffstat:
A
Problems/0146.cpp
 | 
37
+++++++++++++++++++++++++++++++++++++
M
README.md
 | 
1
+

2 files changed, 38 insertions(+), 0 deletions(-)
diff --git a/Problems/0146.cpp b/Problems/0146.cpp
@@ -0,0 +1,37 @@
+class LRUCache {
+  unordered_map<int, pair<int, int>> um;
+  queue<pair<int, int>> q;
+  int capacity;
+
+public:
+  LRUCache(int capacity) : capacity(capacity) {}
+
+  int get(int key) {
+    auto it = um.find(key);
+    if (it == um.end()) return -1;
+    q.push({key, ++it->second.first});
+    return it->second.second;
+  }
+
+  void put(int key, int value) {
+    auto it = um.find(key);
+    if (it != um.end()) {
+      q.push({key, ++it->second.first});
+      it->second.second = value;
+      return;
+    }
+
+    if (um.size() == capacity) {
+      while (true) {
+        auto [key, time] = q.front();
+        q.pop();
+        if (um[key].first == time) {
+          um.erase(key);
+          break;
+        }
+      }
+    }
+    q.push({key, 0});
+    um[key] = {0, value};
+  }
+};
diff --git a/README.md b/README.md
@@ -152,6 +152,7 @@ for solving problems.
 |  0143  |   Medium   | [Reorder List](Problems/0143.cpp)                                                                |
 |  0144  |   Medium   | [Binary Tree Preorder Traversal](Problems/0144.cpp)                                              |
 |  0145  |    Easy    | [Binary Tree Postorder Traversal](Problems/0145.cpp)                                             |
+|  0146  |   Medium   | [LRU Cache](Problems/0146.cpp)                                                                   |
 |  0148  |   Medium   | [Sort List](Problems/0148.cpp)                                                                   |
 |  0149  |    Hard    | [Max Points on a Line](Problems/0149.cpp)                                                        |
 |  0150  |   Medium   | [Evaluate Reverse Polish Notation](Problems/0150.cpp)                                            |