客服电话
APP下载
迪恩网络APP
随时随地掌握行业动态
官方微信
扫描二维码
关注迪恩网络微信公众号
|
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★ Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations:
Follow up: Example: LFUCache cache = new LFUCache( 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.get(3); // returns 3. cache.put(4, 4); // evicts key 1. cache.get(1); // returns -1 (not found) cache.get(3); // returns 3 cache.get(4); // returns 4 设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：
进阶： 示例： LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ ); cache.put(1, 1); cache.put(2, 2); cache.get(1); // 返回 1 cache.put(3, 3); // 去除 key 2 cache.get(2); // 返回 -1 (未找到key 2) cache.get(3); // 返回 3 cache.put(4, 4); // 去除 key 1 cache.get(1); // 返回 -1 (未找到 key 1) cache.get(3); // 返回 3 cache.get(4); // 返回 4 Runtime: 516 ms
Memory Usage: 21.3 MB
1 import Foundation 2 class LFUCache { 3 //最大容量 4 var capacity:Int 5 //当前容量 6 var size:Int 7 // key 对应的node node是在小链表上面的 8 var kNMap:[Int:Node] 9 //Node对应的NodeList的头是哪个 就是任何一个小结点都能查到在大链表的哪个小链表上 10 //一个链表对应的大链表的结点是哪个 11 var heads:[Node:NodeList] 12 //整个大链表的头部 动态的头部 不一定就是1作为头 13 var headList:NodeList? 14 15 init(_ capacity: Int) { 16 self.capacity = capacity 17 self.size = 0 18 kNMap = [Int:Node]() 19 heads = [Node:NodeList]() 20 headList = nil 21 } 22 23 func get(_ key: Int) -> Int { 24 //特判一下 25 if capacity == 0 {return -1} 26 if kNMap[key] == nil {return -1} 27 //获取结点所在的原来的链表 28 if let node:Node = kNMap[key] 29 { 30 node.times += 1 31 //找到这个结点属于的小链表 32 if let curNodeList:NodeList = heads[node] 33 { 34 move(node, curNodeList) 35 } 36 //返回对应的node的值 37 return node.val 38 } 39 return -1 40 } 41 42 func put(_ key: Int, _ val: Int) { 43 //注意特判 44 if capacity == 0 {return} 45 //如果已经存在 就要更新值 46 if kNMap[key] != nil 47 { 48 let node:Node = kNMap[key]! 49 node.val = val 50 node.times += 1 51 //找到属于哪一个大链表 52 53 if let curNodeList = heads[node] 54 { 55 /** 56 * move方法 57 * 就是在一个大链表中，和自己的上下级解耦，然后放到下一个词频链表中 58 * 比如说现在是5 times链上的，则从5times链中拿出来，如果6存在,放到6times链的头部(头插法) 59 * 如果6不存在，建出6times的链表 60 */ 61 move(node, curNodeList) 62 } 63 } 64 //kNMap中不存在,是新插入的 没包含 65 else 66 { 67 //要先判断容量够不够,已经满了 要删掉一个结点 68 if size == capacity 69 { 70 //要删掉的就是作为大链表的 头部的尾结点 (次数最少的 用了最久的) 71 if let deNode = headList?.tail 72 { 73 headList?.deleteNode(deNode) 74 /** 75 * 如果我删掉了 这个deNode 有可能我整个大链表的headList都没有东西了，整个大Node要删掉，要更新大headList 76 * 又因为加入了新节点，所以又要更新headList 77 * 先删再加 78 */ 79 if headList != nil 80 { 81 modifyHeadList(headList!) 82 } 83 //不要忘记在kNMap中删掉 84 kNMap[deNode.key] = nil 85 heads[deNode] = nil 86 size -= 1 87 } 88 } 89 //新建 次数为1 90 let node = Node(key, val, 1) 91 92 //整个大链表都不存在 93 if headList == nil 94 { 95 //建出大链表的头部 96 headList = NodeList(node) 97 } 98 else 99 { 100 // 已经有了大链表的头部 101 /** 102 * 如果有 次数为1的头 就直接添加到大头的头部 103 * 如果没有次数为1大头 就建一个大头 然后添加到大头的尾部 104 */ 105 //大链表的头的头 的次数是 1 也就是说 有为times的小链表 106 if headList?.head?.times == 1 107 { 108 //加到这里 109 headList?.addNodeFromHead(node) 110 } 111 else 112 { 113 //没有times为 1 的小链表 要自己建一个 114 //建出一个times为1的小链表 115 let newList = NodeList(node) 116 newList.next = headList 117 headList?.pre = newList 118 headList = newList 119 } 120 } 121 //最后再添加这条记录 122 kNMap[key] = node 123 heads[node] = headList 124 size += 1 125 } 126 } 127 128 /** 129 * 解耦原来的链表 并放入到一个新的链表中 130 * 131 * @param node 这个node 132 * @param oldNodeList node 的原来属于的list 133 */ 134 func move(_ node:Node?,_ oldNodeList:NodeList) 135 { 136 //老链表你自己先删掉 137 oldNodeList.deleteNode(node) 138 139 let preList = modifyHeadList(oldNodeList) ? oldNodeList.pre : oldNodeList 140 //要去的地方 141 let nextList = oldNodeList.next 142 143 //你的oldNodeList是大链表的最后一个 144 if nextList == nil 145 { 146 //建一个 147 let newList = NodeList(node) 148 if preList != nil 149 { 150 preList?.next = newList 151 } 152 newList.pre = preList 153 if headList == nil 154 { 155 headList = newList 156 } 157 if node != nil 158 { 159 heads[node!] = newList 160 } 161 } 162 //不是最后一个不是times最高的 163 else 164 { 165 //下一个存在 就直接挂在下一个的头部 166 if nextList?.head?.times == node?.times 167 { 168 nextList?.addNodeFromHead(node) 169 if node != nil 170 { 171 heads[node!] = nextList 172 } 173 } 174 //下一个不是 times + 1的 要自己新建一个node 然后左右两边重新连接好 175 else 176 { 177 let newList = NodeList(node) 178 179 if preList != nil 180 { 181 preList?.next = newList 182 } 183 newList.pre = preList 184 newList.next = nextList 185 nextList?.pre = newList 186 //这个是也要更换头 187 if headList == nextList 188 { 189 headList = newList 190 } 191 if node != nil 192 { 193 heads[node!] = newList 194 } 195 } 196 } 197 } 198 199 /** 200 * 这个方法的调用时机是 把一个node从一个nodelist中删掉 ，然后判断是不是要不这个nodelist给删掉 201 * 就是在delete之后， 要不要把整个小链表删掉 202 * 203 * @param nodeList 204 */ 205 func modifyHeadList(_ nodeList:NodeList) -> Bool 206 { 207 //为空了才要删掉整个大链表中的这个结点 208 if nodeList.isEmpty() 209 { 210 //要删的这个 是整个大链表的头部 211 if headList == nodeList 212 { 213 //新的头部是老头部的下一个 214 headList = headList?.next 215 if headList != nil 216 { 217 headList?.pre = nil 218 } 219 } 220 else 221 { 222 //要删的不是头 223 nodeList.pre?.next = nodeList.next 224 if nodeList.next != nil 225 { 226 nodeList.next?.pre = nodeList.pre 227 } 228 } 229 //也就是 这个是要整个都要删掉的 230 return true 231 } 232 //不空的话(也就是不只一个)就不要删 留着 233 return false 234 } 235 } 236 //小链表(挂在下面的) 237 class Node:Hashable 238 { 239 static func == (lhs: Node, rhs: Node) -> Bool { 240 return lhs.key == rhs.key 241 } 242 243 func hash(into hasher: inout Hasher) 244 { 245 hasher.combine(key) 246 } 247 //map中push的key 248 var key:Int 249 //map中对应的value 250 var val:Int 251 //操作的次数 252 var times:Int 253 //小链表的上一个 254 var up:Node? 255 //小链表的下一个 256 var down:Node? 257 258 init(_ key:Int,_ val:Int,_ times:Int) 259 { 260 self.key = key 261 self.val = val 262 self.times = times 263 } 264 } 265 266 //大的链表的结点结构 (每一个结点都是一个小链表) 267 class NodeList:Hashable 268 { 269 static func == (lhs: NodeList, rhs: NodeList) -> Bool { 270 return lhs.head == rhs.head && lhs.tail == rhs.tail 271 } 272 273 func hash(into hasher: inout Hasher) 274 { 275 hasher.combine(head) 276 hasher.combine(tail) 277 } 278 279 //大链表的头部指针 280 var head:Node? 281 //大链表的尾部指针 282 var tail:Node? 283 //大链表的前一个结点 284 var pre:NodeList? 285 //大链表的下一个结点 286 var next:NodeList? 287 288 init(_ node:Node?) 289 { 290 self.head = node 291 self.tail = node 292 } 293 294 //返回这个小链表(小链表本身又是大链表的结点)是不是空的 295 func isEmpty() -> Bool 296 { 297 return head == nil 298 } 299 300 //小链表的头部添加结点 301 func addNodeFromHead(_ newHead:Node?) 302 { 303 newHead?.down = head 304 head?.up = newHead 305 head = newHead 306 } 307 308 //删除小链表中的任意一个结点 309 func deleteNode(_ node:Node?) 310 { 311 //只有一个结点 312 if head == tail 313 { 314 head = nil 315 tail = nil 316 } 317 else 318 { 319 //删除的是小链表的头部 320 if head == node 321 { 322 //头结点变成下一个 323 head = head?.down 324 //头结点的上一个 置空 325 head?.up = nil 326 } 327 //删除的是小链表的尾部 328 else if tail == node 329 { 330 tail = tail?.up 331 tail?.down = nil 332 } 333 //删除的是链表的中间 334 else 335 { 336 node?.up?.down = node?.down 337 node?.down?.up = node?.up 338 } 339 } 340 //完全断链 341 node?.up = nil 342 node?.down = nil 343 } 344 } 345 /** 346 * Your LFUCache object will be instantiated and called as such: 347 * let obj = LFUCache(capacity) 348 * let ret_1: Int = obj.get(key) 349 * obj.put(key, value) 350 */ 424ms 1 class LFUCache { 2 3 var capacity: Int 4 var count: Int 5 var min: Int 6 var nodeMap: [Int: DLNode] 7 var countMap: [Int: DLList] 8 init(_ capacity: Int) { 9 self.capacity = capacity 10 self.count = 0 11 self.min = Int.max 12 self.nodeMap = [Int: DLNode]() 13 self.countMap = [Int: DLList]() 14 } 15 16 func get(_ key: Int) -> Int { 17 if let node = nodeMap[key] { 18 updateNode(node) 19 return node.value 20 } 21 else { 22 return -1 23 } 24 } 25 26 func put(_ key: Int, _ value: Int) { 27 guard capacity > 0 else { return } 28 if let node = nodeMap[key] { 29 node.value = value 30 updateNode(node) 31 } else { 32 if count == capacity { 33 if let minList = countMap[min] { 34 let removed = minList.removeLast() 35 nodeMap[removed.key] = nil 36 count -= 1 37 } 38 } 39 let node = DLNode(key, value) 40 nodeMap[key] = node 41 if let firstList = countMap[1] { 42 firstList.add(node) 43 } else { 44 countMap[1] = DLList(node) 45 } 46 count += 1 47 min = 1 48 } 49 } 50 private func updateNode(_ node: DLNode) { 51 if let list = countMap[node.count] { 52 list.remove(node) 53 if node.count == min, list.isEmpty { 54 min += 1 55 } 56 node.count += 1 57 if let newList = countMap[node.count] { 58 newList.add(node) 59 } else { 60 countMap[node.count] = DLList(node) 61 } 62 } 63 } 64 65 } 66 67 68 69 70 class DLNode { 71 var key: Int 72 var value: Int 73 var count: Int 74 var pre: DLNode? 75 var next: DLNode? 76 init(_ key: Int, _ value: Int) { 77 self.key = key 78 self.value = value 79 count = 1 80 } 81 } 全部评论
专题导读
上一篇：升级xcode8之后出现报错提示，提示swift版本问题发布时间：2022-07-13下一篇：关于Swift的闭包（closure）以及其在可选（Optional）类型中的应用 ...发布时间：2022-07-13热门推荐
热门话题
阅读排行榜
|
请发表评论