解題說明
LFU Cache
題目描述：
設計一個最不常使用（Least Frequently Used, LFU）快取，支援 get 和 put 操作，均為 O(1) 時間複雜度。當快取滿時，移除使用頻率最低的鍵；若頻率相同，移除最久未使用的鍵（LRU）。
解題思路： 使用三個資料結構協同工作：
- keyMap（
unordered_map<int, list<Node>::iterator>）：鍵 → 節點迭代器，O(1) 查找。 - freqMap（
unordered_map<int, list<Node>>）：頻率 → 該頻率的節點雙向鏈結串列（按使用時間排序，尾部最舊）。 - minFreq：追蹤當前最小頻率，用於 O(1) 找到要淘汰的節點。
get(key)：查找 keyMap，若存在則將節點從舊頻率鏈結移到新頻率鏈結的前端，更新 minFreq。put(key, value)：若已存在則更新值並提升頻率。若不存在且滿了，從 freqMap[minFreq] 移除最後一個節點。插入新節點到 freqMap[1] 前端，設 minFreq=1。
C++ 解法
複雜度分析
時間複雜度：get O(1)，put O(1) — 所有操作都是雜湊表查找 + 鏈結串列插入/刪除，均為常數時間。
空間複雜度：O(capacity) — 最多儲存 capacity 個鍵值對，加上頻率映射的額外空間。
虛擬碼
1. Maintain: keyMap (key -> node iterator), freqMap (freq -> node list), minFreq 2. get(key): a. If key not in keyMap, return -1 b. Get node value, call touch(node) to increment frequency c. Return value 3. put(key, value): a. If capacity <= 0, return b. If key exists: update value, call touch(node), return c. If at capacity: remove last node from freqMap[minFreq], remove from keyMap d. Insert new node into freqMap[1] front, set minFreq = 1 4. touch(node): a. Remove node from freqMap[oldFreq] b. If freqMap[oldFreq] empty and minFreq == oldFreq: minFreq++ c. Insert node into freqMap[oldFreq + 1] front
其他解法
OrderedDict per Frequency（Python 風格）：每個頻率維護一個 OrderedDict（有序字典），等效於 LinkedHashMap。操作邏輯相同，但在 C++ 中需要手動實作有序映射。適合 Python/Java，C++ 中用 list 更自然。
雙向鏈結串列 + 頻率桶節點：將頻率也做成鏈結串列節點，每個頻率節點下掛一個鍵的雙向鏈結串列。相鄰頻率的桶互相連接。刪除空桶時直接摘除節點。邏輯更緊湊但實作更複雜，面試中較難無誤寫出。
延伸思考
- LRU Cache（LeetCode 146）與 LFU Cache 的設計有何異同？為什麼 LFU 需要額外的頻率映射？
- 若允許 get 和 put 的時間複雜度為 O(log n)，可以用什麼更簡單的資料結構實現？
- 在實際系統中，LFU 有「頻率污染」問題（某個鍵曾被頻繁訪問但後來不再需要），如何設計帶衰減的 LFU 來解決？