LeetCode - #146 LRU 快取（Top 100）_Swift社群

攜手創作，共同成長！這是我參與「掘金日新計劃 · 8 月更文挑戰」的第11天，點選檢視活動詳情

前言

本題為 LeetCode 前 100 高頻題

我們社群陸續會將顧毅（Netflix 增長黑客，《iOS 面試之道》作者，ACE 職業健身教練。）的 Swift 演算法題題解整理為文字版以方便大家學習與閱讀。

LeetCode 演算法到目前我們已經更新到 145 期，我們會保持更新時間和進度（週一、週三、週五早上 9:00 釋出），每期的內容不多，我們希望大家可以在上班路上閱讀，長久積累會有很大提升。

不積跬步，無以至千里；不積小流，無以成江海，Swift社群伴你前行。如果大家有建議和意見歡迎在文末留言，我們會盡力滿足大家的需求。

難度水平：中等

1. 描述

請你設計並實現一個滿足 LRU (最近最少使用) 快取 約束的資料結構。

實現 LRUCache 類：

LRUCache(int capacity) 以 正整數 作為容量 capacity 初始化 LRU 快取
int get(int key) 如果關鍵字 key 存在於快取中，則返回關鍵字的值，否則返回 -1 。
void put(int key, int value) 如果關鍵字 key 已經存在，則變更其資料值 value ；如果不存在，則向快取中插入該組 key-value 。如果插入操作導致關鍵字數量超過 capacity ，則應該逐出最久未使用的關鍵字。

函式 get 和 put 必須以 O(1) 的平均時間複雜度執行。

2. 示例

示例 1

``` 輸入 ["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"] [[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]] 輸出 [null, null, null, 1, null, -1, null, -1, 3, 4]

解釋 LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // 快取是 {1=1} lRUCache.put(2, 2); // 快取是 {1=1, 2=2} lRUCache.get(1); // 返回 1 lRUCache.put(3, 3); // 該操作會使得關鍵字 2 作廢，快取是 {1=1, 3=3} lRUCache.get(2); // 返回 -1 (未找到) lRUCache.put(4, 4); // 該操作會使得關鍵字 1 作廢，快取是 {4=4, 3=3} lRUCache.get(1); // 返回 -1 (未找到) lRUCache.get(3); // 返回 3 lRUCache.get(4); // 返回 4 ```

約束條件：

1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 10^5
最多呼叫 2 * 10^5 次 get 和 put

3. 答案

```swift class LRUCache {

private let capacity: Int
private var count = 0

private let head = LRUCacheNode(0, 0)
private let tail = LRUCacheNode(0, 0)

private var dict = [Int: LRUCacheNode]()

init(_ capacity: Int) {
    self.capacity = capacity

    head.next = tail
    tail.pre = head
}

func get(_ key: Int) -> Int {
    if let node = dict[key] {
        remove(key)
        insert(node)
        return node.val
    }
    return -1
}

func put(_ key: Int, _ value: Int) {
    if let node = dict[key] {
        node.val = value
        remove(key)
        insert(node)
        return
    }

    let node = LRUCacheNode(key, value)
    dict[key] = node
    if count == capacity, let tailKey = tail.pre?.key {
        remove(tailKey)
    }
    insert(node)
}

private func insert(_ node: LRUCacheNode) {
    dict[node.key] = node

    node.next = head.next
    head.next?.pre = node
    node.pre = head
    head.next = node

    count += 1
}

private func remove(_ key: Int) {
    guard count > 0, let node = dict[key] else {
        return
    }
    dict[key] = nil

    node.pre?.next = node.next
    node.next?.pre = node.pre
    node.pre = nil
    node.next = nil

    count -= 1
}

}

fileprivate class LRUCacheNode {

let key: Int
var val: Int

var pre: LRUCacheNode?
var next: LRUCacheNode?

init(_ key: Int, _ val: Int) {
    self.key = key
    self.val = val
}

} ```

主要思想：使用連結串列和雜湊對映來構建快取。
時間複雜度： O(1)
空間複雜度： O(k)

該演算法題解的倉庫：LeetCode-Swift

點選前往 LeetCode 練習

關於我們

我們是由 Swift 愛好者共同維護，我們會分享以 Swift 實戰、SwiftUI、Swift 基礎為核心的技術內容，也整理收集優秀的學習資料。

後續還會翻譯大量資料到我們公眾號，有感興趣的朋友，可以加入我們。