题面描述:

给定一个缓存最多存放N页，输入K次操作，操作包括插入（A）、查询（Q）和删除（D）。插入时如果页面已存在则刷新访问时间，否则插入新页面，若超过容量N则淘汰最久未使用页面。查询和删除操作也会刷新页面的访问时间。最后输出缓存内页面编号，按LRU（最近最少使用）顺序排列。

思路

双向链表 + 哈希表

这是一道经典原题146. LRU缓存 。

每次查询或插入 key 成功后，都会更新 key 的优先级，这个优先级会影响大小满了之后，如何弹出旧元素，以有空间插入新元素。

朴素情况是，我们维护一个链表，每次遍历链表找到 key ，单次查找的时间复杂度是 $O(n)$ ，这会超时，考虑优化单次查找的时间。

单次查找这部分可以用哈希表来维护，这样插入和删除都是$O(1)$

此外，我们还需要维护一个优先级，这个优先级可以用一个链表维护。

我们需要弹出 key ，所以要从链表中插入删除节点，这就需要链表的前后节点，所以用双向链表维护。

时间复杂度：$O(n)$

题解详解

这道题的目标是实现一个支持 LRU（Least Recently Used）缓存淘汰算法 的缓存系统。LRU 算法旨在淘汰最近最少使用的元素，当缓存空间已满时，将最久未被使用的页面移出缓存，并保持常数时间复杂度完成插入、查询和删除操作。

为了高效地实现上述功能，通常使用以下两种数据结构的结合：

• 哈希表（unordered_map）：用于 O(1) 时间复杂度查找某个页面是否存在缓存中。
• 双向链表（doubly linked list）：用于维护页面的访问顺序。最近使用的页面放在链表头部，最久未使用的页面放在链表尾部。

通过将这两种数据结构结合，能够在 O(1) 的时间内完成插入、删除、和查询操作。

双向链表的作用

在 LRU 缓存中，每次查询或插入页面时，需要更新页面的访问顺序。最近访问的页面应当移到链表头部，而最久未使用的页面会移到链表尾部。一旦缓存满了，需要删除最久未使用的页面（即链表尾部的节点）。

双向链表便于我们在 O(1) 时间内完成以下操作：

• 在链表头部插入新的页面。
• 将某个已存在的页面移动到链表头部。
• 当缓存满时，删除链表尾部的页面。

哈希表的作用

哈希表用于 O(1) 时间内查找页面是否在缓存中。哈希表的键是页面的编号，值是该页面在双向链表中的节点指针。

题解流程

1. 初始化：创建一个可以容纳 N 个页面的缓存（双向链表），并配合哈希表来加速页面的查询操作。
2. 插入操作 A：如果页面已经存在缓存中，则将该页面移到链表头部；如果不存在且缓存未满，则直接插入链表头部；如果缓存已满，则先删除最久未使用的页面（链表尾部），再插入新页面。
3. 查询操作 Q：如果页面存在于缓存中，则将其移动到链表头部；如果不存在，则不进行任何操作。
4. 删除操作 D：如果页面存在于缓存中，则将其从链表和哈希表中删除；如果不存在，则忽略。
5. 输出：最后按照缓存中的 LRU 顺序，输出所有缓存中的页面编号。

代码

Python

class DoubleLinkedNode:
    def __init__(self, key=0, value=0):
        # 初始化双向链表节点
        # key 为节点的键值
        # value 为节点的值
        self.key = key
        self.value = value
        self.prev = None  # 前驱节点
        self.next = None  # 后继节点

class LRUCache:
    def __init__(self, cap):
        # 初始化 LRU 缓存
        self.cache = dict()  # 用哈希表存储 key-value 键值对
        self.head = DoubleLinkedNode()  # 创建头部节点
        self.tail = DoubleLinkedNode()  # 创建尾部节点
        self.head.next = self.tail  # 头尾相连
        self.tail.prev = self.head
        self.cap = cap  # 缓存容量
        self.size = 0  # 当前缓存大小

    def output(self):
        # 输出当前缓存中的所有值
        temp = self.head.next
        ans = []
        while temp and temp != self.tail:
            ans.append(temp.value)
            temp = temp.next
        print(*ans)

    def get(self, key):
        # 获取指定 key 的值
        if key not in self.cache:
            # 如果 key 不在缓存中，返回 -1
            return -1
        node = self.cache[key]
        # 将节点移到链表头部
        self.moveToHead(node)
        return node.value

    def put(self, key, value):
        # 设置指定 key 的值
        if key not in self.cache:
            # 如果 key 不在缓存中
            node = DoubleLinkedNode(key, value)
            self.cache[key] = node
            # 将节点添加到链表头部
            self.addToHead(node)
            self.size += 1
            if self.size > self.cap:
                # 如果缓存容量超限，删除尾部节点
                removed = self.removeTail()
                self.cache.pop(removed.key)
                self.size -= 1
        else:
            # 如果 key 在缓存中
            node = self.cache[key]
            node.value = value
            # 将节点移到链表头部
            self.moveToHead(node)

    def addToHead(self, node):
        # 将节点添加到链表头部
        node.prev = self.head
        node.next = self.head.next
        self.head.next.prev = node
        self.head.next = node

    def removeNode(self, node):
        # 从链表中删除节点
        node.prev.next = node.next
        node.next.prev = node.prev

    def moveToHead(self, node):
        # 将节点移到链表头部
        self.removeNode(node)
        self.addToHead(node)

    def removeTail(self):
        # 删除链表尾部节点
        node = self.tail.prev
        self.removeNode(node)
        return node

C++

#include <sstream>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <stack>

using namespace std;

// 定义链表节点结构体
struct node{
    int val; // 节点值
    struct node * next; // 指向下一个节点的指针
    struct node * pre; // 指向上一个节点的指针
};

// 解决问题的主函数
int solu4(){
    int n, k; // n表示链表最大长度, k表示操作次数
    cin>> n>>k; // 读入n和k

    // 创建链表头尾节点
    struct node* head = new(struct node);
    struct node* back = new(struct node);
    head->next = back; // 头节点指向尾节点
    back->pre = head; // 尾节点指向头节点

    int len= 0; // 当前链表长度
    char c; // 操作类型
    int val; // 操作值

    // 处理k次操作
    while(k--){
        cin>>c>>val; // 读入操作类型和值

        // 如果是添加操作
        if(c  == 'A') {
            bool a = false; // 标记是否找到相同值的节点
            struct node *tmp = head->next; // 从头节点的下一个节点开始遍历
            while (tmp != back) { // 遍历到尾节点前
                if (val == tmp->val) { // 如果找到相同值的节点
                    // 将该节点从链表中删除
                    tmp->pre->next = tmp->next;
                    tmp->next->pre = tmp->pre;
                    // 将该节点添加到头节点之后
                    tmp->next = head->next;
                    head->next->pre = tmp;
                    tmp->pre = head;
                    head->next = tmp;
                    a = true; // 标记已找到
                    break;
                }
                tmp = tmp->next; // 继续遍历下一个节点
            }
            if(!a){ // 如果没有找到相同值的节点
                // 创建新节点并添加到头节点之后
                struct node *cur = new(struct node);
                cur->val = val;
                cur->next = head->next;
                head->next->pre = cur;
                cur->pre = head;
                head->next = cur;

                len++; // 链表长度增加
                if(len>n){ // 如果长度超过n
                    // 删除尾节点之前的节点
                    struct node *tmp = back->pre;
                    back->pre = tmp->pre;
                    back->pre->next = back;
                    free(tmp);
                }
            }
        }
        // 如果是查询操作
        else if(c  == 'Q') {
            struct node *tmp = head->next;
            while (tmp != back) {
                if (val == tmp->val) { // 找到该值的节点
                    // 将该节点移动到头节点之后
                    tmp->pre->next = tmp->next;
                    tmp->next->pre = tmp->pre;
                    tmp->next = head->next;
                    head->next->pre = tmp;
                    tmp->pre = head;
                    head->next = tmp;
                    break;
                }
                tmp = tmp->next;
            }
        }
        // 如果是删除操作
        else if(c  == 'D') {
            struct node *dtmp = head->next;
            while (dtmp != back) {
                if (val == dtmp->val) { // 找到该值的节点
                    // 将该节点从链表中删除
                    dtmp->pre->next = dtmp->next;
                    dtmp->next->pre = dtmp->pre;
                    free(dtmp);
                    len--; // 链表长度减少
                    break;
                }
                dtmp =dtmp->next;
            }
        }
    }

    // 输出链表中的所有节点值
    struct node* tmp = head->next;
    while(tmp != back->pre){
        cout << tmp->val << ' ';
        tmp = tmp->next;
    }
    cout << tmp->val;
    return 0;
}

int main(){
    return solu4();
}

Java

import java.io.*;
import java.util.HashMap;

class Node {
    int no;
    Node left;
    Node right;

    public Node(int no) {
        this.no = no;
    }
}

public class Main{
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            // 总存放页数
            int n = ((int) in.nval);
            in.nextToken();
            HashMap<Integer, Node> map = new HashMap<>();
            Node dummyHead = new Node(-1);
            dummyHead.right = dummyHead;
            dummyHead.left = dummyHead;
            // 总操作数
            int k = ((int) in.nval);
            in.nextToken();
            for (int i = 0; i < k; i++) {
                String s = in.sval;
                in.nextToken();
                int a = ((int) in.nval);
                in.nextToken();
                if (s.equals("A")) {
                    if (!map.containsKey(a)) {
                        if (map.size() == n) {
                            // 删除最后的元素
                            Node del = dummyHead.left;
                            del.left.right = del.right;
                            del.right.left = del.left;
                            del.left = null;
                            del.right = null;
                            map.remove(del.no);
                        }
                        // 插入新元素
                        Node node = new Node(a);
                        node.right = dummyHead.right;
                        node.left = dummyHead;
                        dummyHead.right.left = node;
                        dummyHead.right = node;
                        map.put(a, node);
                    } else {
                        //从原来位置删除
                        Node node = map.get(a);
                        node.left.right = node.right;
                        node.right.left = node.left;
                        // 插入新位置
                        node.right = dummyHead.right;
                        node.left = dummyHead;
                        dummyHead.right.left = node;
                        dummyHead.right = node;
                    }
                } else if (s.equals("Q")) {
                    if (!map.containsKey(a)) continue;
                    //从原来位置删除
                    Node node = map.get(a);
                    node.left.right = node.right;
                    node.right.left = node.left;
                    // 插入新位置
                    node.right = dummyHead.right;
                    node.left = dummyHead;
                    dummyHead.right.left = node;
                    dummyHead.right = node;
                } else if (s.equals("D")) {
                    if (!map.containsKey(a)) continue;
                    //从原来位置删除
                    Node node = map.get(a);
                    node.left.right = node.right;
                    node.right.left = node.left;
                    node.left = null;
                    node.right = null;
                    map.remove(a);
                }
            }
            Node node = dummyHead.right;
            for (int i = 0; i < map.size(); i++, node = node.right) {
                out.print(node.no +  " ");
            }
            out.println();
            out.flush();
            return;
        }
    }
}

javaScript

const rl = require("readline").createInterface({ input: process.stdin });
var iter = rl[Symbol.asyncIterator]();
const readline = async () => (await iter.next()).value;

// 双向链表节点
class Node {
    constructor(no) {
        this.no = no;
        this.left = null;
        this.right = null;
    }
}

(async function () {
    let line1 = (await readline()).split(" ").map(Number);
    let n = line1[0]; // 读取总存放页数
    let k = line1[1]; // 读取总操作数
    let map = new Map();
    let dummyHead = new Node(-1);
    dummyHead.right = dummyHead;
    dummyHead.left = dummyHead;

    for (let i = 0; i < k; i++) {
        let line = (await readline()).split(" ");
        let s = line[0];
        let a = parseInt(line[1]);

        if (s === "A") {
            if (!map.has(a)) {
                if (map.size === n) {
                    // 删除最后的元素
                    let del = dummyHead.left;
                    del.left.right = del.right;
                    del.right.left = del.left;
                    map.delete(del.no);
                }
                // 插入新元素
                let node = new Node(a);
                node.right = dummyHead.right;
                node.left = dummyHead;
                dummyHead.right.left = node;
                dummyHead.right = node;
                map.set(a, node);
            } else {
                // 从原来位置删除
                let node = map.get(a);
                node.left.right = node.right;
                node.right.left = node.left;
                // 插入新位置
                node.right = dummyHead.right;
                node.left = dummyHead;
                dummyHead.right.left = node;
                dummyHead.right = node;
            }
        } else if (s === "Q") {
            if (!map.has(a)) continue;
            // 从原来位置删除
            let node = map.get(a);
            node.left.right = node.right;
            node.right.left = node.left;
            // 插入新位置
            node.right = dummyHead.right;
            node.left = dummyHead;
            dummyHead.right.left = node;
            dummyHead.right = node;
        } else if (s === "D") {
            if (!map.has(a)) continue;
            // 从原来位置删除
            let node = map.get(a);
            node.left.right = node.right;
            node.right.left = node.left;
            map.delete(a);
        }
    }

    // 输出链表中的元素
    let result = [];
    let node = dummyHead.right;
    while (node !== dummyHead) {
        result.push(node.no);
        node = node.right;
    }
    console.log(result.join(" "));
    rl.close();
})();

题目描述

$\qquad$小明有一门专业课，叫做操作系统，简称OS。操作系统的页式存储管理中，当主存满并且需要的存储页不在主存中，需要对主存中的页面进行置换，其中有一个非常重要的算法，即LRU置换算法。

$\qquad$LRU (Least Recently Used)缓存算法理一种常用于管理缓存的策略，其目标是保留最近使用过的数据,而淘汰最久未被使用的数据。实现简单的LRU缓存算法,支持查询、插入、删除操作。

$\qquad$最久未被使用定义：查询、插入和删除操作均为一次访问操作，每个元素均有一个最后一次被访问时间,按照最后一次被访问时间排序，时间最早的即为最久未使用。插入操作：当缓存中已经存在，则刷新值，不存在，则插入，如果超过上限，则淘汰最久未被使用的元素。

输入描述

$\qquad$第一行两个数N和K，分别表示缓存内最多可以存放页数，以及操作序列中的总操作数。其中N∈[1,100]，K∈[1,10000]。

$\qquad$第二至第K+1行，每行两个输入，两个输入用空格分隔。第一个输入是一个字符$ch_i$：A表示插入，Q表示查询，D表示删除。第二个输入是一个整数$a_i$，表示一个页面的编号。其中$a_i$∈[1,100000]。

输出描述

$\qquad$输出一行，表示缓存内各页面的编号，按照LRU优先级。

样例一

输入

2 5
A 103
A 102
A 102
Q 103
A 101

输出

101 103

解释

缓存大小为2，依次进行插入103、102，重复插入102，查询一次103，插入101时，最久未使用的元素为102，所以淘汰102。

Limitation

1s, 1024KiB for each test case.