146. LRU Cache

Medium

Description

設計一個 LRU (Least Recently Used) 快取機制。實作 LRUCache 類別：get(key) 回傳 key 對應的值（不存在則回傳 -1），put(key, value) 更新或插入鍵值對。當快取超過容量時，移除最久未使用的鍵值對。get 和 put 必須在 O(1) 時間內完成。

Example:

Input: [“LRUCache”,“put”,“put”,“get”,“put”,“get”,“put”,“get”,“get”,“get”], [[2],[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]] Output: [null,null,null,1,null,-1,null,-1,3,4]

Intuition#

核心思路：HashMap 提供 O(1) 查找，雙向鏈結串列提供 O(1) 的插入和刪除，兩者結合實現完整的 LRU。

HashMap: key -> Node，O(1) 查找
雙向鏈結串列：維護使用順序，最近使用的在頭部，最久未使用的在尾部
每次 get/put 時把節點移到頭部；容量滿時移除尾部節點

Approaches#

1: LinkedHashMap (Built-in)#

概念: Kotlin/Java 的 LinkedHashMap 已經實作了有序 HashMap，設定 accessOrder = true 即可
時間複雜度: O(1) - get 和 put
空間複雜度: O(capacity)

class LRUCache(private val capacity: Int) {
    private val map = object : LinkedHashMap<Int, Int>(capacity, 0.75f, true) {
        override fun removeEldestEntry(eldest: MutableMap.MutableEntry<Int, Int>?): Boolean {
            return size > capacity
        }
    }

    fun get(key: Int): Int {
        return map.getOrDefault(key, -1)
    }

    fun put(key: Int, value: Int) {
        map[key] = value
    }
}

⭐2: HashMap + Doubly Linked List#

概念: 手動實作雙向鏈結串列，搭配 HashMap 實現所有操作 O(1)
時間複雜度: O(1) - get 和 put
空間複雜度: O(capacity)

class LRUCache(private val capacity: Int) {

    private class Node(val key: Int, var value: Int) {
        var prev: Node? = null
        var next: Node? = null
    }

    private val map = HashMap<Int, Node>()
    private val head = Node(0, 0) // dummy head
    private val tail = Node(0, 0) // dummy tail

    init {
        head.next = tail
        tail.prev = head
    }

    fun get(key: Int): Int {
        val node = map[key] ?: return -1
        moveToHead(node)
        return node.value
    }

    fun put(key: Int, value: Int) {
        val existing = map[key]
        if (existing != null) {
            existing.value = value
            moveToHead(existing)
        } else {
            val node = Node(key, value)
            map[key] = node
            addToHead(node)
            if (map.size > capacity) {
                val removed = removeTail()
                map.remove(removed.key)
            }
        }
    }

    private fun addToHead(node: Node) {
        node.prev = head
        node.next = head.next
        head.next!!.prev = node
        head.next = node
    }

    private fun removeNode(node: Node) {
        node.prev!!.next = node.next
        node.next!!.prev = node.prev
    }

    private fun moveToHead(node: Node) {
        removeNode(node)
        addToHead(node)
    }

    private fun removeTail(): Node {
        val node = tail.prev!!
        removeNode(node)
        return node
    }
}

Node 必須儲存 key，因為 removeTail 時需要知道 key 才能從 HashMap 中移除。這是常見的面試陷阱。

🔑 Takeaways#

Pattern: HashMap + 雙向鏈結串列是實作各種 Cache 策略（LRU、LFU 等）的標配組合
關鍵技巧: Dummy head 和 dummy tail 大幅簡化邊界處理；Node 中儲存 key 方便反向查找 HashMap