題目：
這一題在一年前就已經寫出來了，但是一年前的 Code 使用最新的測資卻會 LTE ， 於是一年後再來寫寫看這一題，希望這一年以來，我能有一些些的長進。
然而一年以後，仍舊無法把 get 以及 put 壓到 O(1)，僅僅是從原本的 O(N log (capacity)) 優化到了 O(log(capacity))，看來還是太嫩了 (´・ω・`)
以前的解法：
時間複雜度：O(N * N log(capacity))
空間複雜度：O(capacity)
N 代表呼叫 get + put 數量的總數
capacity 就是參數的那個 capacity
使用 map 來儲存鍵值對，並用一個變數來記錄目前總共容納了多少個元素。當需要拋棄 "the least recently used key" 的時候，在 map 裡遍尋 timeStamp 最小的元素。
當執行 put 或是 get 某個鍵時，就更新 timeStamp。
class LRUCache {
public:
int global_timer = 0;
map<int, vector<int>> mp;
int max_size = 0;
int now_size = 0;
LRUCache(int capacity) {
max_size = capacity;
now_size = 0;
}
int get(int key) {
if(mp.find(key) == mp.end()) {
return -1;
} else {
global_timer++;
mp[key][1] = global_timer;
return mp[key][0];
}
return 0;
}
void put(int key, int value) {
global_timer++;
if(mp.find(key) != mp.end()){
mp[key][0] = value;
mp[key][1] = global_timer;
} else if(now_size <= max_size) {
now_size++;
mp[key] = vector<int>{value, global_timer};
} else {
int min = 1e9;
int min_key;
//找到 key 最小的元素
for(auto i = mp.begin();i != mp.end();i++) {
if(i->second[1] < min) {
min = i->second[1];
min_key = i->first;
}
}
mp.erase(min_key);
mp[key] = vector<int>{value, global_timer};
}
}
};現在的解法：
時間複雜度：O(N log (capacity))
空間複雜度：O(capacity)
使用 map 來記錄 timeStamp 與 key 的對應關係。因為 map 本身是 binary search tree ， 所以使用 O(log (capacity)) 的時間，可以找出 timeStamp 最小的 key 是哪一個。
因為當需要拋棄 “the least recently used key” 的時候，每次的 get 以及 put 都需要 O(log (capacity)) 所以總時間為 O(N log(capacity))
經過這一個改善，已經可以解決 TLE 的問題了。
class LRUCache {
public:
unordered_map<int, int> k2v;
unordered_map<int, int> k2t;
map<int, int> t2k;
int c;
int nowc;
int globalt;
LRUCache(int capacity) {
c = capacity;
nowc = 0;
globalt = 0;
}
int get(int key) {
if(k2v.find(key) == k2v.end()) {
return -1;
}
globalt++;
// erease old timeStamp
int tempT = k2t[key];
t2k.erase(tempT);
k2t[key] = globalt;
t2k[globalt] = key;
return k2v[key];
}
void put(int key, int value) {
globalt++;
if(k2v.find(key) != k2v.end()) {
int tempT = k2t[key];
t2k.erase(tempT);
k2t[key] = globalt;
t2k[globalt] = key;
k2v[key] = value;
} else {
if(nowc == c) {
// evict least recently used key
int leastT = t2k.begin()->first;
int leastK = t2k[leastT];
k2v.erase(leastK);
k2t.erase(leastK);
t2k.erase(leastT);
} else {
nowc++;
}
k2v[key] = value;
k2t[key] = globalt;
t2k[globalt] = key;
}
}
};LeetCode 詳解：Hashmap + DoubleLinkedList
時間複雜度：O(N)
空間複雜度：O(capacity)
我不確定我這邊的實做是否與 LeetCode 的詳解相同，但總之這個優化可以確確實實地把 get 以及 put 操作的時間複雜度壓在 O(1) !
使用一個 hashMap 去紀錄 key <-> {value, address of Node in a doubly linked-list}。
每當一個 key 原本就存在，並被使用或更新時，就將它從 doubly linked list 裡刪除，並放在 doubly linked list 的最後面。
當一個 key 原本並不存在，就直接放在 doubly linked list 的最後面就好。
當想要拋棄 “the least recently used key” 的時候，就從 doubly linked-list 的最前端拿走那個節點就好了。
typedef struct Node Node;
struct Node{
int key;
int val;
Node *prev;
Node *next;
};class LRUCache {
public:
int c;
int nowc;
Node *head;
Node *tail;
unordered_map<int, Node *> um;
LRUCache(int capacity) {
c = capacity;
nowc = 0;
head = new Node();
head->key = -1;
head->val = -1;
tail = new Node();
tail->key = -2;
head->val = -2;
head->next = tail;
head->prev = NULL;
tail->next = NULL;
tail->prev = head;
}
int get(int key) {
if(um.find(key) == um.end()) {
return -1;
}
// update doubly linked-list
Node *nown = um[key];
Node *prevn = nown->prev;
Node *nextn = nown->next;
// delete Node
prevn->next = nextn;
nextn->prev = prevn;
// insert Node
prevn = tail->prev;
nextn = tail;
prevn->next = nown;
nextn->prev = nown;
nown->prev = prevn;
nown->next = nextn;
return um[key]->val;
}
void put(int key, int value) {
if(um.find(key) == um.end()) {
if(nowc == c) {
// delete old Node
Node *nown = head->next;
Node *prevn = head;
Node *nextn = nown->next;
prevn->next = nextn;
nextn->prev = prevn;
um.erase(nown->key);
//delete(nown);
} else {
nowc++;
} // insert new Node into doubly linked-list
Node *nown = new Node();
nown->val = value;
nown->key = key;
um[key] = nown;
//insert Node
Node *prevn = tail->prev;
Node *nextn = tail;
prevn->next = nown;
nextn->prev = nown;
nown->prev = prevn;
nown->next = nextn;
} else {
Node *nown = um[key];
Node *prevn = nown->prev;
Node *nextn = nown->next;
// update value
nown->val = value;
// delete Node
prevn->next = nextn;
nextn->prev = prevn;
// insert Node
prevn = tail->prev;
nextn = tail;
prevn->next = nown;
nextn->prev = nown;
nown->prev = prevn;
nown->next = nextn;
}
}
};
