题目：

实现 LRUCache 类：

  • LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
  • int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。

  • void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「key-value」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。


    进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？

思路：

如果是O(n)的时间复杂度，那么可以把数据存在slice中，每次查询或者插入时，都遍历一遍，但是要在O(1)时间复杂度内实现，必然要使用哈希表，也就是要使用空间来换时间。
在具体实现上，哈希表用于存储值，双向链表用于记录最新使用过的和最久未使用的数据，方便进行增删改查。

关键部分：

在head和tail的地方使用哨兵节点，有边界条件，可以省去判断相邻节点是否存在的情况（举个例子？）
代码实现（哈希表+双向链表）：

  1. package main
  3. import (
  4.     "fmt"
  5. )
  7. type LRUCache struct {
  8.     capacity   int
  9.     size       int
  10.     cache      map[int]*DataLinkNode
  11.     head, tail *DataLinkNode
  12. }
  14. type DataLinkNode struct {
  15.     key, value int
  16.     next, prev *DataLinkNode
  17. }
  19. //初始化缓存
  20. func Constructor(capacity int) *LRUCache {
  21.     head := InitialNode(0, 0)
  22.     tail := InitialNode(0, 0)
  23.     head.next = tail
  24.     tail.prev = head
  25.     return &LRUCache{
  26.         capacity: capacity,
  27.         cache:    make(map[int]*DataLinkNode, capacity),
  28.         head:     head,
  29.         tail:     tail,
  30.     }
  31. }
  33. //初始化节点
  34. func InitialNode(key, value int) *DataLinkNode {
  35.     return &DataLinkNode{
  36.         key:   key,
  37.         value: value,
  38.     }
  39. }
  41. func (l *LRUCache) Get(key int) int {
  42.     if _, ok := l.cache[key]; !ok {
  43.         return -1 //key不存在
  44.     }
  45.     node := l.cache[key]
  46.     l.removeNode(node)
  47.     l.moveToHead(node)
  48.     return node.value
  49. }
  51. func (l *LRUCache) Put(key, value int) {
  52.     if _, ok := l.cache[key]; !ok { // key不存在
  53.         l.addToHead(InitialNode(key, value))
  54.         l.size++
  55.         if l.size > l.capacity {
  56.             l.removeTail()
  57.             delete(l.cache, key) //记得删除去掉的节点
  58.             l.size--
  59.         }
  60.     } else {
  61.         l.cache[key].value = value
  62.         node := l.cache[key]
  63.         l.moveToHead(node)
  64.     }
  66. }
  68. //增加节点到head
  69. func (l *LRUCache) addToHead(node *DataLinkNode) {
  70.     node.next = l.head.next
  71.     node.prev = l.head
  72.     l.head.next.prev = node
  73.     l.head.next = node
  74. }
  76. //移动节点到head
  77. func (l *LRUCache) moveToHead(node *DataLinkNode) {
  78.     l.removeNode(node)
  79.     l.addToHead(node)
  80. }
  82. //删除一个节点
  83. func (l *LRUCache) removeNode(node *DataLinkNode) {
  84.     node.prev.next = node.next
  85.     node.next.prev = node.prev
  86. }
  88. //删除最后一个节点
  89. func (l *LRUCache) removeTail() *DataLinkNode {
  90.     node := l.tail.prev
  91.     l.removeNode(node) //删除一个节点，直接调用自己的removeNode方法
  92.     return node
  93. }
  95. func main() {
  96.     cache1 := Constructor(3)
  97.     cache1.Put(1, 1)
  98.     cache1.Put(2, 2)
  99.     cache1.Get(1)
  100.     cache1.Put(3, 3)
  101.     cache1.Put(4, 4)
  102.     for cache1.head != nil {
  103.         fmt.Println(cache1.head.key)
  104.         cache1.head = cache1.head.next
  105.     }
  106. }

这道题感觉还是比较麻烦，指针指来指去很容易出问题，写的时候要很细心。

补充一个数组版本的LRU实现：

  1. type LRUCache struct {
  2.     len     int
  3.     dataList []Data //存储key,value
  4. }
  6. type Data struct {
  7.     Key int
  8.     Val int
  9. }
  11. func Constructor(capacity int) LRUCache {
  12.     return LRUCache{
  13.         len:capacity,
  14.     }
  15. }
  18. func (this *LRUCache) Get(key int) int {
  19.     isExist := false  //标志是否存在
  20.     index := 0
  21.     tmp := Data{}
  22.     for i, val := range this.dataList{ //存在key，把index和value取出
  23.         if val.Key == key {     //同时标记isExist为true
  24.             isExist = true
  25.             index = i 
  26.             tmp = val 
  27.             break
  28.         }
  29.     }
  30.     if isExist {
  31.         for ; index < len(this.dataList)-1; index++ {
  32.             this.dataList[index] = this.dataList[index+1]
  33.         } //需要整体左移，最右边的数据是最新使用过的
  34.         this.dataList[index] = tmp
  35.         return tmp.Val
  36.     }
  37.     return -1
  38. }
  41. func (this *LRUCache) Put(key int, value int)  {
  42.     isExist := false //标志位
  43.     index := 0  //索引位
  44.     for i, val := range this.dataList {
  45.         if val.Key == key {  //如果存在key，取出index，设置isExist为true
  46.             isExist = true
  47.             index = i 
  48.             break
  49.         }
  50.     }
  52.     if isExist {
  53.         for ; index < len(this.dataList)-1; index++ {
  54.             this.dataList[index] = this.dataList[index+1]
  55.         }//整体左移，最新使用过的数据放在最右边
  56.         this.dataList[index] = Data{Key:key, Val:value}
  57.     } else {//如果缓存已经满了，整体左移，然后把数据放在最右边一位
  58.         if len(this.dataList) == this.len {
  59.             for i := 0; i < this.len-1; i++ {
  60.                 this.dataList[i] = this.dataList[i+1]
  61.             }
  62.             this.dataList[this.len-1] = Data{Key:key, Val:value}
  63.         } else {//如果没有满，直接插入在最后
  64.             this.dataList = append(this.dataList,Data{Key:key, Val:value})
  65.         }
  66.     }
  67. }
  68. /**
  69.  * Your LRUCache object will be instantiated and called as such:
  70.  * obj := Constructor(capacity);
  71.  * param_1 := obj.Get(key);
  72.  * obj.Put(key,value);
  73.  */