题解 | #设计LRU缓存结构#

public class Solution { /** * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可 * lru design * @param operators int整型二维数组 the ops * @param k int整型 the k * @return int整型一维数组 */ class LRUCache { class Node { var val: Int var key: Int var next: Node? var pre: Node? init() { val = 0; key = 0 } init(_ key: Int, _ val: Int) { self.val = val; self.key = key } }

    var map: [Int: Node] = [:]
    var dummyHead = Node()
    var dummyTail = Node()
    var capacity: Int
    init(_ capacity: Int) {
        self.capacity = capacity
        dummyHead.next = dummyTail
        dummyTail.pre = dummyHead
    }

    func add(_ node: Node) {
        
        let next = dummyHead.next
        node.next = next
        node.pre = dummyHead
        dummyHead.next = node
        next?.pre = node
        // debugPrinter()
    }

    func remove(_ node: Node) {
        // debugPrinter()
        let pre = node.pre
        let next = node.next
        pre?.next = next
        next?.pre = pre
    }

    func put(_ key: Int, _ value: Int) {
        if let node = map[key] {
            remove(node)

        } else if map.count == capacity {
            // capacity is not enough, delete tha last from linkedlist and map
            let key = dummyTail.pre?.key
            
            remove(map[key!]!)
            map[key!] = nil
            
        }
        let newNode = Node(key, value)
        map[key] = newNode
        add(newNode)
    }

    func get(_ key: Int) -> Int {
        if let node = map[key] {
            remove(node)
            add(node)
            return node.val
        } else {
            return -1
        }
    }

// func debugPrinter() {
//     var cur = dummyHead.next
//     while let node = cur {
//         print("\(node.key):\(node.val)", terminator: ", ")
//         cur = cur?.next
//     }
//     print("")
// }
}

func LRU ( _ operators: [[Int]],  _ k: Int) -> [Int] {
    // write code here
    var lruCache = LRUCache(k)
    var res: [Int] = []
    for i in 0..<operators.count {
        let op = operators[i]
        if op[0] == 1 {
           lruCache.put(op[1],op[2])
        } else if op[0] == 2{
           res.append(lruCache.get(op[1]))
            
        }
    }
    return res
    
}

}