LeetCode - #146 LRU 緩存(Top 100)

語言: CN / TW / HK

攜手創作,共同成長!這是我參與「掘金日新計劃 · 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 ,則應該 逐出 最久未使用的關鍵字。

函數 getput 必須以 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^5getput

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 基礎為核心的技術內容,也整理收集優秀的學習資料。

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