一、简介

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，并有如下两个功能

1. set(key, value)：将记录(key, value)插入该结构

2. get(key)：返回key对应的value值

提示:

1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。

2.当缓存的大小超过k时，移除最不经常使用的记录。

3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value

若opt=1，接下来两个整数key, value，表示set(key, value)

若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1

对于每个opt=2，输出一个答案

4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为 O(1)O(1)

二、具体实现

思路：利用双向链表+hash表，双向链表保留位置信息，确定哪些元素最近最少使用，hash表便于实现元素的快速查找。每次新增和查找，都将元素从链表中移动到首位。

type LruCache struct {
   Size    int
   data    map[int]*CacheNode
   firstNode *CacheNode
   lastNode *CacheNode
}

type CacheNode struct {
   k    int
   v    int
   next *CacheNode
   pre  *CacheNode
}

func (l *LruCache) add(k, v int) {
   curNode, isOk := l.data[k]
   if !isOk {
      if len(l.data) >= l.Size {
         // 删除最后一个元素
         l.delLast()
      }

      // 插入当前节点
      curNode = &CacheNode{
         k:    k,
         v:    v,
      }

      if l.firstNode != nil {
         curNode.next = l.firstNode
         l.firstNode.pre = curNode

         l.firstNode = curNode
      } else {
         l.firstNode = curNode
         l.lastNode = curNode
      }

      l.data[k] = curNode

      return
   } else {
      // 需要修改当前节点的值
      curNode.v = v

      // 将 curNode调整到首位
      l.chg2First(curNode)
   }
}

func (l *LruCache) get(k int) int {
   curNode, isOk := l.data[k]

   if isOk {
      l.chg2First(curNode)
      return curNode.v
   }

   return -1
}

func (l *LruCache) chg2First(node *CacheNode) {
   // 如果已经是首位，直接返回
   if l.firstNode == node {
      return
   }

   // 如果在末尾
   if node == l.lastNode {
      // 将末尾改为 node前一个节点
      nodePre := node.pre
      nodePre.next = nil
      l.lastNode = nodePre

      //
      node.pre = nil
      node.next = l.firstNode

      l.firstNode.pre = node
      l.firstNode = node

      return
   }

   // 如果在中间节点
   parentNode := node.pre
   nextNode := node.next

   parentNode.next = nextNode
   nextNode.pre = parentNode

   node.next = l.firstNode
   node.pre = nil

   l.firstNode.pre = node
   l.firstNode = node
}

func (l *LruCache) delLast() {
   // 如果就剩一个元素
   if len(l.data) == 1 {
      l.firstNode = nil
      l.lastNode = nil
      delete(l.data, l.firstNode.k)
      return
   }

   delete(l.data, l.lastNode.k)

   preNode := l.lastNode.pre
   l.lastNode = preNode
   preNode.next = nil


}

func LRU(operators [][]int, k int) []int {
   cache := &LruCache{
      Size: k,
      data: make(map[int]*CacheNode),
   }

   rs := make([]int, 0)
   for _, item := range operators {
      if item[0] == 1 && len(item) >= 3 {
         // inset
         cache.add(item[1], item[2])
      } else if item[0] == 2 && len(item) >=2 {
         // get
         rs = append(rs, cache.get(item[1]))
      }
   }

   return rs
}

题目来源：牛客