携手创造，一起成长！这是我参加「日新计划 8 月更文应战」的第11天，点击查看活动概况。假如哪里写的不对，请咱们谈论批评。

期望往后的日子，能够每天坚持一个算法，最近发现一个有意思的事情，LeetCode中等难度的题，也不简单，暴力算法固然能处理问题，可是从时刻复杂度和空间复杂度上必定达不到要求。

LRU缓存机制

标题

请你设计并完成一个满意 LRU (最近最少使用) 缓存 约束的数据结构。

完成 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量capacity 初始化LRU 缓存

int get(int key) 假如关键字key存在于缓存中，则回来关键字的值，否则回来 -1

void put(int key, int value) 假如关键字key现已存在，则变更其数据值value；假如不存在，则向缓存中刺进该组key-value,假如刺进操作导致关键字数量超越capacity，则应该逐出最久未使用的关键字.

函数 get 和 put 有必要以 O(1) 的平均时刻复杂度运转

示例

输入
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1);    // 回来 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 报废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 回来 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 报废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 回来 -1 (未找到)
lRUCache.get(3);    // 回来 3
lRUCache.get(4);    // 回来 4

提示

提示：
1 <= capacity <= 3000
0 <= key <= 10000
0 <= value <= 105
最多调用 2 * 105 次 get 和 put

剖析

一般常用的方式便是Hash+双链表的方式，哈希能够使用Key-Value的原理直线O(1)的时刻复杂度，能够满意get 和 put的要求的条件。Value存储的是双链表node节点

为什么用双链表

咱们需要一个有序的存储空间来存储先后的循序，数组、栈都能够做到这个一点，可是操作比较费事，这个时分双链表是最好的挑选，无论刺进还是删去，都能够在O(1)处理（哈希的Value存储的是双链表node节点）

图解

剖析示例

1. Cache初始化的时分入参是2，这里咱们需要一个定义一个Hash来存储key-value，然后存储最大缓存数据2

2. put(1,1)也便是说key为1 ,value为1

   

3. put(2,2)也便是说key为2 ,value为2,由于链表上有数据,新的数据要保持在最顶部。相当于活跃度的排序

   

4. get(1)从Hash中获取链表的node地址，直接获取到node的值，这时分要注意了。要注意了，由于get(1)相当于对与1有了操作，这时分就需要中心排序，把当时位置的节点，删去，从头刺进到头节点上去

   

5. put(3, 3)也便是说key为3 ,value为3，这时分要注意，缓存长度是2，这时分就有必要删去掉最后一位不怎么使用的节点，把3刺进到头结点上去。

   

6. get(2)去Hash中现已找不到缓存了，由于空间有限，在上一步被删去了，所以得到的是-1

7. 后边就不一步步的解析了直接上图吧~~

8. 后边三个都是get(1)得到-1现已被删去了，get(3)得到3以及get(4)得到4在正在缓存中。

   

代码

class LRUCache {
    // 哈希
    var mapNode : [Int:MyNode]!
    // 最大数量
    var capacity = 0
    // 头节点
    var first:MyNode!
    // 尾节点
    var last:MyNode!
    // 初始化，存储最大缓存
    init(_ capacity: Int) {
      self.capacity = capacity
        mapNode = [Int:MyNode]()
      first = MyNode.init()
      last = MyNode.init()
      first.next = last
      last.prev = first
    }
    // 获取数据
    func get(_ key: Int) -> Int {
     // 假如map中不存在，或许node不存在直接回来-1
      guard let node = mapNode[key] else {
        return -1
      }
      // 删去节点从头刺进到开始，这里能够简单优化一下，假如现已是头节点，能够不用操作
      removeNode(node)
        addFirst(node)
      return node.val
    }
    // 刺进数据
    func put(_ key: Int, _ value: Int) {
      let node = mapNode[key]
      // 刺进数据也是对原有数据操作，需要放在头节点
      if node != nil {
        //! 更新 key
        node!.val = value
        removeNode(node!)
        addFirst(node!)
      } else {
         // 假如大于存储长度，需要筛选结尾的
        if mapNode.keys.count == capacity {
          let prevNode = mapNode.removeValue(forKey: last.prev!.key)!
          removeNode(prevNode)
        }
        let newNode = MyNode.init(key, value)
        mapNode[key] = newNode
        addFirst(newNode)
      }
    }
    // 双向链表，保持链表不要断开
    private func removeNode(_ node:MyNode) {
      // 下一个链表的上一个节点 指向当时节点的上一个
      node.next!.prev = node.prev
      // 上一个链表的下一个节点(原来指向自己) ，现在要指向自己的下一个节点
      node.prev!.next = node.next
    }
    //  双向链表 -> 刺进节点到头节点后边
    private func addFirst(_ node:MyNode) {
      node.next = first.next
      first.next!.prev = node
      first.next = node
      node.prev = first
    }
}
class MyNode {
  var key:Int = 0
  var val: Int = 0
  var prev: MyNode?
  var next: MyNode?
  init(_ key:Int = 0, _ value:Int = 0) {
    self.key = key
    self.val = value
  }
}