买它滇缅

coco6120 发表于 2023-9-9 19:29
可以再用一个Hashmap来存key: node, 这样delete和removeLast就都是O(1)

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

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

lz请问第一个题请问需要支持哪些cmd？

匿名用户 发表于 2023-9-9 21:36
lz请问第一个题请问需要支持哪些cmd？

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

unordered_map + vector

qinghuwei 发表于 2023-9-13 19:43
unordered_map + vector

感觉不太行

匿名用户 发表于 2023-9-14 13:12
感觉不太行

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

匿名用户 发表于 2023-9-14 13:12
感觉不太行

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

嗷嗷，好像用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;
                       
                }

楼主继续加油，这拒得也挺快的，我的直接ghost，一周多没消息。