一、題目介紹
今天要練習的是LeetCode 146. LRU Cache

LRU是Least Recently Used的縮寫，意思是「最近最少使用」

題目要求我們設計一個具有固定容量的Cache，支援兩個操作

• get(key)：取得指定key的value
• put(key, value)：新增或更新key-value
  當Cache已經達到容量上限時，如果還要加入新的資料，就必須刪除最久沒有被使用的資料

例如Cache容量為2：
put(1, 1)
put(2, 2)
get(1)
put(3, 3)

此時Cache中原本有：
1 → 1
2 → 2
執行get(1)後，key 1變成最近使用

因此：
2 → 2 ← 最久沒有使用
1 → 1 ← 最近使用

當執行put(3, 3)就必須把2移除

最後：
1 → 1
3 → 3

所以get(2)會回傳：-1

二、為什麼需要HashMap + Linked List？
這題最有趣的地方，就是單獨使用HashMap或Linked List都不夠快

我們希望：

1. get(key)可以快速找到資料
2. 使用某個key後，可以快速把它移到「最近使用」的位置
3. Cache滿了之後，可以快速刪除「最久沒使用」的資料
   因此可以把兩種資料結構結合起來

HashMap
負責 key → Node
可以在O(1)平均時間找到指定key

Linked List
負責記錄使用順序

我們規定
頭部 = 最近使用
尾部 = 最久沒有使用

例如：

當get(1)：

三、Java實作

四、Python實作

五、Java與Python比較

六、時間與空間複雜度
get()
HashMap 查找：O(1)
Linked List 移除與加入：O(1)
因此Time Complexity: O(1)

put()
HashMap 操作：O(1)
Linked List 操作：O(1)
因此Time Complexity: O(1)

空間複雜度
Cache最多儲存capacity個資料：Space Complexity: O(capacity)

七、實作結果
Leetcode測試結果：Accepted

八、今日學習心得
Day 29 是這 30 天裡面相對需要理解資料結構的一題。

前面學過：

• Hash Table
• Linked List
• Heap
• Sliding Window
• Backtracking

到了今天，我開始嘗試把不同資料結構組合起來解決問題。

LRU Cache 讓我理解到，一個問題不一定只能使用一種資料結構。例如這題如果只使用 HashMap，雖然可以快速找到資料，卻很難快速知道「哪一筆資料最久沒有使用」；如果只使用 Linked List，又會讓搜尋特定 key 變得比較慢。

因此透過：
HashMap
↓
快速找到 Node

Linked List
↓
快速維護使用順序

兩者合作後，就可以讓 get() 和 put() 都維持在 O(1)。

我覺得這題也讓我更理解「資料結構的選擇」為什麼重要。以前看到 HashMap、Linked List 時，可能會把它們當成不同章節的知識，但實際解題時，它們其實可以像零件一樣組合在一起。