国产手机做系统下载网站,垣曲网站建设,公司网站建设怎么计费,百度商家版下载leetcode: LRU 缓存 LRU 全称为 Least Recently Used#xff0c;最近最少使用#xff0c;常常用于缓存机制#xff0c;比如 cpu 的 cache 缓存#xff0c;使用了 LRU 算法。LRU 用于缓存机制时#xff0c;关键的是当缓存满的时候有新数据需要加载到缓存的#xff0c;这个…leetcode: LRU 缓存 LRU 全称为 Least Recently Used最近最少使用常常用于缓存机制比如 cpu 的 cache 缓存使用了 LRU 算法。LRU 用于缓存机制时关键的是当缓存满的时候有新数据需要加载到缓存的这个时候需要淘汰谁的问题。
如下图所示表示 LRU 算法的过程。假如有一个缓存共有 4 个存储空间按访问时间进行排序最左边的存储空间存储的是最近访问的数据最右边的存储空间存储的是最长时间没有访问的数据。
1一开始缓存是空的这个时候向缓存中放入一个数据 100100 放到最左边的存储空间
2向缓存中放入一个数据 50此时缓存有空余空间所以将已有的数据向后移动将 50 放到缓存的最左边
3向缓存中放入数据 500, 步骤与上一步相同
4向缓存中放入数据 1000步骤与上一步相同
5读取数据 100读取之后 100 就是最后访问的数据了所以将 100 移到缓存的最左边其它数据依次向后移动
6向缓存中放入数据 1此时缓存是满的所以需要先淘汰一个数据从访问时间来看最后一次访问 50 的间隔时间最长也就是排在最右边的数据所以将 50 淘汰其它数据向后移动将新数据 1 放入最左边的位置 如下是题目描述题目的最后要求 get() 和 put() 的时间复杂度都要是 O(1) 的。使用数组来表示缓存难以满足 O(1) 的要求因为在 put 或者 get 的时候会引起数组数据的移动数组中数据的移动时间复杂度是 O(n) 的。所以需要使用链表来表示缓存当访问一个数据的时候需要将当前这个数据从原来的位置上删除然后加到链表的头部删除一个节点的话需要将这个节点的前一个节点和下一个节点连接起来如果使用单向链表的话那么只能找到这个节点的下一个节点找不到上一个节点所以需要使用双向链表。 1使用双向循环链表来表示缓存
2为了满足时间复杂度是 O(1) 的要求使用 data_addr_ 数组来保存节点的地址数组的下标是 key题目中说明了 key 的取值范围是 [0, 10000]所以可以使用一个数组来表示。使用 map 也不能保证时间复杂度是 O(1) 的map 一般使用红黑树来实现时间复杂度是 O(logn) 的。把数组的下标当 key数组元素的值就是值数组本省也可以当做一个简单的 map 来使用。
3当 put 数据时要进行判断现在缓存是不是满了如果满的话需要删除最久没有访问的数据head_-next 保存最新访问的数据head_-prev 保存最久没有访问的数据
struct Node {int key;int value;struct Node *next;struct Node *prev;
};class LRUCache {
public:LRUCache(int capacity) {capacity_ capacity;head_ new Node();head_-next head_;head_-prev head_;}int get(int key) {Node *node data_addr_[key];if (node nullptr) {return -1;}ListUnLink(node);ListLinkHead(node);return node-value;}void put(int key, int value) {if (data_addr_[key] ! nullptr) { Node *node data_addr_[key];ListUnLink(node);node-value value;ListLinkHead(node);} else {Node *new_node new Node();new_node-key key;new_node-value value;new_node-next nullptr;new_node-prev nullptr;if (count_ capacity_) {Node *to_delete head_-prev;ListUnLink(to_delete);data_addr_[to_delete-key] nullptr;delete to_delete;count_--;}ListLinkHead(new_node);data_addr_[key] new_node;count_;}}void ListLinkHead(struct Node *ele) {ele-next head_-next;ele-next-prev ele;head_-next ele;ele-prev head_;}void ListUnLink(struct Node *ele) {ele-prev-next ele-next;ele-next-prev ele-prev;}private:int capacity_ 0;int count_ 0;Node *data_addr_[10001] {nullptr};struct Node *head_ nullptr;};
