leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

0146.cpp (911B)

      1 class LRUCache {
      2     unordered_map<int, pair<int, int>> um;
      3     queue<pair<int, int>> q;
      4     int capacity;
      5 
      6   public:
      7     LRUCache(int capacity) : capacity(capacity) {}
      8 
      9     int get(int key) {
     10         auto it = um.find(key);
     11         if (it == um.end()) return -1;
     12         q.push({key, ++it->second.first});
     13         return it->second.second;
     14     }
     15 
     16     void put(int key, int value) {
     17         auto it = um.find(key);
     18         if (it != um.end()) {
     19             q.push({key, ++it->second.first});
     20             it->second.second = value;
     21             return;
     22         }
     23 
     24         if (um.size() == capacity) {
     25             while (true) {
     26                 auto [key, time] = q.front();
     27                 q.pop();
     28                 if (um[key].first == time) {
     29                     um.erase(key);
     30                     break;
     31                 }
     32             }
     33         }
     34         q.push({key, 0});
     35         um[key] = {0, value};
     36     }
     37 };