题目描述

设计LRU缓存结构，该结构在构造时确定大小，假设大小为K，并有如下两个功能

• set(key, value)：将记录(key, value)插入该结构
• get(key)：返回key对应的value值

[要求]

1. set和get方法的时间复杂度为O(1)
2. 某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的。
3. 当缓存的大小超过K时，移除最不经常使用的记录，即set或get最久远的。

若opt=1，接下来两个整数x, y，表示set(x, y)
若opt=2，接下来一个整数x，表示get(x)，若x未出现过或已被移除，则返回-1
对于每个操作2，输出一个答案

版本一、

func LRU( operators [][]int ,  k int ) []int {
    // write code here
    res := make([]int,0,len(operators))
    key := make([]int,k)
    val := make([]int,k)
    for _,va := range operators{
        switch{
            case va[0] == 1:
            if len(key)==k{
                key = key[1:]
                val = val[1:]
            }
            key = append(key, va[1])
            val = append(val, va[2])
            break
            case va[0] == 2 :
            idx := -1
            for i:=0;i<len(key);i++{
                    if key[i] == va[1]{
                        idx = i
                        break
                    }
                }
                if idx == -1{
                    res = append(res, -1)
                }else{
                    res = append(res, val[idx])
                    if idx<k-1{
                        key = append(key[:idx], append(key[idx+1:],key[idx])...)
                        val = append(val[:idx], append(val[idx+1:],val[idx])...)
                    }
                }
             
            break
        }
         
    }
    return res
}

版本二、

package main
 
/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
type Data struct {
    Key   int
    Value int
}
 
type Node struct {
    data *Data
    pre  *Node
    next *Node
}
 
type LRUStruct struct {
    head     *Node
    tail     *Node
    lens     int
    hashMap  map[int]*Node
    capacity int
}
 
func (lruS *LRUStruct) InitLRU(capa int) {
    lruS.hashMap = make(map[int]*Node)
    lruS.capacity = capa
}
 
func (lruS *LRUStruct) Insert(key, value int) {
    if useV, ok := lruS.hashMap[key]; ok {
        useV.data.Value = value
        lruS.Delete(useV)
        lruS.InsertTop(useV)
    } else {
        newNode := &Node{
            data: &Data{key, value},
        }
        lruS.InsertTop(newNode)
    }
}
 
func (lruS *LRUStruct) Get(key int) int {
    if useV, ok := lruS.hashMap[key]; ok {
        lruS.Delete(useV)
        lruS.InsertTop(useV)
        return useV.data.Value
    }
    return -1
}
 
func (lruS *LRUStruct) Delete(node *Node) {
    if node == lruS.head {
        lruS.head = lruS.head.next
    }
    if node == lruS.tail {
        lruS.tail = lruS.tail.pre
    }
    if nil != node.pre {
        node.pre.next = node.next
    }
    if nil != node.next {
        node.next.pre = node.pre
    }
    node.pre = nil
    node.next = nil
    delete(lruS.hashMap, node.data.Key)
    lruS.lens--
}
 
func (lruS *LRUStruct) InsertTop(node *Node) {
    node.next = lruS.head
    if nil != lruS.head {
        lruS.head.pre = node
    }
    if nil == lruS.tail {
        lruS.tail = node
    }
    lruS.head = node
    lruS.lens++
    if lruS.lens > lruS.capacity {
        lruS.Delete(lruS.tail)
    }
    lruS.hashMap[node.data.Key] = node
}
 
func LRU(operators [][]int, k int) []int {
    var resultList []int
    var lrus LRUStruct
    lrus.InitLRU(k)
    for _, v := range operators {
        switch v[0] {
        case 1:
            lrus.Insert(v[1], v[2])
        case 2:
            resultList = append(resultList, lrus.Get(v[1]))
        }
        //lrus.Dump()
    }
    return resultList
}