題目描述

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]]