当前位置：首页 > article >正文

【数据结构与算法】LRUCache

article 2024/11/14 12:47:46

实现LRUCache

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

函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

// 结点类
struct Node {
    int key_, value_;
    Node *prev, *next;
    Node(int k = 0, int v = 0): key_(k), value_(v), prev(nullptr), next(nullptr) {}
};

class LRUCache {
public:
    int size_, cap_;
    Node *head, *tail;
    unordered_map<int, Node *> h;

    LRUCache(int capacity) {
        size_ = 0;
        cap_ = capacity;
        head = new Node();
        tail = new Node();
        head->next = tail;
        tail->prev = head;
    }
    
    int get(int key) {
        if(!h.count(key)) {
            return -1;
        } else { // 访问一个元素后，将其移动到头结点
            RemoveNode(h[key]);
            AddNodeToHead(h[key]);
            return h[key]->value_;
        }
    }
    
    void put(int key, int value) {
        if(h.count(key)) {
            RemoveNode(h[key]);
            AddNodeToHead(h[key]);
            h[key]->value_ = value;
        } else {
            if(size_ == cap_) { // LRU容量不够，删除链表尾元素
                h.erase(tail->prev->key_);
                RemoveNode(tail->prev);
                size_--;
            }
            h[key] = new Node(key, value);
            AddNodeToHead(h[key]);
            size_++;
        }
    }

    // 从双向链表中删除某个结点
    void RemoveNode(Node *node) {
        node->prev->next = node->next;
        node->next->prev = node->prev;
    }

    // 将node插入到头结点之后
    void AddNodeToHead(Node *node) {
        node->prev = head;
        node->next = head->next;

        head->next->prev = node;
        head->next = node;
    }
};