题目描述

146. LRU Cache

 

哈希表+双向链表

详见代码和注释：

class LRUCache {
private:int capacity_{0};int size_{0};struct Node{int key{0};int val{0};Node* pre{nullptr};Node* next{nullptr};Node(int k,int v,Node* pr,Node* nex):key(k),val(v),pre(pr),next(nex){}};Node* head_{nullptr};Node* tail_{nullptr};//使用哈希表让查找的时间复杂度降为O(1)unordered_map<int,Node*> data_;public:LRUCache(int capacity):capacity_(capacity) {//题目保证传入大于0的capacity,非法值没考虑}int get(int key) {if(data_.contains(key)){Node* node = data_[key];setHead(node);return node->val;}return -1;}void put(int key, int value) {if(data_.contains(key)){data_[key]->val = value;setHead(data_[key]);}else{if(capacity_ > 0 && size_ == capacity_){//缓存已满Node* to_delete_LRU_node = tail_;//需要删除尾结点,tail_结点就是Least Recently Used Nodetail_ = tail_->pre;//有可能tail_和head_是同一个结点，tail_->pre是nullptrif(tail_){//to_delete_LRU_node的前面还有结点tail_->next = nullptr;}else{//to_delete_LRU_node的前面已经没有结点,to_delete_LRU_node和head_指向同一个结点//下面会通过to_delete_LRU_node销毁头结点,需要将head_设置为nullptr,不能让head_指向不存在的内存head_ = nullptr;}data_.erase(to_delete_LRU_node->key);delete to_delete_LRU_node;size_--;}Node* newnode = new Node(key,value,nullptr,head_);if(head_){head_->pre = newnode;}else{//如果头结点head_不存在,那么尾结点tail_也一定不存在tail_ = newnode;}head_ = newnode;data_[key] = newnode;size_++;}}
private://将node设置为链表的头结点,输入的node不为nullptrvoid setHead(Node* node){if(node != head_){if(node == tail_){//node是尾结点的话,node前一个结点需要作为新的尾结点tailtail_ = tail_->pre;}// if(node->pre) 判断是多余的,node不是头结点,那么node的前一个结点一定不是nullptrnode->pre->next = node->next;if(node->next){//node的下一个结点可能不存在node->next->pre = node->pre;}node->pre = nullptr;node->next = head_;//前面的条件保证了此处head_一定不为nullptrhead_->pre = node;head_ = 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);*/

几组测试用例：

["LRUCache","put","put","get","put","get","put","get","get","get"][[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

["LRUCache","put","put","get","put","get","put","get","get","get"][[2],[1,0],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]]

["LRUCache","put","get","put","get","get"][[1],[2,1],[2],[3,2],[2],[3]]