Day 12：LRU Cache (LC #146) ➝ LinkedHashMap應用 - iT 邦幫忙::一起幫忙解決難題，拯救 IT 人的一天

2025 iThome 鐵人賽

DAY 12

0

自我挑戰組

Java × LeetCode-30天日記系列第 12 篇

Day 12：LRU Cache (LC #146) ➝ LinkedHashMap應用

17th鐵人賽

2025-09-26 09:52:42

47 瀏覽

分享至

題目理解
我的理解： 這題的核心是模擬一個固定大小的快取 (Cache)，當容量滿的時候，要把最久沒用過的元素刪掉。
方法

雙向鏈結串列 (Doubly Linked List)：用來維護 key 的使用順序。
head 後面：放最近使用過的節點。
tail 前面：放最久未使用的節點。
get(key)：
如果 key 存在 → 取出值，並把該節點移到最前面 (代表最近使用)。
如果 key 不存在 → 回傳 -1。
put(key, value)：
如果 key 已存在 → 先刪除舊節點，再插入新節點到最前面。
如果 key 不存在，但容量已滿 → 移除最後一個節點 (tail.prev)。
插入新節點到最前面，並更新 HashMap。

心得
這題一開始我覺得很複雜但後來了解其實是把HashMap（保證O(1)查找）與雙向鏈結串列（保證O(1)插入/刪除）的優點結合，我覺得學會這題是要知道如何正確組合資料結構。

Day 11：Implement Queue using Stacks (LC #232)

系列文

Java × LeetCode-30天日記共 12 篇

目錄

RSS系列文訂閱系列文

0 人訂閱

完整目錄

熱門推薦

{{ item.subject }}

{{ item.channelVendor }} | {{ item.webinarstarted }} |

{{ formatDate(item.duration) }}

直播中

尚未有邦友留言

立即登入留言

參賽組數

902 組

團體組數

37 組

累計文章數

12008 篇

完賽人數

106 人

15th鐵人賽 16th鐵人賽 13th鐵人賽 14th鐵人賽 12th鐵人賽 11th鐵人賽 17th鐵人賽鐵人賽 2019鐵人賽 javascript 2018鐵人賽 python 2017鐵人賽 windows php c# windows server linux css react

IT邦幫忙