視頻講解

哈希 + 雙向鏈表

為什么要用雙向鏈表？

快速刪除節點（O(1））

如果是單鏈表的話，刪除一個節點時，需要從頭遍歷，找到前驅節點，才能修改 prev->next，導致 O(n) 的時間復雜度。

雙向鏈表存儲了兩個指針，一個指針指向下一個節點，另一個指針指向上一個節點（前驅指針）。所以我們可以根據前驅指針快速找到上一個節點，然后移除掉當前節點。

demo：

class LRUCache {
public:struct Node{int key,val;Node *prev,*next;Node(int k,int v) : key(k) , val(v) , prev(nullptr) , next(nullptr){}};map<int,Node*>mp;Node *L,*R; //雙哨兵int n; //LRU的總數//創建操作LRUCache(int capacity) {n = capacity;L = new Node(-1,-1);R = new Node(-1,-1);L->next = R;R->prev = L;}//獲取值操作 (獲得值的時候需要注意：如果有值存在哈希表中的話，那么就要將這個值放在最新的地方)//比如： L | 2 1 4 | R //我們查詢1這個數，那么查完后需要變成： L | 2 4 1 | R int get(int key) {if(mp.count(key)){Node* node = mp[key];remove(node); //在鏈表中移除該節點 通過雙向指針移除insert(node->key,node->val); // 在鏈表中插入該節點return node->val;}else{return -1;}}//插入操作void put(int key, int value) {if(mp.count(key)){Node* node = mp[key];remove(node);insert(key,value); //這里需要用給的key和value而不是node->key和node->val（因為可能插入的是新的值）}else{if(mp.size() == n){Node* node = L->next; //滿了，需要移除的節點remove(node);insert(key,value);}else{insert(key,value);}}}//以下為自定義新增函數 remove是移除節點的函數 insert是插入節點的函數//同時在鏈表和哈希表中刪除nodevoid remove(Node* node){Node* pre = node->prev;Node* nxt = node->next;pre->next = nxt;nxt->prev = pre;mp.erase(node->key);}//同樣要同時操作鏈表和哈希表void insert(int key,int val){Node* node = new Node(key,val);Node* pre = R->prev;//這里是最后一個插入的數//向右pre->next = node;node->next = R;//向左node->prev = pre;R->prev = node;mp[key] = 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);*/