[Swift]LeetCode146.LRU缓存机制|LRUCache

OStack程序员社区-中国程序员成长平台 › 门户 › 编程› 移动开发›Swift 教程

原作者: [db:作者] 来自: [db:来源] 收藏邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号：山青咏芝（shanqingyongzhi）
➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）
➤GitHub地址：https://github.com/strengthen/LeetCode
➤原文地址：
➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。
➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎，请直接点击！！！

进入博主App Store主页，下载使用各个作品！！！

注：博主将坚持每月上线一个新app！！！

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example:

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制。它应该支持以下操作：获取数据 get 和写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

496ms

 1 class LRUCache {
 2 
 3     class RecencyNode {
 4         let key: Int
 5         var value: Int
 6         var next: RecencyNode?
 7         var prev: RecencyNode?
 8 
 9         init(key: Int, value: Int) {
10             self.key = key
11             self.value = value
12         }
13     }
14 
15     var head: RecencyNode?
16     var tail: RecencyNode?
17 
18     var buckets: [Int: RecencyNode]
19 
20     let capacity: Int
21     init(_ capacity: Int) {
22         buckets = [Int: RecencyNode]()
23         buckets.reserveCapacity(capacity)
24         self.capacity = capacity
25     }
26     
27     func get(_ key: Int) -> Int {
28       if let existing = buckets[key] {
29           upgradeRecency(existing)
30           return existing.value
31       }
32       return -1
33     }
34     
35     func put(_ key: Int, _ value: Int) {
36         let node: RecencyNode
37         if let existingNode = buckets[key] {
38             // value exists for this key, just modify it
39             existingNode.value = value
40             node = existingNode
41         } else {
42             // new insert, should check for possible eviction
43             if buckets.count == self.capacity {
44                 evict()
45             }
46             node = RecencyNode(key: key, value: value)
47         }
48 
49         upgradeRecency(node) 
50         buckets[key] = node
51     }
52 
53     private func evict() {
54         guard let oldHead = head else { return }
55         guard buckets.count >= capacity else { return }
56 
57         self.head = oldHead.next
58         if self.head == nil {
59             tail = self.head
60         }
61         
62         buckets[oldHead.key] = nil
63         oldHead.next = nil
64         oldHead.prev = nil
65         
66     }
67 
68     private func upgradeRecency(_ node: RecencyNode) {
69          
70          if let tail = tail {
71                if tail === node { return }
72                if let head = head, head === node {
73                    self.head = head.next
74                }
75             
76                node.prev?.next = node.next
77                node.next?.prev = node.prev
78                node.prev = tail
79                node.next = nil
80                tail.next = node
81                self.tail = tail.next
82               
83           } else {
84               // empty list
85               tail = node
86               head = tail
87           }
88     }
89 }

508ms

 1 class DLinkedNode {
 2     let key: Int
 3     var value: Int
 4     var pre: DLinkedNode?
 5     var next: DLinkedNode?
 6     
 7     init(key: Int, value: Int) {
 8         self.key = key
 9         self.value = value
10     }
11 }
12 
13 class LRUCache {
14     private let dummyHead: DLinkedNode
15     private var cache: [Int: DLinkedNode] = [:]
16     private var trail: DLinkedNode
17     
18     private let capacity: Int
19     init(_ capacity: Int) {
20         self.capacity = capacity
21         self.dummyHead = DLinkedNode(key: 0, value: 0)
22         self.trail = self.dummyHead
23     }
24     
25     func get(_ key: Int) -> Int {
26         if cache[key] == nil {
27             return -1
28         } else {
29             let node = cache[key]!
30             hitNode(node)
31             return node.value
32         }
33     }
34     
35     func hitNode(_ node: DLinkedNode) {
36         if node === trail {
37             return
38         }
39         node.pre?.next = node.next
40         node.next?.pre = node.pre
41         
42         trail.next = node
43         node.pre = trail
44         node.next = nil
45         
46         trail = trail.next!
47     }
48     
49     func put(_ key: Int, _ value: Int) {
50         if cache[key] != nil {
51             let node = cache[key]!
52             hitNode(node)
53             node.value = value
54             return
55         }
56         
57         if cache.count < capacity {
58             let newNode = DLinkedNode(key: key, value: value)
59             
60             trail.next = newNode
61             newNode.pre = trail
62             
63             trail = trail.next!
64             cache[key] = newNode
65         } else {
66             let removeNode = dummyHead.next!
67             
68             dummyHead.next = removeNode.next
69             removeNode.next?.pre = dummyHead
70             
71             cache[removeNode.key] = nil
72             let newNode = DLinkedNode(key: key, value: value)
73             
74             trail.next = newNode
75             newNode.pre = trail
76             
77             trail = trail.next!
78             cache[key] = newNode
79         }
80     }
81 }
82 
83 /**
84  * Your LRUCache object will be instantiated and called as such:
85  * let obj = LRUCache(capacity)
86  * let ret_1: Int = obj.get(key)
87  * obj.put(key, value)
88  */
89

512ms

 1 class NodeList {
 2     var key: Int
 3     var value: Int
 4     var next: NodeList?
 5     var prev: NodeList?
 6 
 7     init(_ key: Int, _ value: Int) {
 8         self.key = key
 9         self.value = value
10     }
11 }
12 
13 class LRUCache {
14     private(set) var capacity: Int
15 
16     private let head: NodeList 
17     private let tail: NodeList
18 
19     private var cache = [Int: NodeList]()
20 
21     init(_ capacity: Int) {
22         self.capacity = capacity
23         head = NodeList(-1, -1)
24         tail = NodeList(-1, -1)
25         head.next = tail
26         tail.prev = head
27     }
28 
29     func add(_ node: NodeList) {
30         let headNext = head.next
31         head.next = node
32         headNext?.prev = node
33         node.prev = head
34         node.next = headNext
35     }
36 
37     func remove(_ node: NodeList) {
38         let nextNode = node.next
39         let prevNode = node.prev
40         nextNode?.prev = prevNode
41         prevNode?.next = nextNode
42     }
43 
44     func reset(_ node: NodeList) {
45         remove(node)
46         add(node)
47     }
48 
49     func get(_ key: Int) -> Int {
50         guard let node = cache[key] else { return -1 }
51         reset(node)
52         return node.value
53     }
54 
55 
56     func put(_ key: Int, _ value: Int) {
57         if let existingNode = cache[key] {
58             remove(existingNode)
59             cache.removeValue(forKey: key)
60         }
61 
62         let newNode = NodeList(key, value)
63         add(newNode)
64         cache[key] = newNode
65 
66         guard 
67             cache.count > capacity,
68             let oldNode = tail.prev
69         else { return }
70 
71         remove(oldNode)
72         cache.removeValue(forKey: oldNode.key)
73     }
74 }
75 
76 /**
77  * Your LRUCache object will be instantiated and called as such:
78  * let obj = LRUCache(capacity)
79  * let ret_1: Int = obj.get(key)
80  * obj.put(key, value)
81  */

560ms

 1 class LRUCache {
 2     private let capacity: Int
 3     private var size = 0
 4     private var cache = [Int: DListNode]()
 5     private var head = DListNode(-1, -1)
 6     private var tail = DListNode(-1, -1)
 7 
 8     init(_ capacity: Int) {
 9         self.capacity = capacity
10         head.next = tail
11         tail.prev = head
12     }
13     
14     func get(_ key: Int) -> Int {
15         if let node = cache[key] {
16             remove(node)
17             add(node)
18             return node.value
19         }
20         return -1
21     }
22     
23     func put(_ key: Int, _ value: Int) {
24         if let node = cache[key] {
25             node.value = value
26             remove(node)
27             add(node)
28         } else {
29             let node = DListNode(key, value)
30             cache[key] = node
31             if size == capacity {
32                 // print(tail.prev!.key)
33                 cache[tail.prev!.key] = nil
34                 remove(tail.prev!)
35             } else {
36                 size += 1
37             }
38             add(node)
39         }
40     }
41     
42     private func add(_ node: DListNode) {
43         node.prev = head
44         node.next = head.next
45         head.next?.prev = node
46         head.next = node
47     }
48     
49     private func remove(_ node: DListNode) {
50         let prev = node.prev
51         let next = node.next
52         prev?.next = next
53         next?.prev = prev
54     }
55 }
56 
57 private class DListNode {
58     public var key: Int
59     public var value: Int
60     public var prev: DListNode?
61     public var next: DListNode?
62     
63     public init(_ key: Int, _ value: Int) {
64         self.key = key
65         self.value = value
66     }
67 }
68 
69 /**
70  * Your LRUCache object will be instantiated and called as such:
71  * let obj = LRUCache(capacity)
72  * let ret_1: Int = obj.get(key)
73  * obj.put(key, value)
74  */
75