首页
题库
公司真题
专项练习
面试题库
在线编程
面试
面试经验
AI 模拟面试
简历
求职
学习
课程
专栏·文章
竞赛
搜索
我要招人
发布职位
发布职位、邀约牛人
更多企业解决方案
在线笔面试、雇主品牌宣传
登录
/
注册
彭三岁
字节跳动_服务端开发
发布于北京
关注
已关注
取消关注
@永恒的图灵:
题解 | #go语言设计LRU缓存结构#
题目要求 get 和 set 请求都是 O(1)O(1)O(1) 的平均时间复杂度,那很容易想到使用 map,但如果 value 是 int 型,那就很难实现 LRU 的目的,我们可以设计一个双端链表,将最近访问和插入的节点插入到链表的头节点,当缓存不够时,只需要移出链表尾部的节点,因为要是 set 操作时间复杂度也是 O(1)O(1)O(1) 所以必须时刻记录尾节点的位置,这也是为什么要使用双端链表的目的。// 双向链表type DLinkedNode struct{ key,value int prev,next *DLinkedNode}type Solution struct { // write code here Capacity,size int Cache map[int]*DLinkedNode head,tail *DLinkedNode}// 生成链表节点func InitialDLinkNode(key,value int) *DLinkedNode{ return &DLinkedNode{key:key,value:value}} func Constructor(capacity int) Solution { solution:= Solution{ Capacity:capacity, // 生成虚拟头节点 head:InitialDLinkNode(0,0), // 生成虚拟尾节点 tail:InitialDLinkNode(0,0), Cache:make(map[int]*DLinkedNode,capacity), } // 初始化head和tail节点 solution.head.next=solution.tail solution.tail.prev=solution.head return solution}func (this *Solution) get(key int) int { // write code here if node,ok:=this.Cache[key];!ok{ return -1 }else{ // 最近访问的节点移动到链表头节点 this.moveToHead(node) return node.value } }func (this *Solution) set(key int, value int) { // write code here if node,ok:=this.Cache[key];!ok{ // 根据key,value生成链表节点 newNode:=InitialDLinkNode(key,value) this.Cache[key]=newNode // 新节点插入到链表头 this.addToHead(newNode) this.size++ // 缓存满 if this.size>this.Capacity{ // 移除尾节点 removed:=this.removeTail() delete(this.Cache,removed.key) this.size-- } }else{ node.value=value // 最近访问的节点移动到链表头 this.moveToHead(node) }}// 插入到链表头func (this *Solution) addToHead(node *DLinkedNode){ node.prev=this.head node.next=this.head.next this.head.next.prev=node this.head.next=node}// 删除节点func (this *Solution) removeNode(node *DLinkedNode){ node.prev.next=node.next node.next.prev=node.prev}// 移动节点到头节点位置func (this *Solution) moveToHead(node *DLinkedNode){ this.removeNode(node) this.addToHead(node)}// 移除尾节点func (this *Solution) removeTail()(node *DLinkedNode){ node=this.tail.prev this.removeNode(node) return node}/** * Your Solution object will be instantiated and called as such: * solution := Constructor(capacity); * output := solution.get(key); * solution.set(key,value); */
点赞 2
评论 0
全部评论
推荐
最新
楼层
秋招专场
校招火热招聘中
官网直投
相关推荐
贺兰星辰
06-01 21:11
百度_测试(实习员工)
过去、现在和未来 —— Java 的现代化之路
Java,一门广受赞誉,却又饱受诟病的语言,在从其诞生至今,便无时不刻的被于其他语言对比,有时候这种对比是空穴来风的诽谤,但更多的是对这门语言未来的担心,而近 10 年来涌现的一个又一个新生的程序语言更是让 Java 一次又一次地被推上风口浪尖,使公众一次又一次的质疑:Java,是否真的停滞不前了?2024 年,从大街上随便抓一个 Java 程序员,询问其 Java 有哪些槽点,我相信你的这个下午大概是别想离开这个人的声音了 —— 从泛型不支持基本数据类型到各种各样令人抓耳挠腮的奇怪问题,你绝对可以听这个人滔滔不绝地说上一整天。那么这些问题 Java 官方知道吗?当然知道,他们在解决吗?Umm...
我的求职思考
点赞
评论
收藏
转发
鱼大姐想要offer
05-27 14:29
蔚来_数据产品经理(准入职员工)
蔚来汽车25届提前批内推
【NIO新能源汽车明星品牌———蔚来2024届校园招聘内推!】【招聘岗位】:6大类IT技术类、产品类、运营类、米哈游、职能/行政/财会类、公关/市场/营销类、生产/制造/研发类【工作城市】:北京、上海、广州、深圳、成都、武汉等新一线城市皆有岗位在招。【内推链接】https://nio.jobs.feishu.cn/s/i2K7ebFF【内推码】R6D4SHC(内推简历优先筛选~)还有HC,不限学校,不限学历,抓紧投递!评论回复【姓名缩写 岗位】 能捞就捞,尽量保证不石沉大海。
投递蔚来等公司7个岗位 >
点赞
评论
收藏
转发
范晨
04-29 20:16
唐山师范学院 计算机类
7k 996
❤️职场感受7k 996 我看谁能去
点赞
评论
收藏
转发
热锅巴
04-20 18:13
合肥工业大学 计算机类
终于结束了
昨天同时收到两个意向。最后决定去淘天了这两个月终于可以告一段落了后续更新一些面经和时间线。还有很多录音没复盘hhhh
点赞
评论
收藏
转发
美团sp_offer发放机
05-30 21:08
美团_ios/mac
求求大家投下美团吧,暑期春招hc空缺严重,还空1000+
美团内推码:6Z9YCJ5 投递链接: https://zhaopin.meituan.com/web/campus美团内推码:6Z9YCJ5 想来美团的走我内推,牛客私信我,我来推进面试offer流程。历史offer千人入职美团有图有真相 如果自己已经投过也可以牛客私信我,秋招社招走我内推 全流程推进,hc 充足, 来美团牛客私信我就对了,跟对人走对路很关键 ,我给大家全流程推进
投递美团等公司10个岗位 >
点赞
评论
收藏
转发
点赞
收藏
评论
分享
回复帖子
提到的真题
返回内容
全站热榜
1
...
给你们预测一下今年的秋招!
3353
2
...
阿里体检完还没发正式offer
2504
3
...
【🎁】25届硬件牛牛互助计划(1期)
2393
4
...
5.31拼多多服务端开发实习生一面(75min)
2283
5
...
海康暑期实习
2244
6
...
深圳蟑螂真的很可怕吗
2197
7
...
毕业了!
1985
8
...
拿了蓝桥杯c++b组国二,水平怎么样,找后端开发工作有多大优势?
1850
9
...
momenta 实习 C++ 一面
1730
10
...
海康威视,25暑期实习,软件开发岗
1674
正在热议
#
和牛牛一起刷题打卡
#
13979次浏览
1290人参与
#
通信硬件薪资爆料
#
256235次浏览
2411人参与
#
不去互联网可以去金融科技
#
4336次浏览
59人参与
#
牛客帮帮团来啦!有问必答
#
1094002次浏览
16330人参与
#
面试被问第一学历差时该怎么回答
#
18285次浏览
199人参与
#
简历中的项目经历要怎么写?
#
14326次浏览
191人参与
#
工作两年想退休了
#
19313次浏览
241人参与
#
简历中的项目经历要怎么写
#
482166次浏览
8763人参与
#
实习生应该准时下班吗
#
93334次浏览
706人参与
#
你收到了团子的OC了吗
#
530884次浏览
6297人参与
#
简历无回复,你会继续海投还是优化再投?
#
23489次浏览
329人参与
#
你已经投递多少份简历了
#
338638次浏览
4905人参与
#
你怎么评价今年的春招?
#
12476次浏览
193人参与
#
晒一晒我的offer
#
3771960次浏览
58078人参与
#
我的上岸简历长这样
#
202564次浏览
4099人参与
#
担心入职之后被发现很菜怎么办
#
39627次浏览
328人参与
#
本周投递记录
#
221041次浏览
5380人参与
#
我想象的工作vs实际工作
#
105787次浏览
1700人参与
#
硬件人的简历怎么写
#
81839次浏览
849人参与
#
产品人求职现状
#
56857次浏览
823人参与
#
工作压力大怎么缓解
#
12616次浏览
176人参与
牛客网
牛客企业服务