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

力扣HOT100之链表：146. LRU 缓存

news 2025/5/11 13:06:09

这道题从来没做过，完全不知道该怎么写，直接去看视频了，感觉这个视频讲解的挺好的。
这道题主要是需要自己额外定义数据结构和函数，需要定义节点结构体，用于存放键值对，每个节点都有前后指针，所以这道题是采用哈希表+双向链表的做法来做的。这道题添加和删除节点的逻辑都很好理解，最难想到的就是当插入节点，但缓存已满时，如何找到最久未使用的节点，这个实现起来不难，每一次插入节点都从头部插入，不常使用的节点总是在链表的最末端，所以我们只需要将末端的节点删除即可。

//定义节点
struct Node{int key, val;Node *pre, *next;Node() : key(0), val(0), pre(nullptr), next(nullptr){}Node(int _key, int _val) : key(_key), val(_val), pre(nullptr), next(nullptr){}
};class LRUCache {
public:Node *head, *tail;   //双向链表的头节点和尾节点unordered_map<int, Node*> hash;    //内部维护一个哈希表int capacity, size;   //容量和当前元素个数LRUCache(int _capacity) {capacity = _capacity;size = 0;head = new Node();tail = new Node();head -> next = tail;tail -> pre = head;}int get(int key) {if(!hash.count(key))return -1;Node* node = hash[key];removeNode(node);addNodeHead(node);return node -> val;}void put(int key, int value) {if(hash.count(key)){   //该键已经存在Node* node = hash[key];node -> val = value;removeNode(node);addNodeHead(node);}else{   //插入的为新键if(size >= capacity){  //已经达到最大容量Node* removed = tail -> pre;  //删除双向链表中的最后一个节点hash.erase(removed -> key);  //及时从哈希表中删除不活跃节点对应的键removeNode(removed);size--;}Node *node = new Node(key, value);addNodeHead(node);hash[key] = node;size++;}}//自定义删除节点函数void removeNode(Node *node){node -> pre -> next = node -> next;node -> next -> pre = node -> pre;}//自定义添加节点函数void addNodeHead(Node *node){node -> pre = head;node -> next = head -> next;head -> next -> pre = node;head -> next = node;}};/*** Your LRUCache object will be instantiated and called as such:* LRUCache* obj = new LRUCache(capacity);* int param_1 = obj->get(key);* obj->put(key,value);*/