2023-05-02 14:00 门头沟学院 嵌入式工程师
关注
LRU算法笔记
LRU算法使用双向链表和哈希表进行实现
1. 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
2.哈希表即为普通的哈希映射，通过缓存数据的键映射到其在双向链表中的位置。
所以，双向链表用于存储数据，增删头尾比较容易，但是需要知道地址才能erase中间元素，查找效率低；哈希表用于映射相应元素在双向链表中的地址，弥补了双向链表的查找效率。
两者配合实现增删查改。
cpp选手，双向链表list<int>，哈希表用unordered_map<int, list<int>::iterator>实现。
下图为华为426第二题cpp解法，引用了这位佬的一张图片，本菜鸡不太懂如何正确引用，只能放上佬的个人主页
https://www.nowcoder.com/users/515175727
图片有大佬水印，可直接访问主页
1. 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
2.哈希表即为普通的哈希映射，通过缓存数据的键映射到其在双向链表中的位置。
所以，双向链表用于存储数据，增删头尾比较容易，但是需要知道地址才能erase中间元素，查找效率低；哈希表用于映射相应元素在双向链表中的地址，弥补了双向链表的查找效率。
两者配合实现增删查改。
cpp选手，双向链表list<int>，哈希表用unordered_map<int, list<int>::iterator>实现。
下图为华为426第二题cpp解法，引用了这位佬的一张图片，本菜鸡不太懂如何正确引用，只能放上佬的个人主页
https://www.nowcoder.com/users/515175727
图片有大佬水印，可直接访问主页
全部评论
相关推荐
点赞 评论 收藏
分享
点赞 评论 收藏
分享
先锋战士：说得很真诚。鄙视链自古有之，学历，家庭背景，财富，权利。从小有之，小学羡慕那些当班委的，中学羡慕那些学生会的，高中羡慕尖子班拿教学金的，大学羡慕高绩点，毕业了羡慕进大厂的。工作了，又羡慕高职级的，再后来又羡慕别人早早结婚的。我想表达的观点很简单，无论是华为od还是百度，都是经历，没有孰高孰低，为了抵达下一个风景，总会付出更多东西，但不就是人生吗？正如登山，每个阶段的山，都要想办法攀登，在博主的文字中，见到了坚持和积极寻找问题解决办法的心态
点赞 评论 收藏
分享
