破題

• 這題目要求我們實作一種叫做 LRU 的 cache 機制，它可以快速地存取和更新資料。
• 為了實作這種機制，我們需要用到兩種資料結構：一個是 hash table，一個是 doubly linked list。
• 在面試中，面試官通常會要求我們寫出 doubly linked list 的程式，而不是直接使用現成的資料結構。有些語言中有一些已經實作了 LRU cache 機制的資料結構，比如 Java 中的 LinkedHashMap ，但是這種做法不符合面試官的要求，所以我們只會在這裡介紹它背後的想法。

class LRUCache(private val capacity: Int) : LinkedHashMap<Int?, Int?>(capacity, 0.75f, true) {
    operator fun get(key: Int): Int {
        return super.getOrDefault(key, -1)!!
    }

    fun put(key: Int, value: Int) {
        super.put(key, value)
    }

    override fun removeEldestEntry(eldest: Map.Entry<Int?, Int?>): Boolean {
        return size > capacity
    }
}

• Hash table 可以讓我們在 的時間內找到一筆資料的位置，doubly linked list 可以讓我們在 的時間內插入或刪除一筆資料。
• Doubly linked list 用來按照使用頻率存儲資料，越靠近 linked list 頭部的資料表示越近期被使用過，越靠近 linked list 尾部的資料表示越久沒有被使用過。
• Hash table 用來記錄每筆資料在 doubly linked list 中的位置，這樣我們就可以快速地定位和移動資料。
• 當我們要新增一個筆的資料時，如果 doubly linked list 沒有超過容量限制，我們就直接把它新增到 doubly linked list 的 head，並在 hash table 中記錄它的位置。如果 doubly linked list 已經滿了，我們就先刪除 doubly linked list 的尾部節點，表示它是最久沒有被使用過的，然後再把新的資料新增到 doubly linked list 的 head，並更新 hash table 中的記錄。

跟一流的人才幹大事，享受成功進步的高級樂趣！
內推機會來啦！能與優秀的程式設計師共事，是特別痛快的事，因為厲害的工程師大神會刺激你想要迎頭趕上的上進心，尤其是一起討論解決方案時，他們會觸發你有更好的解決思維能力，彼此共同成長並且一起享受解謎與破關般的樂趣。 你一定聽得懂我在說甚麼感覺，趕快把握機會，動動手指投遞履歷吧！ 立即加入「面試讀書會」，和大家一起準備面試！

內推機會	加入讀書會 (邀請碼：8484)

MutableMap + Deque

解題思路

• 我們使用了兩個資料結構來實現這個機制：一個是 Deque，一個是 MutableMap。
  • Deque 可以讓我們在兩端插入或刪除資料，我們用它來按照使用頻率存儲資料的 key，越靠近 queue 尾部的 key 表示越近期被使用過，越靠近 queue 頭部的 key 表示越久沒有被使用過。
  • MutableMap 可以讓我們在 的時間內根據 key 找到對應的 value，我們用它來存儲資料的 key 和 value 的對應關係。
• 當我們要 get 一筆資料時，我們先判斷 MutableMap 中是否包含這個 key
  • 如果不包含，就回傳 -1 表示沒有找到；
  • 如果包含，就從 Deque 中刪除這個 key，然後再把它新增到 Deque 的尾部，表示它是最近被使用過的，最後回傳 MutableMap 中這個 key 對應的 value。
• 當我們要新增或更新一筆資料時，我們先判斷 MutableMap 中是否包含這個 key
  • 如果包含，就從 Deque 中刪除這個 key，然後再把它新增到 Deque 的尾部，並更新 MutableMap 中這個 key 對應的 value；
  • 如果不包含，就判斷 Deque 是否已經達到容量限制，如果達到了，就從 Deque 的頭部刪除一個 key，並從 MutableMap 中移除這個 key 和 value 的對應關係；然後再把新的 key 新增到 Deque 的尾部，並在 MutableMap 中新增新的 key 和 value 的對應關係。

程式

class LRUCache(private val capacity: Int) {
    val deque: Deque<Int> = ArrayDeque<Int>(capacity)
    val map = mutableMapOf<Int, Int>()
    fun get(key: Int): Int {
        if (map.contains(key)) {
            deque.remove(key)
            deque.offer(key)
        }
        return map[key] ?: -1
    }

    fun put(key: Int, value: Int) {
        if (map.contains(key)) {
            deque.remove(key)
        } else if (deque.size >= capacity) {
            val removeKey = deque.poll()
            map.remove(removeKey)
        }

        deque.offer(key)
        map[key] = value
    }

}

複雜度分析

• 時間複雜度:
  對於 get 和 put 操作都是 ，因為 MutableMap 可以在 的時間內找到或更新一個 key 和 value 的對應關係，而 Deque 可以在 的時間內在兩端插入或刪除一個 key。

• 空間複雜度:
  ，因為 MutableMap 和 Deque 最多存儲 個元素。

　更多 LeetCode 解答在此，一起來學習！

內推機會來啦！

跟一流的人才幹大事，享受成功進步的高級樂趣！

內推機會	加入讀書會 (邀請碼：8484)