[LeetCode] 146. LRU Cache

轉自LeetCode

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and set.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

<Solution>

這題是要去設計一個給 LRU cache 用的 data structure

所謂 LRU 就是當 cache 容量滿了，又有新資料進來，就把最久沒用到的資料從 cache 給拿掉

這邊要注意到的是，每次 get, set 的那筆資料，都要變成最近一個使用的資料

這邊設計的想法是

• 用 list 來存放資料，front 是剛使用到的資料，back 是最久沒用到的資料。用 list 來存放資料，也是因為移動資料位置比較方便。list 存放的資料是 pair，key 就是 key，value 就是 value

• 那每次去 list 找資料，這樣時間會耗太久，所以在用一個 unordered_map 來當作 hash map。key 就是 key，value 是該 key 存放在 list 裡面資料的 iterator，這樣之後可以透過 iterator 直接拿到資料，而且 hash map 的 access 是 O(1)，這樣就很快

• 每次 set 之後，都要檢查是否超過 capacity，超過就刪除 list 最後一個資料，記得要也從 hash map 裡面刪除相關資料

code 如下

C++

Java