146. LRU 缓存

发表于 2023-07-03 更新于 2023-11-20 分类于力扣阅读次数： Waline：本文字数： 424 阅读时长 ≈ 1 分钟

考点

哈希表与链表的综合

题解

class LRUCache {
	private:
		struct Node {
			int key;
			int value;
			Node(int _key, int _value) : key(_key), value(_value) {}
		};
		int capacity;
		list<Node> l;
		unordered_map<int, list<Node>::iterator> m;

	public:
		LRUCache(int _capacity) : capacity(_capacity) {}

		int get(int key) {
			auto it = m.find(key);
			if (it == m.end())	return -1;
			int value = it->second->value;
            //先从链表中删除
			l.erase(it->second);
            //再添加到头部
			l.emplace_front(key, value);
            //更新哈希表
			m[key] = l.begin();
			return value;
		}

		void put(int key, int value) {
			auto it = m.find(key);
			if (it == m.end()) {
                //容量为0就不能插入新元素
				if (capacity == 0) return;
				if (m.size() == (unsigned long long)capacity) {
					m.erase(l.back().key);
					l.pop_back();
				}
			} else {
				l.erase(it->second);
			}
			l.emplace_front(key, value);
			m[key] = l.begin();
		}
};