首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数：144640 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，操作次数是 n ，并有如下两个功能
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操作复杂度均为
数据范围： ，
示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出

[1,-1]

说明

[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
示例2

输入

[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2

输出

[1,-1,-1,3,4]
算法知识视频讲解
添加回答
Go
七月牧夫头像 七月牧夫 
package main

import "container/list"

type LRUCache struct {
	Len        int
	Value      map[int]int
	LruIndex   map[int]*list.Element
	Lru       *list.List
}

func (l *LRUCache) set(k, v int) {
	if l.Lru.Len() >= l.Len {
		k := l.Lru.Back().Value.(int)
		delete(l.Value, k)
		delete(l.LruIndex, k)
		l.Lru.Remove(l.Lru.Back())
	}
	l.Value[k] = v
	l.LruIndex[k] = l.Lru.PushFront(k)
}

func (l *LRUCache) get(k int) int {
	if v, ok := l.Value[k]; ok {
		l.Lru.MoveToFront(l.LruIndex[k])
		return v
	}
	return -1
}

func LRU( operators [][]int ,  k int ) []int {
	lru := &LRUCache{
		Len: k,
		Value: make(map[int]int),
        LruIndex: make(map[int]*list.Element),
		Lru: list.New(),
	}

	ret := make([]int, 0)
	for _, v := range operators {
		if v[0] == 1 {
			lru.set(v[1], v[2])
		}
		if v[0] == 2 {
			ret = append(ret, lru.get(v[1]))
		}
	}
	return ret
}

发表于 2022-02-13 23:32:31 回复(0)
Go
哎哟喂12138头像 哎哟喂12138

go 中没有对应的结构，需要自己定义相关数据结构，完整代码如下：

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LRU( operators [][]int ,  k int ) []int {
    // write code here
    res := make([]int,0)
    cache := newCache(k)
    for  i := range operators {
        if operators[i][0] == 1 {
            // set
            cache.Put(operators[i][1],operators[i][2])
        } else {
            val := cache.Get(operators[i][1])
            res = append(res,val)

        }
    }
    return res
}

type Node struct {
    Pre,Next *Node
    Key,Val int
}

func newNode(key,val int) *Node{
    return &Node{Key: key,Val: val}
} 

type LRUCache struct{
    Map map[int]*Node
    Head,Tail *Node
    Size int
    Cap int
}

func newCache(cap int) *LRUCache {
    cache := &LRUCache{
        Map: make(map[int]*Node,cap),
        Head: newNode(0,0),
        Tail: newNode(0,0),
        Size:0,
        Cap: cap,
    }

    cache.Head.Next = cache.Tail
    cache.Tail.Pre = cache.Head
    return cache
}

func (m *LRUCache)RemoveNode(node *Node) {
    node.Next.Pre = node.Pre
    node.Pre.Next = node.Next

}


func (m *LRUCache) RemoveTail() *Node {
    node := m.Tail.Pre
    m.RemoveNode(node)
    return node
}

func (m *LRUCache) MoveToHead(node *Node) {
    m.RemoveNode(node)
    m.AddToFront(node)
}

func (m *LRUCache) AddToFront(node *Node) {
    node.Next = m.Head.Next
    node.Pre = m.Head

    m.Head.Next.Pre = node
    m.Head.Next = node
}


func (m *LRUCache) Get(key int) int{
    if node,ok := m.Map[key];ok {
       m.MoveToHead(node)
        return node.Val
    } 
    return -1
}

func (m *LRUCache) Put(key,val int){
    if node,ok := m.Map[key];ok {
        node.Val = val
        m.MoveToHead(node)
        return
    } else {
        newNode := newNode(key,val)
        m.Map[key] = newNode
        m.AddToFront(newNode)
        m.Size++
        if m.Size > m.Cap {
            tail := m.RemoveTail()
            delete(m.Map,tail.Key)
            m.Size--
        }

    }
}
发表于 2021-12-01 23:06:03 回复(0)
Go
rouroumaibing头像 rouroumaibing 
package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LRU( operators [][]int ,  k int ) []int {
    // write code here
    var res []int
    quene := make([]int, 0)
    tmpMap := make(map[int]int)

    for loop:=0;loop < len(operators); loop++{
        if operators[loop][0] == 1 {
            if len(quene) >= k {
                delete(tmpMap, quene[0])
                quene = quene[1:]
            }
            quene= append(quene, operators[loop][1])
            tmpMap[operators[loop][1]]= operators[loop][2]
        }else if operators[loop][0] == 2 {
            if _, ok := tmpMap[operators[loop][1]]; ok{
                res = append(res, tmpMap[operators[loop][1]])
                index := Find(operators[loop][1], quene)
                quene = removeIndex(index, quene)
                quene = append(quene, operators[loop][1])
            }else{
                res = append(res, -1)
            }
        }
    }
    return res
}
func Find(a int, quene []int) int {
    for k, v := range quene {
        if v == a {
            return k
        }
    }
    return -1
}

func removeIndex(index int, quene []int) []int{
    tmp := make([]int, 0)
    for loop:= 0; loop < len(quene); loop++{
        if loop == index {
            continue
        }
        tmp = append(tmp, quene[loop])
    }
    return tmp
}

发表于 2021-10-31 16:13:12 回复(0)
Go
MambaHJ头像 MambaHJ

go 哈希表 + 双链表解法，container 包实现

package main

import (
    "sync"
    "container/list"
)

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
func LRU( operators [][]int ,  k int ) []int {
    // write code here
    cache := NewLruCache(k)
    var res []int
    for _, opt := range operators {
        o := opt[0]
        switch o {
        case 1:
            cache.Set(opt[1], opt[2])
        case 2:
            res = append(res, cache.Get(opt[1]))
        }
    }
    return res
}

type Node struct {
    key int
    val int
}

type LruCache struct {
    lruList *list.List
    cache map[int]*list.Element
    limit int
    mu sync.Mutex
}

func NewLruCache(k int) *LruCache {
    return &LruCache{
        lruList: list.New(),
        cache: make(map[int]*list.Element, k),
        limit: k,
    }
}

func (l *LruCache) Set(key, val int) {
    l.mu.Lock()
    defer l.mu.Unlock()
    // 更新
    if node, ext := l.cache[key]; ext {
        node.Value.(*Node).val = val
        l.lruList.MoveToFront(node)
        return
    }
    // 插入
    if len(l.cache) == l.limit {
        toDel := l.lruList.Back()
        delete(l.cache, toDel.Value.(*Node).key)
        l.lruList.Remove(toDel)
    }
    e := l.lruList.PushFront(&Node{
        key: key,
        val: val,
    })
    l.cache[key] = e
}

func (l *LruCache) Get(key int) int {
    l.mu.Lock()
    defer l.mu.Unlock()
    if node, ext := l.cache[key]; ext {
        l.lruList.MoveToFront(node)
        return node.Value.(*Node).val
    }
    return -1
}
发表于 2021-08-28 23:39:03 回复(0)
Go
找到工作了吗今天头像 找到工作了吗今天

单链表+虚拟头结点

每次插入到最前面

package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/

type lrulist struct {
    dummyhead *Listnode
    p int
    l int
}

type Listnode struct {
    key int
    value int
    next *Listnode
}


func LRU( operators [][]int ,  k int ) []int {
    // write code here
    list := &lrulist{&Listnode{},k,0}
    res := []int{}
    for i:=range operators {
        if operators[i][0]==1{
            list.set(operators[i][1],operators[i][2])
        }else{
            res=append(res,list.get(operators[i][1]))
        }
    }
    return res
}

func (l *lrulist) set(key,value int) {
    if l.l==l.p {
        l.removefront()
    }
    l.inserthead(key,value)
}

func (l *lrulist) get(key int) int {
    value := l.removekey(key)
    if value!=-1{
        l.inserthead(key,value)
    }
    return value
}

func (l *lrulist) removefront() {
    node := l.dummyhead
    for node.next!=nil && node.next.next!=nil {
        node=node.next
    }
    node.next=nil
    l.l--
}

func (l *lrulist) removekey(key int) int {
    node := l.dummyhead
    for node.next!=nil{
        if node.next.key==key{
            break
        }else{
            node=node.next
        }
    }
    if node.next==nil {
        return -1
    }else{
        res := node.next.value
        node.next=node.next.next
        l.l--
        return res
    }
}

func (l *lrulist) inserthead(key,value int) {
    tmp := &Listnode{key,value,nil}
    tmp.next=l.dummyhead.next
    l.dummyhead.next=tmp
    l.l++
}
发表于 2021-08-25 21:38:27 回复(0)
Go
👀offer快到碗里来！！！头像 👀offer快到碗里来！！！ 
package main

/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/
type LRUStruct struct {
    Size int
    Capacity int
    Cache map[int]*NodeList
    Head, Tail *NodeList
}

type NodeList struct {
    Key, Value int
    Prev, Next *NodeList
}

func LRU( operators [][]int ,  k int ) []int {
    res := []int{}
    newlru := initLRU(k)

    for i := 0;i < len(operators); i++{
        if len(operators[i]) == 3{
            newlru.set(operators[i][1], operators[i][2])
        }else{
            res = append(res, newlru.get(operators[i][1]))
        }
    }

    return res
}

func (this *LRUStruct) get(k int) int{
    if v, ok := this.Cache[k]; ok {
        this.removeToHead(v)
        return v.Value
    }

    return -1
}

func (this *LRUStruct) set(key int, value int) {
    if v, ok := this.Cache[key]; ok {
        v.Value = value
        this.removeToHead(v)
        return 
    }
    node := initNode(key, value)
    this.addToHead(node)
    this.Cache[key] = node
    this.Size ++
    if this.Size > this.Capacity {
        n := this.removeTail()
        delete(this.Cache, n.Key)
        this.Size --
    }

    return
}

func initNode (key int, value int) *NodeList {
    return &NodeList{Key:key, Value: value}
}

func initLRU(cap int) *LRUStruct {
    l := &LRUStruct{
        Capacity: cap,
        Cache: map[int]*NodeList{},
        Head: initNode(0, 0),
        Tail: initNode(0, 0),
    }
    l.Head.Next = l.Tail
    l.Tail.Prev = l.Head

    return l
}

func (this *LRUStruct) addToHead(node *NodeList) {
    node.Next = this.Head.Next
    node.Prev = this.Head
    this.Head.Next.Prev = node
    this.Head.Next = node
}

func (this *LRUStruct) removeNode(node *NodeList) {
    node.Prev.Next = node.Next
    node.Next.Prev = node.Prev
}

func (this *LRUStruct) removeToHead(node *NodeList){
    this.removeNode(node)
    this.addToHead(node)
}

func (this *LRUStruct) removeTail() *NodeList {
    node := this.Tail.Prev
    this.removeNode(node)

    return node
}
发表于 2021-08-24 17:08:53 回复(0)
Go
tttddd头像 tttddd

golang 双向链表+map 一个简单的代码示例

package main

import(
    "container/list"
)
/**
 * lru design
 * @param operators int整型二维数组 the ops
 * @param k int整型 the k
 * @return int整型一维数组
*/

//lru 数据结构
type lru struct{
    ll *list.List    //实际存储，用双向链表表示
    cache map[int]*list.Element    //从key到链表元素的映射
    cap int        //容量
}

//lru中存储的实体
type entry struct{
    key int
    value int
}

func (c *lru) get(key int)int{
    //查询到元素，将元素移动到链表表首
    if ele,ok:=c.cache[key];ok{
        en:=ele.Value.(*entry)
        c.ll.MoveToFront(ele)
        return en.value
    }
    return -1
}

func (c *lru) put(key int,value int){
    //更新
    if ele,ok:=c.cache[key];ok{
        c.ll.MoveToFront(ele)
        ele.Value.(*entry).value=value
        return
    }
    //容量已满需要删除
    if len(c.cache)==c.cap{
        last:=c.ll.Back()
        delete(c.cache,last.Value.(*entry).key)
        c.ll.Remove(last)
    }
    //添加一条实体
    en:=&entry{
        key:key,
        value:value,
    }
    c.cache[key]=c.ll.PushFront(en)
}

func LRU( operators [][]int ,  k int ) []int {
    // write code here
    ret:=make([]int,0)
    //新建一个lru缓存结构
    newlru:=&lru{
        ll:list.New(),
        cache:make(map[int]*list.Element),
        cap:k,
    }
    //执行操作，将结果写入ret
    for i:=0;i<len(operators);i++{
        if len(operators[i])==3{
            newlru.put(operators[i][1],operators[i][2])
        }else{
            ret=append(ret,newlru.get(operators[i][1]))
        }
    }
    return ret
}
发表于 2021-07-15 16:14:55 回复(1)
提交观点

问题信息

模拟
难度：
7条回答 15451浏览

热门推荐

通过挑战的用户

相关试题

设计LRU缓存结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号