leetcode146——LRU缓存机制

题目地址

LRU(Least Recently Used)是一种常见的页面置换算法,在计算中,所有的文件操作都要放在内存中进行,然而计算机内存大小是固定的,所以我们不可能把所有的文件都加载到内存,因此我们需要制定一种策略对加入到内存中的文件进项选择。

leetcode146——LRU缓存机制

一、hash+双向链表

我们使用一个哈希表来维护,值和链表节点关系。用一个双向链表来模拟LRU缓存,该双向链表需要以下几个功能:

  • 删除尾部节点(代表最久未使用的数据)
  • 插入一个节点到头部位置(新使用了一个数据值)
  • 移动一个节点到首部(使用过的数据再次使用)
struct DLinkedNode
{
	int key, value;
	DLinkedNode* pre;
	DLinkedNode* nex;
	DLinkedNode() :key(0), value(0), pre(nullptr), nex(nullptr) {};
	DLinkedNode(int _key,int _value) :key(_key), value(_value), pre(nullptr), nex(nullptr) {};
};
class LRUCache {
	unordered_map<int, DLinkedNode*> cache;
	DLinkedNode* head;
	DLinkedNode* tail;
	int size;//目前缓存中的数据数量
	int v;//最大容量
private:
	void add_to_head(DLinkedNode* node)
	{
		node->pre = head;
		node->nex = head->nex;
		head->nex->pre = node;
		head->nex = node;
	}
	void removenode(DLinkedNode* node)//移除节点
	{
		node->pre->nex = node->nex;
		node->nex->pre = node->pre;
	}
	void movehead(DLinkedNode* node)
	{//移动到头部
		removenode(node);
		add_to_head(node);
	}
	int  remove_tail()
	{
		DLinkedNode* tail_node;
		tail_node = tail->pre;
		tail_node->pre->nex = tail;
		tail->pre = tail_node->pre;
		int key = tail_node->key;
		delete tail_node;
		return key;
	}
public:
	LRUCache(int capacity) {
		size = 0;
        v=capacity;
		head = new DLinkedNode();
		tail = new DLinkedNode();
		head->nex = tail;
		tail->pre = head;
	}

	int get(int key) {
		if (!cache.count(key))
		{
			return -1;
		}
		DLinkedNode* node = cache[key];
		movehead(node);
		return node->value;
	}

	void put(int key, int value) {
		if (!cache.count(key))
		{
			DLinkedNode* node = new DLinkedNode(key, value);
			add_to_head(node);
			cache[key] = node;
			size++;
			if (size > v)
			{
				int key=remove_tail();
				cache.erase(key);
                size--;
			}
		}
		else
		{
			DLinkedNode* node = cache[key];
			node->value = value;
			movehead(node);
		}
	}
};

上一篇:LRU算法 JS实现,双向链表+哈希表


下一篇:Java高级工程师进阶学习:字节跳动Java实习面试凉凉经