fucking-algorithm

fucking-algorithm copied to clipboard

请在提交 bug 之前先搜索

• [X] 我已经搜索过 issues，没有发现相同的 bug。

出错的题目链接

https://leetcode.cn/problems/lru-cache/description/

报错信息

答案错误

你是否愿意提交 PR 修复这个 bug？

• [X] 我愿意！

class LRUCache { private: int cap; unordered_map<int, int> cache; // 存储key和对应的值 unordered_map<int, list::iterator> keyMap; // 存储key和对应的链表节点迭代器 list lruList; // 双向链表

public: LRUCache(int capacity) { cap = capacity; }

int get(int key) {
    if (cache.find(key) == cache.end()) {
        return -1;
    }
    makeRecently(key);
    return cache[key];
}

void put(int key, int val) {
    if (cache.find(key) != cache.end()) {
        cache[key] = val;
        makeRecently(key);
        return;
    }

    if (cache.size() >= cap) {
        int oldestKey = lruList.front();
        lruList.pop_front();
        cache.erase(oldestKey);
        keyMap.erase(oldestKey);
    }

    cache[key] = val;
    lruList.push_back(key);
    keyMap[key] = --lruList.end();
}

private: void makeRecently(int key) { auto it = keyMap[key]; lruList.erase(it); lruList.push_back(key); keyMap[key] = --lruList.end(); } };