算法知识点————【LRU算法】

思想：淘汰最久没有使用的
应用场景：手机清后台的时候先清最久没有使用的应用
设计一种数据结构：接收一个 capacity 参数作为缓存的最大容量，然后实现两个 API，一个是 put(key, val) 方法存入键值对，另一个是 get(key) 方法获取 key 对应的 val，如果 key 不存在则返回 -1。要求：get 和 put 方法必须都是 O(1) 的时间复杂度。


哈希链表：哈希的查找配合双向链表的快速插入和删除

class Node{
public:
  int key,value;
  Node *prev,*next;
  Node(int k =0 ,int v =0 ) : key(k),value(v){}
};
class LRUCache{
private:
	int capacity;
    Node* dummy;//哨兵
    unordered_map<int,Node*> key_to_value;
  
  //删除节点
  void remove(Node * x){
    x->prev->next = x->next;
    x->next->prev = x->prev;
  }
  //添加节点 放到最上面
  void put_front(Node * x){
    x->prev = dummy;
    x->next = dummy->next;
    x->prev->next = x;
    x->next->prev = x;
  }  
  //获取节点 抽出放在最上面
  Node* get_node(int key){
    auto it = key_to_value.find(key);
    if(it == key_to_value.end()) return nullptr;//没找到
    auto node = it->second;//找到的话 map的node节点返回
    remove(node);
    put_front(node);
    return node;
  }
public:
  LRUCache(int capacity) : capacity(capacity),dummy(new Node()){
    dummy->prev  = dummy;
    dummy->next = dummy;
  }
  int get(int key){
    auto node = get_node(key);
    return node? node->value:-1;
  }
  void put(int key,int value){
    auto node = get_node(key);
    if(node){//有这本书
      node->value = value;
      return ;
    }
    key_to_value[key] = node = new Node(key,value);//没有这本书
    put_front(node);//添加
    if(key_to_value.size() > capacity){//添加得判断
      auto node_back = dummy->prev;
      key_to_value.erase(node_back->key);
      remove(node_back);
      delete node_back;
    }
  }
  
};

记录LRU算法在笔试题中的应用
题目：
设计实现一个LRU(Least Recently Used)缓存器
LRU有如下两个方法:
int get(int key) - 从缓存中取值，返回key对应的value(值总是一个正数)，如不存在返回-1。
void set(int key, int value) -**往缓存中存键值对。**当缓存达到容量限制时，令“最近最少使用”的键值对失效。
根据输入内容操作该LRU缓存器，输出LRU缓存器每个get的结果。
例如:
缓存器容量为3; set(1,2) set(2,3) set(3,4)
get(1)返回 2 get(4)返回 -1 set(4,5)
get(2) 返回 -1

输入描述
第一行输入两个数NL(N>0.L>0)，N为缓存器容量，L为接下来输入的行数
接下来输入L行:
(1)对应get操作,输入格式为"g%d";
(2)对应set操作，输入格式为"s%d %d”，前一个数为key，后一个为

代码：

#include <iostream>
#include <unordered_map>
#include <list>
using namespace std;

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

	int get(int key) {
		// 如果 key 不存在，返回 -1
		if (cacheMap.find(key) == cacheMap.end()) {
			return -1;
		}
		else {
			// 如果 key 存在，将该节点移动到链表头，并返回对应的值
			cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
			return cacheMap[key]->second;
		}
	}

	void set(int key, int value) {
		// 如果 key 已存在，更新 value，并将该节点移动到链表头
		if (cacheMap.find(key) != cacheMap.end()) {
			cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
			cacheMap[key]->second = value;
		}
		else {
			// 如果 key 不存在，先检查容量是否超限
			if (cacheList.size() == capacity) {
				// 超过容量，移除链表尾部的最少使用元素
				int lastKey = cacheList.back().first;
				cacheList.pop_back();
				cacheMap.erase(lastKey);
			}
			// 插入新元素到链表头
			cacheList.push_front(make_pair(key, value));
			cacheMap[key] = cacheList.begin();
		}
	}

private:
	int capacity;  // 缓存容量
	list<pair<int, int>> cacheList;  // 双向链表，保存键值对，最近使用的在前面
	unordered_map<int, list<pair<int, int>>::iterator> cacheMap;  // 哈希表，保存键和链表节点的映射
};

int main() {
	int N, L;
	cin >> N >> L;  // N 为缓存容量，L 为接下来操作的行数

	LRUCache lru(N);  // 创建一个容量为 N 的 LRU 缓存

	for (int i = 0; i < L; ++i) {
		string operation;
		cin >> operation;
		if (operation == "g") {
			int key;
			cin >> key;
			// 执行 get 操作
			cout << lru.get(key) << endl;
		}
		else if (operation == "s") {
			int key, value;
			cin >> key >> value;
			// 执行 set 操作
			lru.set(key, value);
		}
	}

	return 0;
}