[Swift]LeetCode146. LRU缓存机制 | LRU Cache_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

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 1cache.put(3,3);    // evicts key 2cache.get(2);       // returns -1 (not found)cache.put(4,4);    // evicts key 1cache.get(1);       // returns -1 (not found)cache.get(3);       // returns 3cache.get(4);       // returns 4

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

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

进阶:

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

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );cache.put(1,2);cache.get(1);       // 返回  1cache.put(3,3);    // 该 *** 作会使得密钥 2 作废cache.get(2);       // 返回 -1 (未找到)cache.put(4,4);    // 该 *** 作会使得密钥 1 作废cache.get(1);       // 返回 -1 (未找到)cache.get(3);       // 返回  3cache.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 = key11             self.value = value12         }13     }14 15     var head: RecencyNode?16     var tail: RecencyNode?17 18     var buckets: [Int: RecencyNode]19 20     let capacity: Int21     init(_ capacity: Int) {22         buckets = [Int: RecencyNode]()23         buckets.reserveCapacity(capacity)24         self.capacity = capacity25     }26     27     func get(_ key: Int) -> Int {28       if let existing = buckets[key] {29           upgradeRecency(existing)30           return existing.value31       }32       return -133     }34     35     func put(_ key: Int,_ value: Int) {36         let node: RecencyNode37         if let existingNode = buckets[key] {38             // value exists for this key,just modify it39             existingNode.value = value40             node = existingNode41         } else {42             // new insert,should check for possible eviction43             if buckets.count == self.capacity {44                 evict()45             }46             node = RecencyNode(key: key,value: value)47         }48 49         upgradeRecency(node) 50         buckets[key] = node51     }52 53     private func evict() {54         guard let oldhead = head else { return }55         guard buckets.count >= capacity else { return }56 57         self.head = oldhead.next58         if self.head == nil {59             tail = self.head60         }61         62         buckets[oldhead.key] = nil63         oldhead.next = nil64         oldhead.prev = nil65         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.next74                }75             76                node.prev?.next = node.next77                node.next?.prev = node.prev78                node.prev = tail79                node.next = nil80                tail.next = node81                self.tail = tail.next82               83           } else {84               // empty List85               tail = node86               head = tail87           }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 = value10     }11 }12 13 class LRUCache {14     private let dummyhead: Dlinkednode15     private var cache: [Int: Dlinkednode] = [:]16     private var trail: Dlinkednode17     18     private let capacity: Int19     init(_ capacity: Int) {20         self.capacity = capacity21         self.dummyhead = Dlinkednode(key: 0,value: 0)22         self.trail = self.dummyhead23     }24     25     func get(_ key: Int) -> Int {26         if cache[key] == nil {27             return -128         } else {29             let node = cache[key]!30             hitNode(node)31             return node.value32         }33     }34     35     func hitNode(_ node: Dlinkednode) {36         if node === trail {37             return38         }39         node.pre?.next = node.next40         node.next?.pre = node.pre41         42         trail.next = node43         node.pre = trail44         node.next = nil45         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 = value54             return55         }56         57         if cache.count < capacity {58             let newNode = Dlinkednode(key: key,value: value)59             60             trail.next = newNode61             newNode.pre = trail62             63             trail = trail.next!64             cache[key] = newNode65         } else {66             let removeNode = dummyhead.next!67             68             dummyhead.next = removeNode.next69             removeNode.next?.pre = dummyhead70             71             cache[removeNode.key] = nil72             let newNode = Dlinkednode(key: key,value: value)73             74             trail.next = newNode75             newNode.pre = trail76             77             trail = trail.next!78             cache[key] = newNode79         }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 = value10     }11 }12 13 class LRUCache {14     private(set) var capacity: Int15 16     private let head: NodeList 17     private let tail: NodeList18 19     private var cache = [Int: NodeList]()20 21     init(_ capacity: Int) {22         self.capacity = capacity23         head = NodeList(-1,-1)24         tail = NodeList(-1,-1)25         head.next = tail26         tail.prev = head27     }28 29     func add(_ node: NodeList) {30         let headNext = head.next31         head.next = node32         headNext?.prev = node33         node.prev = head34         node.next = headNext35     }36 37     func remove(_ node: NodeList) {38         let nextNode = node.next39         let prevNode = node.prev40         nextNode?.prev = prevNode41         prevNode?.next = nextNode42     }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.value53     }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] = newNode65 66         guard 67             cache.count > capacity,68             let oldNode = tail.prev69         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 = capacity10         head.next = tail11         tail.prev = head12     }13     14     func get(_ key: Int) -> Int {15         if let node = cache[key] {16             remove(node)17             add(node)18             return node.value19         }20         return -121     }22     23     func put(_ key: Int,_ value: Int) {24         if let node = cache[key] {25             node.value = value26             remove(node)27             add(node)28         } else {29             let node = DListNode(key,value)30             cache[key] = node31             if size == capacity {32                 // print(tail.prev!.key)33                 cache[tail.prev!.key] = nil34                 remove(tail.prev!)35             } else {36                 size += 137             }38             add(node)39         }40     }41     42     private func add(_ node: DListNode) {43         node.prev = head44         node.next = head.next45         head.next?.prev = node46         head.next = node47     }48     49     private func remove(_ node: DListNode) {50         let prev = node.prev51         let next = node.next52         prev?.next = next53         next?.prev = prev54     }55 }56 57 private class DListNode {58     public var key: Int59     public var value: Int60     public var prev: DListNode?61     public var next: DListNode?62     63     public init(_ key: Int,_ value: Int) {64         self.key = key65         self.value = value66     }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