首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数：31671 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:
1. Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2. get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3. set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹
数据范围:




示例1

输入

["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2

输出

["null","null","1","null","-1","null","-1","3","4"]

说明

我们将缓存看成一个队列，最后一个参数为2代表capacity，所以
Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
output=s.get(1);// 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null" 
output=s.get(2);// 因为get(2)操作，不存在对应的key，故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null" 
output=s.get(1);// 因为get(1)操作，不存在对应的key，故get操作返回"-1"
output=s.get(3);//因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
output=s.get(4);//因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"
算法知识视频讲解
添加回答
Go
只因不会Java头像 只因不会Java
灵神版
package main

import "container/list"

type entry struct {
    key, val int
}
type Solution struct {
     cap int
     cache map[int]*list.Element
     lst *list.List
}

func Constructor(capacity int) Solution {
    return Solution{
        cap: capacity,
        cache: map[int]*list.Element{},
        lst: list.New(),
    }
}

func (s *Solution) get(key int) int {
    e := s.cache[key]
    if e == nil {
        return -1
    }
    s.lst.MoveToFront(e)
    return e.Value.(entry).val
}

func (s *Solution) set(key int, value int)  {
    if e := s.cache[key]; e != nil {
        e.Value = entry{key, value}
        s.lst.MoveToFront(e)
        return
    } 

    s.cache[key] = s.lst.PushFront(entry{key, value})
    if len(s.cache) > s.cap {
        rmKey := s.lst.Remove(s.lst.Back()).(entry).key
        delete(s.cache, rmKey)
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * solution := Constructor(capacity);
 * output := solution.get(key);
 * solution.set(key,value);
 */

发表于 2022-10-18 09:40:38 回复(0)
Go
秋叶原の黑猫头像 秋叶原の黑猫
使用go的list包实现LRU 

package main

import "container/list"

type Solution struct {
     // write code here
    cap int 
    lst *list.List
    cache map[int]*list.Element
}

type entry struct{
    key,value int
}

func Constructor(capacity int) Solution {
    // write code here
    return Solution{
        capacity,
        list.New(),
        map[int]*list.Element{},
    }
}


func (this *Solution) get(key int) int {
    // write code here
    e:=this.cache[key]
    if e==nil{
        return -1
    }
    this.lst.MoveToFront(e)
    return e.Value.(entry).value
}


func (this *Solution) set(key int, value int)  {
    // write code here
    e:=this.cache[key]
    if e!=nil{
        e.Value=entry{key,value}
        this.lst.MoveToFront(e)
        return
    }
    this.cache[key]=this.lst.PushFront(entry{key,value})
    if len(this.cache)>this.cap{
        delete(this.cache,this.lst.Remove(this.lst.Back()).(entry).key)
    }
}


发表于 2022-09-13 19:20:14 回复(0)
Go
齐天旺旺头像 齐天旺旺 

// type Solution struct {
//      // write code here
// }


// func Constructor(capacity int) Solution {
//     // write code here
// }


// func (this *Solution) get(key int) int {
//     // write code here
// }


// func (this *Solution) set(key int, value int)  {
//     // write code here
// }


// /**
//  * Your Solution object will be instantiated and called as such:
//  * solution := Constructor(capacity);
//  * output := solution.get(key);
//  * solution.set(key,value);
//  */


package main

var head *Node
var end *Node

type Node struct {
   Key   int
   Value int
   pre   *Node
   next  *Node
}

func (n *Node) Init(key int, value int) {
   n.Key = key
   n.Value = value
}

type Solution struct {
   Capacity int              //页面初始化大小
   Size     int              //页面实际大小
   Map      map[int]*Node //具体的cache
}

func Constructor(capacity int) *Solution {
   Solution := Solution{Capacity: capacity}
   Solution.Map = make(map[int]*Node, capacity)
   return &Solution
}

func (l *Solution) get(key int) int {
   if v, ok := l.Map[key]; ok {
      l.refreshNode(v)
      return v.Value
   } else {
      return -1
   }
}

func (l *Solution) set(key, value int) {
   if v, ok := l.Map[key]; !ok {
      if len(l.Map) >= l.Capacity {
         oldKey := l.removeNode(head)
         delete(l.Map, oldKey)
      }
      node := Node{Key: key, Value: value}
      l.addNode(&node)
      l.Map[key] = &node
   } else {
      v.Value = value
      l.refreshNode(v)
   }
}

func (l *Solution) refreshNode(node *Node) {
   if node == end {
      return
   }
   l.removeNode(node)
   l.addNode(node)
}

func (l *Solution) removeNode(node *Node) int {
   if node == end {
      end = end.pre
   } else if node == head {
      head = head.next
   } else {
      node.pre.next = node.next
      node.next.pre = node.pre
   }
   return node.Key
}

func (l *Solution) addNode(node *Node) {
   if end != nil {
      end.next = node
      node.pre = end
      node.next = nil
   }
   end = node
   if head == nil {
      head = node
   }
}


发表于 2022-05-14 22:10:16 回复(0)
Go
_HAo头像 _HAo

Go 语言需要手动添加 package main

发表于 2022-05-02 20:07:04 回复(1)
提交观点

问题信息

模拟 链表 哈希
上传者：牛客301499号
难度：
4条回答 2985浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

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