LeetCode 146. LRU Cache [Swift 题解]

题目

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  

设计LRU是个很典型的面试题目, LRU有两个比较明显的限制条件:
1. capacity: 最多保存的cache 数目, 如果多于的话则最旧的那条可以删除
2. get 的时候相当于一次refresh,这个key则会重新在cache list最新的位置

附: 原题目链接

思路

结合上面的分析, 对于key/value pair这种我们应该是需要一个dictionary的。 另外很直观的想象,我们需要一个list来存储这个cache的新旧排序, 新进来的cache排在list 尾部, 超过capacity的话则把最旧的删除,这样的话选择double linked list就成为比较自然的选择。

class Node {  
    var key: Int
    var value: Int
    var next: Node?
    weak var prev: Node?

    init(key: Int, value: Int) {
        self.key = key
        self.value = value
    }
}

class LRUCache {  
    var capacity: Int
    var dict: [Int: Node]
    var head: Node
    var tail: Node

    init(_ capacity: Int) {
        self.capacity = capacity
        self.dict = [Int: Node]()
        self.head = Node(key: 0, value: 0)
        self.tail = Node(key: 0, value: 0)
        self.head.next = self.tail
        self.tail.prev = self.head
    }

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

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

        let newNode = Node(key: key, value: value)
        dict[key] = newNode
        add(node: newNode)

        if dict.count > capacity {
            let first = head.next!
            remove(node: first)
            dict.removeValue(forKey: first.key)
        }
    }

    private func add(node: Node) {
        let last = self.tail.prev!
        last.next = node
        node.prev = last
        node.next = tail
        tail.prev = node
    }

    private func remove(node: Node) {
        guard let prev = node.prev, let next = node.next else {
            return
        }

        prev.next = next
        next.prev = prev
    }
}

chenbo

编程爱好者

Singapore