leetcode146：LRU缓存

题目链接

leetcode

题目描述

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：

• LRUCache(int capacity)以 正整数 作为容量 capacity 初始化 LRU 缓存
• int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
• void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
  函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

C++ 代码

#include <iostream>
#include <vector>
#include <unordered_map>
#include <list>
using namespace std;

/*
    哈希表 + 双向链表

    时间复杂度：O(1)
        get 操作 O(1)，因为哈希表可以快速定位结点，而移动结点到头部也是 O(1) 操作。
        put 操作 O(1)，因为哈希表和链表操作都是 O(1) 复杂度。
    空间复杂度：O(capacity)
        其中 capacity 是缓存的最大容量。
        哈希表占用空间最多为 O(capacity)，链表占用空间最多为 O(capacity) 的空间。
*/
class LRUCache {
public:
    LRUCache(int capacity) {
        this->capacity = capacity;
        head = new Node(), tail = new Node();
        head->next = tail, tail->prev = head;
    }

    int get(int key) {
        // key 不存在
        if (!cache.count(key)) {
            return -1;
        }
        // key 存在
        Node* p = cache[key];
        removeNode(p);
        addNode(p);
        return p->val;
    }
    
    void put(int key, int value) {
        // key 不存在
        if (!cache.count(key)) {
            // 缓存已满
            if (cache.size() == capacity) {
                Node* p = tail->prev;
                removeNode(p);
                cache.erase(p->key);
                delete p;
                // p = nullptr;
            }
            // 缓存不满
            Node* p = new Node(key, value);
            addNode(p);
            cache[key] = p;
        } else {
            // key 存在
            Node* p = cache[key];
            p->val = value;
            removeNode(p);
            addNode(p);
        }
    }

private:
    struct Node {
        int key, val;
        Node *prev, *next;
        Node() : key(-1), val(-1), prev(nullptr), next(nullptr) {}
        Node(int k, int v) : key(k), val(v), prev(nullptr), next(nullptr) {}
    };
    // 双向链表
    Node *head, *tail;
    // 哈希表
    unordered_map<int, Node*> cache;
    // 缓存容量
    int capacity;

    // 添加一个节点到链表的头部
    void addNode(Node* p) {
        p->prev = head;
        p->next = head->next;
        head->next->prev = p;
        head->next = p;
    }

    // 从链表中删除一个节点
    void removeNode(Node* p) {
        p->next->prev = p->prev;
        p->prev->next = p->next;
    }
};

// 辅助函数：打印数组
void printArray(const vector<string>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << nums[i];
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

void printArray(const vector<int>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        if (nums[i] == NULL) {
            cout << "null";
        } else {
            cout << nums[i];
        }
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

// 辅助函数：打印二维数组
void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (size_t i = 0; i < nums.size(); i++) {
        cout << "[";
        for (size_t j = 0; j < nums[i].size(); j++) {
            cout << nums[i][j];
            if (j != nums[i].size() - 1) cout << ",";
        }
        cout << "]";
        if (i != nums.size() - 1) cout << ",";
    }
    cout << "]";
}

int main() {
    LRUCache* obj = new LRUCache(2);
    vector<string> operations = {"LRUCache","put","put","get","put","get","put","get","get","get"};
    vector<vector<int>> params = {{2},{1,1},{2,2},{1},{3,3},{2},{4,4},{1},{3},{4}};
    vector<int> output;

    for (int i = 0; i < operations.size(); i++) {
        string op = operations[i];
        if (op == "LRUCache") {
            output.push_back(NULL); // 表示无返回值
        } else if (op == "put") {
            obj->put(params[i][0], params[i][1]);
            output.push_back(NULL);
        } else if (op == "get") {
            int res = obj->get(params[i][0]);
            output.push_back(res);
        }
    }

    cout << "Input: " << endl;
    printArray(operations);
    cout << endl;
    printArray(params);
    cout << endl;
    cout << "Output: " << endl;
    printArray(output);
    cout << endl;

    delete obj;

    return 0;
}