1. 原題鏈接：https://leetcode.com/problems/lru-cache/
2. 解題思路
- 為了增刪改查都有較高的性能，使用雙向鏈表和哈希表的組合
- 針對LRU，哈希表對于查詢和修改可以實作O(1)的時間復雜度，但是無法在O(1)時間復雜度實作洗掉操作
- 雙向鏈表可以很好的實作O(1)時間復雜度的增加和洗掉，因此需要將雙向鏈表和哈希表結合起來一起使用，這兩種資料結構的結合點在于哈希表的value存盤的是雙向鏈表某個節點的地址（也就是：哈希表的value是一個指向雙向鏈表某個節點的指標）
- 越靠近雙向鏈表頭部的節點，表示你最近剛訪問過，越靠近雙向鏈表尾部的節點，表示最近很少訪問，最后一個節點表示最近訪問最少
3. 演算法
- 對于get操作，如果節點存在將其從當前位置摘除，并將該節點插入到鏈表頭部；否則，回傳-1
- 對于put操作，如果key存在，更新value；否則，檢查當前capacity是否已滿，如果已滿，洗掉最后一個節點（也就是：最近最少訪問的節點）和哈希表對應的key；然后，創建包含key、value的新節點，將其插入鏈表頭部
4. 實作
struct Node {
int key; //為了洗掉節點時，同時洗掉hash表中的key
int val;
Node *next;
Node *prev;
Node(int k, int v){
key = k;
val = v;
next = NULL;
prev = NULL;
}
};
class LRUCache {
public:
LRUCache(int capacity) {
size = capacity;
//啞節點可以化解很多例外情況
Node *dummy1 = new Node(-1, -1);
Node *dummy2 = new Node(-1, -1);
head = dummy1;
tail = dummy2;
head->next = dummy2;
tail->prev = dummy1;
}
int get(int key) {
map<int, Node*>::iterator iter;
iter = table.find(key);
if(iter != table.end()){
Node *cur = iter->second;
//從當前位置摘掉
cur->prev->next = cur->next;
cur->next->prev = cur->prev;
//將該節點插入頭部
cur->next = head->next;
cur->prev = head;
head->next->prev = cur;
head->next = cur;
return cur->val;
}
return -1;
}
void put(int key, int value) {
if(get(key) > 0){
//更新已存在key的value
// head->next->val = value;
table[key]->val = value;
return;
}
//當容量為0時，先洗掉，再插入
if(size == 0){
Node *del_node = tail->prev;
del_node->next->prev = del_node->prev;
del_node->prev->next = del_node->next;
del_node->prev = NULL;
del_node->next = NULL;
//先洗掉hash表中的key，再洗掉節點
table.erase(del_node->key);
delete del_node;
size++;
}
Node *node = new Node(key, value);
//將其插入頭部
node->next = head->next;
node->prev = head;
head->next->prev = node;
head->next = node;
table[key] = node;
size--;
}
private:
map<int, Node*> table;
int size;
Node *head;
Node *tail;
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/85165.html
標籤：其他
上一篇：二叉搜索樹的后序遍歷序列
下一篇：資料結構-線性結構