剑指 Offer II 031. 最近最少使用缓存

重复题

public class LRUNode {
   public var key : Int
   public var val : Int
   public var next : LRUNode?
   public var prev : LRUNode?
   public init(){
     self.key = 0
     self.val = 0
     self.next = nil
     self.prev = nil
   }
   public init(_ key:Int,_ val:Int) {
     self.key = key
     self.val = val
     self.next = nil
     self.prev = nil
   }
}


class LRUCache {
    var map = Dictionary<Int,LRUNode>()
    var maxLen = 0
    var len = 0
    var first = LRUNode()
    var last = LRUNode()

    init(_ capacity: Int) {
        maxLen = capacity
        //把首尾的虚拟节点连起来
        first.next = last
        last.prev = first
    }
    
    func get(_ key: Int) -> Int {
        //如果存在的话
        if let tempNode = map[key] {
            //先删除原来的节点
            removeNode(tempNode)
            //把节点放置到前边
            afterFirstNode(tempNode)
            return tempNode.val
        }
        return -1
    }
    
    func put(_ key: Int, _ value: Int) {
       //如果存在节点的话
       if let tempNode = map[key]{
           tempNode.val = value
           removeNode(tempNode)
           afterFirstNode(tempNode)
       }else{
           if maxLen == len {
               //先删除最后的节点
               let lastNode = last.prev!
               removeNode(lastNode)
                map.removeValue(forKey: lastNode.key)
               //创建新的节点
               let tempNode = LRUNode(key,value)
               map[key] = tempNode
               afterFirstNode(tempNode)
           }else{
              //直接创建新的节点
              let tempNode = LRUNode(key,value)
              map[key] = tempNode
              afterFirstNode(tempNode)
              len += 1
           }


       }
   



    }

    //移除节点
    func removeNode(_ tempNode:LRUNode){
        //当前节点上一个节点的next指向当前节点的next
        tempNode.prev?.next = tempNode.next
        //当前节点的next的prev指向当前节点的上一个节点 
        tempNode.next?.prev = tempNode.prev
    }
    //把节点放置到虚拟头节点后边
    func afterFirstNode(_ tempNode:LRUNode){
        
        let oldNode = first.next
        first.next = tempNode
        tempNode.prev = first
        tempNode.next = oldNode
        oldNode?.prev = tempNode
    }



}