为啥我的理论运行结果是正确的，通过率是0，自己测试了几个都正确

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

struct Info
{
    int LocalCell;
    int NeighborCell;
    int optime = 0;
    int things = 0;
};

void writeInfos(vector<Info>& infos, Info info, int capacity)
{
    for(int i = 0; i < infos.size(); i++)
    {
        if(infos[i].LocalCell == info.LocalCell)
        {
            info.things = infos[i].things++;
            infos[i] = info;
            return;
        }
    }
    if(capacity > infos.size())
    {
        info.things++;
        infos.push_back(info);
        return;
    }
    info.things++;
    sort(infos.begin(),infos.end(),[](Info A, Info B)
    {
        if(A.things == B.things)
        {
            return A.optime < B.optime;
        }
        else 
        {
            return A.things < B.things;
        }
    });
    infos[0] = info;
    return;
}

void readInfos(vector<Info> &infos,int id, int optime)
{
    for(int i = 0; i < infos.size(); i++)
    {
        if(infos[i].LocalCell == id)
        {
            infos[i].things++;
            infos[i].optime = optime;
        }
    }
}

int queryInfo(vector<Info> &infos, int id)
{
    for(int i = 0; i < infos.size(); i++)
    {
        if(infos[i].LocalCell == id)
        {
            return infos[i].NeighborCell;
        }
    }
    return -1;
}

int main(void)
{
    string cmd;
    getline(cin,cmd);
    int capacity;
    cin >> capacity;
    vector<Info> infos;
    int optime = 0;
    while(getline(cin,cmd))
    {
        if(cmd == "write:")
        {
            int n;
            cin >> n;
            getchar();
            while(n--)
            {
                Info info_tmp;
                cin >> info_tmp.LocalCell >> info_tmp.NeighborCell;
                getchar();
                optime++;
                info_tmp.optime = optime;
                writeInfos(infos,info_tmp,capacity);
            } 
        }
        if(cmd == "read:")
        {
            int id;
            cin >> id;
            optime++;
            readInfos(infos,id,optime);
        }
        if(cmd == "query:")
        {
            int id;
            cin >> id;
            getchar();
        }
    }
    return 0;
}

思路

本题的原题是力扣460题。

本题的目标是实现一个具有LRU（最近最少使用）策略的缓存系统。为此，我们设计了一个名为Node的数据结构，以及结合哈希表和红黑树（通过std::set）的复合数据结构来支持缓存操作。

数据结构定义

• Node 结构：每个Node包含以下字段：

  • cnt：表示节点被访问的次数。
  • time：表示节点最近一次被访问的时间。
  • key：节点的键，用于标识缓存项。
  • value：节点的值，即缓存项的数据内容。

  这个结构既用于哈希表中的值，也用于红黑树中的元素。

• 哈希表：使用std::unordered_map存储键和指向节点的指针，以实现快速查找。

• 平衡二叉树：使用std::set来维护一个按(cnt, time)排序的节点集合，确保可以快速访问和删除最少使用的缓存项。

核心操作

• 读取（Read）操作：

  • 检查键是否存在于哈希表中。
  • 如果存在，则更新节点的cnt和time，重新插入到红黑树中以保持排序。
  • 返回节点的值。

• 写入（Write）操作：

  • 如果键存在，更新其值及访问的元数据（cnt和time），并更新红黑树。
  • 如果键不存在，创建一个新的节点，加入哈希表和红黑树。
  • 如果缓存已满（即达到预设的最大容量），则先从红黑树中移除最少使用的缓存项，然后移除对应的哈希表条目。

• 查询（Query）操作：

  • 直接通过哈希表检查键是否存在，并返回相应的值或-1（不存在的标志）。

在这个实现中，我们通过组合哈希表和红黑树来维护LRU缓存，这不仅确保了操作的效率，也简化了最少使用元素的管理。这种策略适用于需要频繁读写且对性能要求较高的场景。

代码

Python

import collections
import time

# 定义一个名为 Node 的类，类似于C++中的结构体
class Node:
    def __init__(self, cnt, tim, key, value):
        self.cnt = cnt  # 计数器，用于记录某个键的访问次数
        self.tim = tim  # 时间戳，用于记录某个键最后一次被访问的时间
        self.key = key  # 键
        self.value = value  # 键对应的值

    # 定义小于操作符，用于比较两个 Node 对象
    def __lt__(self, other):
        # 如果计数器相同，按时间戳排序；否则按计数器排序
        if self.cnt == other.cnt:
            return self.tim < other.tim
        return self.cnt < other.cnt

# 定义全局变量
n = 0  # 缓存的容量
tim = 0  # 全局时间戳
mapp = {}  # 存储键和值的映射
S = set()  # 用于存储所有的 Node 对象

# 获取某个键对应的值
def get(key):
    global tim
    if n == 0 or key not in mapp:  # 如果缓存容量为0或键不在映射中，返回-1
        return -1
    cache = mapp[key]  # 获取对应的缓存节点
    S.remove(cache)  # 从集合中删除旧节点
    cache.cnt += 1  # 增加访问计数器
    tim += 1  # 更新全局时间戳
    cache.tim = tim  # 更新节点的时间戳
    S.add(cache)  # 将更新后的节点重新插入集合
    mapp[key] = cache  # 更新映射中的节点
    return cache.value  # 返回节点的值

# 插入或更新某个键值对
def put(key, value):
    global tim
    if n == 0:  # 如果缓存容量为0，直接返回
        return
    if key not in mapp:  # 如果键不在映射中
        if len(mapp) == n:  # 如果映射中的元素数量等于缓存容量
            oldest = min(S)  # 获取集合中最小的节点（即要被替换的节点）
            S.remove(oldest)  # 从集合中删除该节点
            del mapp[oldest.key]  # 从映射中删除该节点
        tim += 1  # 更新全局时间戳
        cache = Node(1, tim, key, value)  # 创建一个新的节点
        mapp[key] = cache  # 将节点插入映射
        S.add(cache)  # 将节点插入集合
    else:  # 如果键已经在映射中
        cache = mapp[key]  # 获取对应的缓存节点
        S.remove(cache)  # 从集合中删除旧节点
        cache.cnt += 1  # 增加访问计数器
        tim += 1  # 更新全局时间戳
        cache.tim = tim  # 更新节点的时间戳
        cache.value = value  # 更新节点的值
        S.add(cache)  # 将更新后的节点重新插入集合
        mapp[key] = cache  # 更新映射中的节点

# 主函数
if __name__ == "__main__":
    s = input()  # 读取操作类型
    n = int(input())  # 读取缓存容量
    while True:
        try:
            s = input()  # 读取操作类型
            if s[0] == 'w':  # 如果操作是写入
                m = int(input())  # 读取写入操作的数量
                for _ in range(m):  # 逐个读取并写入键值对
                    a, b = map(int, input().split())
                    put(a, b)
            elif s[0] == 'r':  # 如果操作是读取
                x = int(input())  # 读取要查询的键
                get(x)
            else:  # 如果操作是查询当前缓存的值
                x = int(input())  # 读取要查询的键
                if x in mapp:  # 如果键在映射中
                    print(mapp[x].value)  # 打印对应的值
                else:
                    print(-1)  # 如果键不在映射中，打印-1
        except EOFError:
            break  # 读取结束后，退出循环

C++

#include <bits/stdc++.h>

using namespace std;

struct Node {
    int cnt, tim, key, value;
    Node() {}
    Node(int a, int b, int c, int d):cnt(a), tim(b), key(c), value(d){}
    bool operator < (const Node& nod) const {
        return cnt == nod.cnt ? tim < nod.tim : cnt < nod.cnt;
    }
};
int n, tim;
unordered_map<int, Node> mapp;
set<Node> S;
int get(int key) {
    if (n == 0 || mapp.find(key) == mapp.end()) {
        return -1;
    }
    Node cache = mapp[key];
    S.erase(cache);
    cache.cnt += 1;
    cache.tim = ++tim;
    S.insert(cache);
    mapp[key] = cache;
    return cache.value;
}

void put(int key, int value) {
    if (n == 0) return;
    auto it = mapp.find(key);
    if (it == mapp.end()) {
        if (mapp.size() == n) {
            mapp.erase(S.begin()->key);
            S.erase(S.begin());
        }
        Node cache = Node(1, ++tim, key, value);
        mapp[key] = cache;
        S.insert(cache);
    } else {
        Node cache = it->second;
        S.erase(cache);
        cache.cnt += 1;
        cache.tim = ++tim;
        cache.value = value;
        S.insert(cache);
        it->second = cache;
    }
}

int main() {
    string s;cin >> s;
    cin >> n;
    int x;
    while (cin >> s) {
        if (s[0] == 'w') {
            int m;
            cin >> m;
            while (m --) {
                int a, b;
                cin >> a >> b;
                put(a, b);
            }
        } else if(s[0] == 'r') {
        	cin >> x;
            get(x);
        } else while (cin >> x) {
            if (mapp.count(x)) cout << mapp[x].value << endl;
            else cout << -1 << endl;
        }
    }
}

Java

import java.util.*;

// 节点类，用于存储缓存条目
class Node implements Comparable<Node> {
    int cnt, tim, key, value;

    // 默认构造函数
    Node() {}

    // 带参构造函数
    Node(int a, int b, int c, int d) {
        this.cnt = a;
        this.tim = b;
        this.key = c;
        this.value = d;
    }

    // 定义节点的比较方式（用于排序）
    @Override
    public int compareTo(Node nod) {
        // 优先比较使用次数，次数相同则比较时间戳
        return this.cnt == nod.cnt ? this.tim - nod.tim : this.cnt - nod.cnt;
    }
}

public class Main {
    static int n, tim;  // 缓存的容量和全局时间戳
    static Map<Integer, Node> mapp = new HashMap<>();  // 用于存储键和节点的映射
    static TreeSet<Node> S = new TreeSet<>();  // 有序集合，用于自动排序节点

    // 获取缓存中的值
    static int get(int key) {
        if (n == 0 || !mapp.containsKey(key)) {  // 如果容量为0或键不存在
            return -1;
        }
        Node cache = mapp.get(key);  // 获取缓存节点
        S.remove(cache);  // 从有序集合中删除当前节点
        cache.cnt += 1;  // 增加访问次数
        cache.tim = ++tim;  // 更新时间戳
        S.add(cache);  // 将更新后的节点重新插入有序集合
        mapp.put(key, cache);  // 更新哈希映射
        return cache.value;  // 返回节点的值
    }

    // 插入或更新缓存
    static void put(int key, int value) {
        if (n == 0) return;  // 如果缓存容量为0，直接返回
        Node cache;
        if (!mapp.containsKey(key)) {  // 如果键不存在于缓存中
            if (mapp.size() == n) {  // 如果缓存已满
                Node firstNode = S.first();  // 获取使用次数最少且时间戳最早的节点
                mapp.remove(firstNode.key);  // 从哈希映射中删除
                S.remove(firstNode);  // 从有序集合中删除
            }
            cache = new Node(1, ++tim, key, value);  // 创建新节点
            mapp.put(key, cache);  // 将新节点加入哈希映射
            S.add(cache);  // 将新节点加入有序集合
        } else {  // 如果键已存在于缓存中
            cache = mapp.get(key);  // 获取对应的节点
            S.remove(cache);  // 从有序集合中删除旧节点
            cache.cnt += 1;  // 增加访问次数
            cache.tim = ++tim;  // 更新时间戳
            cache.value = value;  // 更新节点的值
            S.add(cache);  // 将更新后的节点重新插入有序集合
            mapp.put(key, cache);  // 更新哈希映射
        }
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String s = scanner.next();  // 读取第一个字符串（初始化）
        n = scanner.nextInt();  // 读取缓存容量
        int x;

        // 处理用户输入
        while (scanner.hasNext()) {
            s = scanner.next();  // 读取操作符
            if (s.charAt(0) == 'w') {  // 如果操作是'w'，进行写操作
                int m = scanner.nextInt();  // 读取接下来的操作次数
                while (m-- > 0) {  // 循环处理写操作
                    int a = scanner.nextInt();
                    int b = scanner.nextInt();
                    put(a, b);  // 将键值对放入缓存
                }
            } else if (s.charAt(0) == 'r') {  // 如果操作是'r'，进行读操作
                x = scanner.nextInt();
                get(x);  // 获取对应键的值
            } else {  // 其他情况下，处理查询操作
                while (scanner.hasNextInt()) {
                    x = scanner.nextInt();
                    if (mapp.containsKey(x)) {  // 如果键在缓存中
                        System.out.println(mapp.get(x).value);  // 打印值
                    } else {
                        System.out.println(-1);  // 键不存在，返回-1
                    }
                }
            }
        }
    }
}

Python

import heapq

# 节点类，用于存储缓存条目
class Node:
    def __init__(self, cnt=0, tim=0, key=0, value=0):
        self.cnt = cnt       # 使用次数
        self.tim = tim       # 时间戳
        self.key = key       # 键
        self.value = value   # 值

    # 定义节点的比较方式（用于排序）
    def __lt__(self, other):
        # 优先比较使用次数，次数相同则比较时间戳
        return (self.cnt, self.tim) < (other.cnt, other.tim)


class LFUCache:
    def __init__(self, capacity: int):
        self.capacity = capacity  # 缓存的容量
        self.tim = 0              # 全局时间戳
        self.mapp = {}            # 用于存储键和节点的映射
        self.S = []               # 使用优先队列（最小堆）用于自动排序节点

    # 获取缓存中的值
    def get(self, key: int) -> int:
        if self.capacity == 0 or key not in self.mapp:  # 如果容量为0或键不存在
            return -1
        cache = self.mapp[key]  # 获取缓存节点
        self.S.remove(cache)    # 从优先队列中删除当前节点
        heapq.heapify(self.S)   # 重新构建堆
        cache.cnt += 1          # 增加访问次数
        self.tim += 1
        cache.tim = self.tim    # 更新时间戳
        heapq.heappush(self.S, cache)  # 将更新后的节点重新插入优先队列
        self.mapp[key] = cache  # 更新哈希映射
        return cache.value      # 返回节点的值

    # 插入或更新缓存
    def put(self, key: int, value: int) -> None:
        if self.capacity == 0:  # 如果缓存容量为0，直接返回
            return
        if key in self.mapp:  # 如果键已存在于缓存中
            cache = self.mapp[key]  # 获取对应的节点
            self.S.remove(cache)    # 从优先队列中删除旧节点
            heapq.heapify(self.S)   # 重新构建堆
            cache.cnt += 1          # 增加访问次数
            self.tim += 1
            cache.tim = self.tim    # 更新时间戳
            cache.value = value     # 更新节点的值
        else:  # 如果键不存在于缓存中
            if len(self.mapp) == self.capacity:  # 如果缓存已满
                first_node = heapq.heappop(self.S)  # 弹出使用次数最少且时间戳最早的节点
                del self.mapp[first_node.key]       # 从哈希映射中删除
            cache = Node(1, self.tim + 1, key, value)  # 创建新节点
            self.tim += 1
        heapq.heappush(self.S, cache)  # 将节点插入优先队列
        self.mapp[key] = cache  # 更新哈希映射

# 主程序入口，处理用户输入，根据输入的指令执行相应的缓存操作
if __name__ == "__main__":
    import sys
    input = sys.stdin.read
    data = input().split()

    # 初始化缓存容量
    index = 1
    cache = LFUCache(int(data[index]))
    index += 1

    # 处理用户输入
    while index < len(data):
        s = data[index]
        index += 1
        if s[0] == 'w':  # 如果操作是'w'，进行写操作
            m = int(data[index])
            index += 1
            for _ in range(m):
                a = int(data[index])
                b = int(data[index + 1])
                cache.put(a, b)  # 将键值对放入缓存
                index += 2
        elif s[0] == 'r':  # 如果操作是'r'，进行读操作
            x = int(data[index])
            index += 1
            cache.get(x)  # 获取对应键的值
        else:  # 其他情况下，处理查询操作
            while index < len(data) and data[index].isdigit():
                x = int(data[index])
                index += 1
                if x in cache.mapp:  # 如果键在缓存中
                    print(cache.mapp[x].value)  # 打印值
                else:
                    print(-1)  # 键不存在，返回-1