数据结构与算法面试题：实现一个 LRU 缓存，支持如下操作：获取值、更新值、删除键值对和插入键值对

#include <iostream>
#include <unordered_map>
#include <list>

using namespace std;

class LRUCache {
public:
    LRUCache(int capacity) { // 构造函数
        cap = capacity; // 缓存容量
    }
    
    int get(int key) { // 获取值操作
        if (cache.count(key)) { // 缓存命中
            auto it = cache[key]; // 从哈希表中找到对应的迭代器
            int val = it->second; // 取出键值对中的值
            recent.erase(it); // 将访问过的键位于链表头部，将其删除
            recent.push_front(key); // 将当前键放在链表头部
            cache[key] = recent.begin(); // 更新键在双向链表中的对应迭代器位置
            return val;
        }
        return -1; // 缓存未命中
    }
    
    void put(int key, int value) { // 更新值操作
        if (cache.count(key)) { // 若键已存在，则替换其值
            auto it = cache[key]; // 从哈希表中找到对应的迭代器
            recent.erase(it); // 将访问过的键位于链表头部，将其删除
        }
        else if (recent.size() == cap) { // 若链表已满，则删除最久未使用的键
            int old_key = recent.back(); // 查找链表尾部的键值并保留
            recent.pop_back(); // 删除链表尾部的键值对
            cache.erase(old_key); // 从哈希表中删除对应的键
        }
        recent.push_front(key); // 将当前键放在链表头部
        cache[key] = recent.begin(); // 更新键在双向链表中的对应迭代器位置
        cache[key]->second = value; // 更新键值对中的值
    }

private:
    int cap;
    unordered_map<int, list<int>::iterator> cache; // 哈希表，键为键值，值为双向链表中对应节点的迭代器
    list<int> recent; // 双向链表，存储键值
};

int main() {
    LRUCache lru_cache(2);
    lru_cache.put(1, 1);
    lru_cache.put(2, 2);
    cout << lru_cache.get(1) << endl; // 查询键1，返回1，并将该键移动到链表头部
    lru_cache.put(3, 3); // 插入键3，此时容量超出限制，删除最近最少使用的键2
    cout << lru_cache.get(2) << endl; // 查询键2，未命中，返回-1
    lru_cache.put(4, 4); // 插入键4，此时容量超出限制，删除最近最少使用的键1
    cout << lru_cache.get(1) << endl; // 查询键1，未命中，返回-1
    cout << lru_cache.get(3) << endl; // 查询键3，返回3，并将该键移动到链表头部
    cout << lru_cache.get(4) << endl; // 查询键4，返回4，并将该键移动到链表头部
    return 0;
}

import java.util.*;

class LRUCache {
    private int cap;
    private Map<Integer, Integer> cache; // 哈希表，键为键值，值为对应的值
    private Deque<Integer> recent; // 双向链表，存储键值

    public LRUCache(int capacity) { // 构造函数
        cap = capacity; // 缓存容量
        cache = new HashMap<>();
        recent = new LinkedList<>();
    }

    public int get(int key) { // 获取值操作
        if (cache.containsKey(key)) { // 缓存命中
            recent.remove(key); // 移除双向链表中的键
            recent.addFirst(key); // 将当前键放在链表头部
            return cache.get(key); // 返回值
        }
        return -1; // 缓存未命中
    }

    public void put(int key, int value) { // 更新值操作
        if (cache.containsKey(key)) { // 若键已存在，则替换其值
            recent.remove(key); // 移除双向链表中的键
        }
        else if (recent.size() == cap) { // 若链表已满，则删除最久未使用的键
            int old_key = recent.removeLast(); // 查找链表尾部的键值并保留
            cache.remove(old_key); // 从哈希表中删除对应的键值对
        }
        recent.addFirst(key); // 将当前键放在链表头部
        cache.put(key, value); // 更新键值对中的值
    }
}

public class Main {
    public static void main(String[] args) {
        LRUCache lru_cache = new LRUCache(2);
        lru_cache.put(1, 1);
        lru_cache.put(2, 2);
        System.out.println(lru_cache.get(1)); // 查询键1，返回1，并将该键移动到链表头部
        lru_cache.put(3, 3); // 插入键3，此时容量超出限制，删除最近最少使用的键2
        System.out.println(lru_cache.get(2)); // 查询键2，未命中，返回-1
        lru_cache.put(4, 4); // 插入键4，此时容量超出限制，删除最近最少使用的键1
        System.out.println(lru_cache.get(1)); // 查询键1，未命中，返回-1
        System.out.println(lru_cache.get(3)); // 查询键3，返回3，并将该键移动到链表头部
        System.out.println(lru_cache.get(4)); // 查询键4，返回4，并将该键移动到链表头部
    }
}