LeetCode-Solutions-in-Cpp17

Solutions to high-frequency interview questions of LeetCode in C++17, taking into account both efficiency and comprehensibility.

---

Project maintained by downdemo Hosted on GitHub Pages — Theme by mattgraham

• 只要执行了 get 或 put 的数据，就是最近使用的数据。额外用一个队列存储 key，每次 get 或 put 时，则把该 key 提取到队列最前方，这样越靠前就是越常用的。当元素超出上限时，弹出队尾的 key 即可

class LRUCache {
 public:
  explicit LRUCache(int capacity) : n(capacity) {}

  int get(int key) {
    if (n == 0 || !m.count(key)) {
      return -1;
    }
    q.remove(key);         // 从队列中删除该key
    q.emplace_front(key);  // 再添加到队首
    return m[key];
  }

  void put(int key, int value) {
    if (n == 0) {
      return;
    }
    if (m.count(key)) {      // 已存在该key
      m[key] = value;        // 修改值
      q.remove(key);         // 从队列中删除该key
      q.emplace_front(key);  // 再添加到队首
      return;
    }
    if (size(m) == n) {    // 不存在该 key 且到达容量上限
      m.erase(q.back());   // 移除该元素
      q.pop_back();        // 移除队尾的key
    }                      // 容量重新到达未满状态
    q.emplace_front(key);  // 添加key到队首
    m.emplace(key, value);
  }

 private:
  int n;
  list<int> q;
  unordered_map<int, int> m;
};

• std::list::remove 要先查找元素再删除，时间复杂度为 O(n)，使用std::list::erase 能将时间复杂度优化到 O(1)，为此用哈希表保存 std::list 的迭代器，令 std::list 保存 key 和 value 即可

class LRUCache {
 public:
  explicit LRUCache(int capacity) : n(capacity) {}

  int get(int key) {
    if (n == 0 || !m.count(key)) {
      return -1;
    }
    q.splice(begin(q), q, m[key]);  // 提到队首
    return q.front().second;
  }

  void put(int key, int value) {
    if (n == 0) {  // 已存在该key
      return;
    }
    if (m.count(key)) {
      q.splice(begin(q), q, m[key]);  // 提到队首
      q.front().second = value;       // 修改值
      return;
    }
    if (size(m) == n) {  // 不存在该 key 且到达容量上限
      m.erase(q.back().first);
      q.pop_back();
    }  // 容量重新到达未满状态
    q.emplace_front(key, value);
    m.emplace(key, begin(q));
  }

 private:
  int n;
  list<pair<int, int>> q;  // 仍要保存 key，在哈希表中移除时要知道队尾元素的 key
  unordered_map<int, list<pair<int, int>>::iterator> m;
};