楼主: 匿名
跳转到指定楼层
上一主题 下一主题
收起左侧

买它滇缅

地里匿名用户
🔗
匿名用户-QNMXX  2023-9-10 12:13:37
coco6120 发表于 2023-9-9 19:29
可以再用一个Hashmap来存key: node, 这样delete和removeLast就都是O(1)

确实 好像只能这样了。。。 哎碰到这种题算我倒霉吧
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-IB5LA  2023-9-10 12:36:12
匿名用户 发表于 2023-9-9 21:13
确实 好像只能这样了。。。 哎碰到这种题算我倒霉吧

lz请问第一个题请问需要支持哪些cmd?
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-QNMXX  2023-9-10 12:49:18
匿名用户 发表于 2023-9-9 21:36
lz请问第一个题请问需要支持哪些cmd?

你翻前面的楼有人贴出来了
回复

使用道具 举报

🔗
qinghuwei 2023-9-14 10:43:19 | 只看该作者
全局:
unordered_map + vector
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-QNMXX  2023-9-14 13:12:23

感觉不太行
回复

使用道具 举报

🔗
qinghuwei 2023-9-14 13:21:31 | 只看该作者
全局:

可以吧,unordered_map 存放key和对应的vector 位置.
然后vector里面存放key - value数据,
删除最后一个就是把 vector最后一个删除,然后把哈希表里面的也删除。
get就是直接从哈希表拿vector下标。
put就是看一下哈希表里面的有没有下标,如果没有下标就放最后,有下标就直接更新。
remove(key)就是查出来下标,然后和vector最后一个换下位置,然后更新一下哈希表。
回复

使用道具 举报

🔗
qinghuwei 2023-9-14 13:32:52 | 只看该作者
全局:

OK,看来需要两个vector 加一个hashmap。
两个vector一个存放key的访问顺序,另一个存放key-value.
回复

使用道具 举报

🔗
qinghuwei 2023-9-14 13:41:09 | 只看该作者
全局:
嗷嗷,好像用double linked list也行,这样就和LRU一样了。
回复

使用道具 举报

全局:
这个本质就是个LRU吧?用Map + 双向链表实现的LRU, 会有个单独的head node指向last。然后

                public void removeLast() {
                        hs.remove(head.next.key);       //删除头部数据
                        head.next = head.next.next;
                        head.next.prev = head;
                       
                }

本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-6SUBM  2023-9-30 06:16:38 来自APP
楼主继续加油,这拒得也挺快的,我的直接ghost,一周多没消息。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表