LeetCode.cpp/src/leetcode/problems/lru-cache.cpp at main · 0xMashiro/LeetCode.cpp · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

#include "leetcode/problems/lru-cache.h"

namespace leetcode {
namespace problem_146 {

int LRUCache::get(int key) {
  if (hash_.find(key) == hash_.end()) return -1;
  auto it = hash_[key];
  int value = it->second;
  cache_.erase(it);
  cache_.push_front({key, value});
  hash_[key] = cache_.begin();
  return value;
}

void LRUCache::put(int key, int value) {
  if (hash_.find(key) != hash_.end()) {
    auto it = hash_[key];
    cache_.erase(it);
    cache_.push_front({key, value});
    hash_[key] = cache_.begin();
  } else {
    if (cache_.size() == capacity_) {
      hash_.erase(cache_.back().first);
      cache_.pop_back();
    }
    cache_.push_front({key, value});
    hash_[key] = cache_.begin();
  }
}

}  // namespace problem_146
}  // namespace leetcode