/ * *
The title
Using your knowledge of data structures, design and implement an LRU (least recently used) caching mechanism. Implement the LRUCache class:
Capacity Initializes the LRU cache int GET (int key) Returns the value of the key if the key exists in the cache; otherwise -1 is returned. Void put(int key, int value) If the keyword already exists, change its data value. If the keyword does not exist, the set of keyword – values is inserted. When the cache reaches its maximum capacity, it should delete the oldest unused data values before writing new data to make room for new data values. Advanced: Can you do both in O(1) time?
Example:
Input [” LRUCache “, “put”, “put”, “get”, “put”, “get”, “put”, “get”, “get”, “get”] [[2], [1, 1], [2, 2], [1], [3, 3], [2]. (4, 4], [1], [3], [4]] output [null, null, null, 1, null, 1, null, 1, 3, 4]
LRUCache LRUCache = new LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} lRUCache. Get (1); // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} lRUCache. Get (2); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} lRUCache. Get (1); // return -1 (not found) lRUCache. Get (3); // return 3 lRUCache. Get (4); / / return 4
Tip:
1 <= Capacity <= 3000 0 <= key <= 3000 0 <= value <= 104 Invoke get and PUT a maximum of 3 * 104 times
Source: LeetCode link: leetcode-cn.com/problems/lr… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
The test code
let lRUCache = LRUCache(2); lRUCache.put(1, 1); // Cache is {1=1} lRUCache. Put (2, 2); {1=1, 2=2} print(lRUCache. // Return 1 lRUCache. Put (3, 3); {1=1, 3=3} print(lRUCache. Get (2)); // return -1 (not found) lRUCache. Put (4, 4); {4=4, 3=3} print(lRUCache. Get (1)); Print (lRUCache. Get (3)); Print (lRUCache. Get (4)); / / return 4
notes
So this is a very simple problem to do with an array, but it’s not very efficient to do with a bidirectional list, but it’s a little bit more complicated
The logic is the same: a dictionary stores key values and is used to determine numbers
We use a data structure to store data in order of activity and both get and set increase activity and when we get out of the way, we remove the least active data
The code address
Github.com/zmfflying/Z… * /
The problem solving code
Import Foundation class LRUCache {class Node {var key: Int? var value: Int? var prev: Node? var next: Node? } var maxCount: Int = 0 var dic: [Int: Node] = [Int: Node]() Node = Node.init() var foot: Node = Node.init() init(_ capacity: Int) { maxCount = capacity head.next = foot foot.prev = head } func get(_ key: Int) -> Int {let node = dic[key] {moveNodeToHead(node: node) return node.value! } return -1 } func put(_ key: Int, _ value: Int) {if let node = dic[key] {node.value = value //put moveNodeToHead(node: Node)} else {let node = node.init () node.key = key node.value = value // put the node corresponding to the key first node.next = head.next node.prev = head head.next? Dic [key] = node if dic. Count > maxCount {// Remove the last node dic.removeValue(forKey: foot.prev! .key!) let temp = foot.prev? .prev temp? .next = foot foot.prev = temp } } } func moveNodeToHead(node: Node) { if head.next! .key == node.key { return } node.prev? .next = node.next node.next? .prev = node.prev node.next = head.next node.prev = head head.next? .prev = node head. Next = node}} //class LRUCache {// var maxCount: Int = 0 // // var dic: [Int: Int] = [Int: Int]() // var arr: [Int] = [Int]() // // init(_ capacity: Int) { // maxCount = capacity // } // // func get(_ key: Int) -> Int { // if let value = dic[key] { // if let index = arr.firstIndex(of: key) { // arr.remove(at: index) // } // arr.append(key) // return value // } // return -1 // } // // func put(_ key: Int, _ value: Int) { // if let index = arr.firstIndex(of: key) { // arr.remove(at: index) // } // arr.append(key) // if dic[key] == nil && dic.count == maxCount { // dic.removeValue(forKey: arr.removeFirst()) // } // dic[key] = value // } //}Copy the code