$LRU$ 是一個快取機制
快取的意思是：因記憶體有限，所以得在必要時拋棄不必要的資料
但是頻繁使用的東西若一直丟掉會造成一個狀況：持續進行不必要的動作導致時間常數增加非常多
因此我們需要將最近、最少使用的資料拋棄，簡單而言就是要將「最早存取」的資料拋棄
這裡的「存取」指以下幾種操作
1. 更新資料
2. 插入資料
3. 檢索資料
現在請寫一個程式來實作一個 $LRU\ Cache$ 吧！
！！！重要提醒！！！
本題複雜度應於 $O(N)$ 內解決
也就是說，每一個操作都必需是 $O(1)$ 才行
因為此題常數有點大
本題多個測資點，單筆測資
第一行有一個正整數 $N$
第二行是一個正整數 $P$ 代表 $LRU\ Cache$ 的容量
接下來有 $N$ 行：
每一行第一格是一個字串
若字串為 $insert$，後面會跟著兩個正整數，前者為鍵值 $key$，後者則為對應到的值 $value$
若字串為 $query$，後面會跟著一個正整數，代表鍵值 $key$，請輸出你檢索到的值 $value$
例外規則：
$key$ 不得重複，若有重複則視為更新 $value$
$query$ 找不到資料時，請輸出 $-1$，表示檢索無果
$N \leq 4 \times 10^6$
$P \leq 10^4$
$0 < key, \ value \leq INT\_MAX$
對於每一個 $query$，輸出一個整數
每一個數中間以空白分隔
9 2 insert 1 1 insert 2 2 query 1 insert 3 3 query 2 insert 4 4 query 1 query 3 query 4
1 -1 -1 3 4
範例測資說明：
現在有容量為 $2$ 的快取
1. 丟入 $1\ 1$，拋棄順序：$1$
2. 丟入 $2\ 2$，拋棄順序：$1\ 2$
3. 詢問 $1$，輸出 $1$，拋棄順序：$2\ 1$
4. 丟入 $3\ 3$，拋棄 $2$，拋棄順序：$1\ 3$
5. 詢問 $2$，找不到輸出 $-1$
6. 丟入 $4\ 4$，拋棄 $1$，拋棄順序：$3\ 4$
7. 詢問 $1$，找不到輸出 $-1$
8. 詢問 $3$，輸出 $3$，拋棄順序：$4\ 3$
9. 詢問 $4$，輸出 $4$，拋棄順序：$3\ 4$
STL 參考：STL containers
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||