leetcode N刷汇总101-150题

146. LRU Cache[面试必备]

#include <bits/stdc++.h>
using namespace std;

class LRUCache {
  public:
    LRUCache(int capacity) { this->capacity = capacity; }

    int get(int key) {
        if (dir.count(key)) {
            vistied(key);
            return dir[key]->second;
        }
        return -1;
    }

    void put(int key, int value) {
        if (dir.count(key)) {
            vistied(key);
        } else {
            if (capacity <= dir.size()) {
                dir.erase(cacheList.back().first);
                cacheList.pop_back();
            }
            cacheList.push_front(make_pair(key, value));
            dir[key] = cacheList.begin();
        }
        dir[key]->second = value;
    }
    void vistied(int key) {
        auto p = *dir[key];
        cacheList.erase(dir[key]);
        cacheList.push_front(p);
        dir[key] = cacheList.begin();
    }

  private:
    unordered_map<int, list<pair<int, int>>::iterator> dir;
    list<pair<int, int>> cacheList;
    int capacity;
};