【LeetCode热题100】【链表】LRU缓存

叶茂林

发布于 2024-03-31 08:29:14

10200

代码可运行

运行总次数：0

代码可运行

我昨天面了天美L1的游戏客户端开发，面了我100分钟，问完实习、项目、计算机图形学和C++后给了我两道算法题做，一道是最长公共子序列，一道是LRU缓存，我知道是经典的题目，但是我都没敲过，我之前写过一个KV的数据库系统用过LRU（最近最少使用）缓存，用的是双向链表和哈希表解决的，当时是实现了一个双向链表，用来存储value，哈希表存储key和对应存储value的链表节点的指针，最近被访问的key就把它的节点移到链表头，超过容量就删掉链表尾

原题：146. LRU 缓存 - 力扣（LeetCode）

手动实现一个双向链表，用来存储key和value，哈希表存储key和对应链表节点的指针，链表存储key是为了删除哈希表中的元素

get首先判断key在不在，在的话，通过哈希表找到节点指针，移动到链表开头，返回value

put首先判断key在不在，在的话，通过哈希表找到节点指针，移动到链表开头，更新value，不在的话，创建一个新的节点插到链表头，添加key和指针到哈希表，如果超过容量，根据链表尾部的key删除哈希表中的元素，再删掉该链表节点

实现细节上，为了插入和删除的方便，使用一个头部和一个尾部节点作为界限，不存储数据

class LRUCache {
private:
    struct Node {
        int key = 0, value = 0;
        Node *prev = nullptr, *next = nullptr;

        explicit Node(int key = 0, int value = 0) : key(key), value(value) {}
    };

    unordered_map<int, Node *> cache;
    Node *head, *tail;
    int size, capacity;

    inline void moveToHead(Node *node) { // 将节点插到链表头部的后面
        node->prev = head; // 牵头
        node->next = head->next; // 交尾
        head->next->prev = node; // 后面牵头
        head->next = node; // 前面交尾
    }

    inline void removeNode(Node *node) { // 从链表中摘除节点
        node->prev->next = node->next; // 前面交尾
        node->next->prev = node->prev; // 后面牵头
    }

public:
    LRUCache(int capacity) : capacity(capacity), size(0), head(new Node()), tail(new Node()) {
        head->next = tail;
        tail->prev = head;
    }

    int get(int key) {
        if (cache.find(key) == cache.end()) // 没有
            return -1;
        Node *node = cache[key];
        removeNode(node);
        moveToHead(node);
        return node->value;
    }

    void put(int key, int value) {
        Node *node = nullptr;
        if (cache.find(key) == cache.end()) { // 还没有就创建一个
            node = new Node(key, value);
            cache[key]=node;        
            size++;
        } else { // 已经有了就更新一下
            node = cache[key];
            node->value = value;
            removeNode(node);
        }
        moveToHead(node);
        if (size > capacity) { // 容量超了
            size--;
            Node *old = tail->prev;
            cache.erase(old->key); // 删除哈希表元素
            removeNode(old); // 删除链表节点
            delete old;
        }
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-03-30，如有侵权请联系 cloudcommunity@tencent.com 删除

leetcode