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

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@H_197_37@ 

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。
 
获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key,value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。
 
进阶:
 
你是否可以在 O(1) 时间复杂度内完成这两种操作？
 
示例:
 
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1,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@H_197_37@ 

496ms@H_197_37@ 
 
 
 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 }@H_197_37@ 
 

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  @H_197_37@ 
 

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  */@H_197_37@ 
 

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  @H_197_37@