题面描述

我们需要设计一个文件缓存系统，该系统可以指定缓存的最大值（单位为字节）。文件缓存系统支持两种操作：

1. 存储文件（put）：将文件放入缓存系统中。
2. 读取文件（get）：从缓存系统中访问文件。如果文件不存在，则不做任何操作。

当缓存空间不足以存放新的文件时，系统需要根据一定的规则删除文件，直到剩余空间满足新文件的大小。删除规则如下：

• 第一优先顺序：访问次数从少到多。
• 第二优先顺序：最近访问时间从老到新。

思路

通过双向链表和哈希表实现高效的文件管理。当缓存空间不足时，优先删除访问频率最低且最久未访问的文件；每次文件访问后，更新其访问频率并调整其在链表中的位置。最终输出缓存中的文件名列表，按字典序排序。

1. 数据结构选择：

   • 使用一个哈希表（unordered_map）来存储文件名到文件信息的映射。
   • 文件信息包括文件大小、访问次数和最近访问时间。
   • 使用一个优先队列（priority_queue）来维护文件的删除顺序。

2. 操作实现：

   • put操作：
     • 检查文件是否已经存在于缓存中，如果存在则不进行任何操作。
     • 如果缓存空间不足，则按照删除规则删除文件，直到空间足够。
     • 将新文件放入缓存中，并更新缓存的总大小。
   • get操作：
     • 如果文件存在于缓存中，则更新其访问次数和最近访问时间。
     • 如果文件不存在，则不进行任何操作。

3. 删除规则：

   • 使用优先队列来维护文件的删除顺序。优先队列的排序规则为：
     • 访问次数少的文件优先删除。
     • 如果访问次数相同，则最近访问时间较早的文件优先删除。

cpp

#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

struct FileInfo {
    int size;
    int accessCount;
    int lastAccessTime;
};

class FileCache {
private:
    int maxSize;
    int currentSize;
    int time;
    unordered_map<string, FileInfo> cache;
    
    struct Compare {
        bool operator()(const pair<string, FileInfo>& a, const pair<string, FileInfo>& b) {
            if (a.second.accessCount != b.second.accessCount) {
                return a.second.accessCount > b.second.accessCount;
            }
            return a.second.lastAccessTime > b.second.lastAccessTime;
        }
    };
    
    priority_queue<pair<string, FileInfo>, vector<pair<string, FileInfo>>, Compare> pq;
    
public:
    FileCache(int m) : maxSize(m), currentSize(0), time(0) {}
    
    void put(const string& fileName, int fileSize) {
        if (cache.find(fileName) != cache.end()) {
            return; // 文件已存在，不进行任何操作
        }
        
        while (currentSize + fileSize > maxSize && !cache.empty()) {
            auto top = pq.top();
            pq.pop();
            currentSize -= top.second.size;
            cache.erase(top.first);
        }
        
        if (currentSize + fileSize <= maxSize) {
            FileInfo info = {fileSize, 0, time++};
            cache[fileName] = info;
            pq.push({fileName, info});
            currentSize += fileSize;
        }
    }
    
    void get(const string& fileName) {
        if (cache.find(fileName) != cache.end()) {
            cache[fileName].accessCount++;
            cache[fileName].lastAccessTime = time++;
            // 由于优先队列无法直接更新元素，我们需要重新插入
            pq.push({fileName, cache[fileName]});
        }
    }
    
    vector<string> getFileList() {
        vector<string> files;
        for (const auto& entry : cache) {
            files.push_back(entry.first);
        }
        sort(files.begin(), files.end());
        return files;
    }
};

int main() {
    int m, n;
    cin >> m >> n;
    FileCache fc(m);
    
    for (int i = 0; i < n; ++i) {
        string op, fileName;
        int fileSize = 0;
        cin >> op >> fileName;
        if (op == "put") {
            cin >> fileSize;
            fc.put(fileName, fileSize);
        } else if (op == "get") {
            fc.get(fileName);
        }
    }
    
    vector<string> files = fc.getFileList();
    if (files.empty()) {
        cout << "NONE" << endl;
    } else {
        for (int i = 0; i < files.size(); ++i) {
            if (i > 0) cout << ",";
            cout << files[i];
        }
        cout << endl;
    }
    
    return 0;
}

python

# 双向链表节点
class Node:
    def __init__(self, key, val, freq):
        """
        :param key: 文件名
        :param val: 文件大小
        :param freq: 文件被访问的次数
        """
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = None  # 前驱节点
        self.next = None  # 后继节点


# 双向链表
class Link:
    def __init__(self):
        self.size = 0  # 链表大小
        self.head = None  # 链表头节点
        self.tail = None  # 链表尾节点

    def addLast(self, node):
        """
        尾插法：将节点插入链表尾部
        :param node: 要插入的节点
        """
        if self.size == 0:
            # 如果链表为空，插入的节点既是头节点也是尾节点
            self.head = node
            self.tail = node
        else:
            # 否则将节点插入到链表尾部
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        self.size += 1

    def remove(self, node):
        """
        删除指定节点
        :param node: 要删除的节点
        """
        if self.size == 0:
            return  # 空链表无法删除

        if self.size == 1:
            # 如果链表只有一个节点，删除后链表为空
            self.head = None
            self.tail = None
        elif self.head == node:
            # 如果要删除的节点是头节点
            self.head = self.head.next
            self.head.prev = None
        elif self.tail == node:
            # 如果要删除的节点是尾节点
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            # 如果要删除的节点是中间节点
            node.prev.next = node.next
            node.next.prev = node.prev
        self.size -= 1


# LFU缓存系统
class LFUCache:
    def __init__(self, capacity):
        self.keyMap = {}  # 记录文件名到节点的映射
        self.freqMap = {}  # 记录访问频率到链表的映射
        self.capacity = capacity  # 缓存的最大容量
        self.minFreq = 0  # 当前最小访问频率

    def get(self, key):
        """
        读取文件
        :param key: 文件名
        """
        if key not in self.keyMap:
            return  # 文件不存在，不进行任何操作

        # 文件存在，更新访问频率
        node = self.keyMap[key]
        self.incNodeFreq(node)

    def put(self, key, val):
        """
        存储文件
        :param key: 文件名
        :param val: 文件大小
        """
        if key in self.keyMap:
            return  # 文件已存在，不进行任何操作

        # 当缓存空间不足时，删除文件直到空间足够
        while self.capacity < val:
            if self.minFreq == 0:
                return  # 缓存已空，无法再删除文件

            # 找到最小访问频率对应的链表
            minFreqLink = self.freqMap[self.minFreq]

            # 删除链表头部的节点（访问频率最小且最久未访问）
            removeNode = minFreqLink.head
            self.capacity += removeNode.val  # 释放空间

            # 从 keyMap 和 freqMap 中删除该节点
            minFreqLink.remove(removeNode)
            self.keyMap.pop(removeNode.key)

            # 如果链表为空，删除该频率的记录
            if minFreqLink.size == 0:
                del self.freqMap[self.minFreq]

                # 更新最小访问频率
                if self.freqMap:
                    self.minFreq = min(self.freqMap.keys())
                else:
                    self.minFreq = 0  # 缓存已空

        # 添加新文件
        self.capacity -= val  # 占用空间
        self.minFreq = 1  # 新文件的访问频率为 1
        node = Node(key, val, self.minFreq)  # 创建新节点

        # 将节点添加到 freqMap 和 keyMap 中
        self.freqMap.setdefault(self.minFreq, Link())
        self.freqMap[self.minFreq].addLast(node)
        self.keyMap[key] = node

    def incNodeFreq(self, node):
        """
        增加节点的访问频率
        :param node: 要更新的节点
        """
        # 从原频率链表中删除该节点
        self.freqMap[node.freq].remove(node)

        # 如果原链表为空，删除该频率的记录
        if self.freqMap[node.freq].size == 0:
            del self.freqMap[node.freq]

            # 如果删除的频率是最小频率，更新最小频率
            if node.freq == self.minFreq:
                self.minFreq += 1

        # 更新节点的访问频率
        node.freq += 1

        # 将节点添加到新频率对应的链表中
        self.freqMap.setdefault(node.freq, Link())
        self.freqMap[node.freq].addLast(node)


# 输入处理
m = int(input())  # 缓存最大容量
lfu = LFUCache(m)  # 初始化 LFU 缓存

n = int(input())  # 操作数量
for _ in range(n):
    operation = input().split()  # 读取操作
    op = operation[0]  # 操作类型
    fileName = operation[1]  # 文件名

    if op == "put":
        fileSize = int(operation[2])  # 文件大小
        lfu.put(fileName, fileSize)  # 存储文件
    else:
        lfu.get(fileName)  # 读取文件

# 输出缓存中的文件名列表
if lfu.capacity == m:
    print("NONE")  # 缓存为空
else:
    ans = list(lfu.keyMap.keys())  # 获取缓存中的所有文件名
    ans.sort()  # 按字典序排序
    print(",".join(ans))  # 输出结果

java

import java.util.*;

public class Main {
    static class FileCache {
        private int maxSize;
        private int currentSize;
        private int time;
        private Map<String, FileInfo> cache;
        private PriorityQueue<FileEntry> pq;

        // 文件信息：大小、访问次数、最后访问时间
        static class FileInfo {
            int size;
            int accessCount;
            int lastAccessTime;
            FileInfo(int size, int accessCount, int lastAccessTime) {
                this.size = size;
                this.accessCount = accessCount;
                this.lastAccessTime = lastAccessTime;
            }
        }

        // 优先队列中的条目，包含文件名和文件信息
        static class FileEntry implements Comparable<FileEntry> {
            String fileName;
            FileInfo info;
            FileEntry(String fileName, FileInfo info) {
                this.fileName = fileName;
                this.info = info;
            }

            // 比较逻辑：访问次数少优先，时间早优先
            @Override
            public int compareTo(FileEntry o) {
                if (this.info.accessCount != o.info.accessCount) {
                    return Integer.compare(this.info.accessCount, o.info.accessCount);
                }
                return Integer.compare(this.info.lastAccessTime, o.info.lastAccessTime);
            }
        }

        public FileCache(int maxSize) {
            this.maxSize = maxSize;
            this.currentSize = 0;
            this.time = 0;
            this.cache = new HashMap<>();
            this.pq = new PriorityQueue<>();
        }

        public void put(String fileName, int fileSize) {
            if (cache.containsKey(fileName)) {
                return; // 文件已存在
            }

            // 删除文件直到空间足够
            while (currentSize + fileSize > maxSize && !cache.isEmpty()) {
                FileEntry entry = pq.poll(); // 弹出堆顶元素
                // 检查该条目是否有效（缓存中存在且信息一致）
                if (cache.containsKey(entry.fileName) && cache.get(entry.fileName) == entry.info) {
                    currentSize -= entry.info.size;
                    cache.remove(entry.fileName);
                }
            }

            if (currentSize + fileSize <= maxSize) {
                FileInfo info = new FileInfo(fileSize, 0, time++);
                cache.put(fileName, info);
                pq.offer(new FileEntry(fileName, info)); // 添加新条目到队列
                currentSize += fileSize;
            }
        }

        public void get(String fileName) {
            if (cache.containsKey(fileName)) {
                FileInfo oldInfo = cache.get(fileName);
                // 更新访问次数和时间
                FileInfo newInfo = new FileInfo(
                    oldInfo.size,
                    oldInfo.accessCount + 1,
                    time++
                );
                cache.put(fileName, newInfo);
                pq.offer(new FileEntry(fileName, newInfo)); // 添加新条目到队列
            }
        }

        public List<String> getFileList() {
            List<String> files = new ArrayList<>(cache.keySet());
            Collections.sort(files); // 字典序排序
            return files;
        }
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        sc.nextLine(); // 消耗换行符
        FileCache fc = new FileCache(m);

        for (int i = 0; i < n; i++) {
            String[] parts = sc.nextLine().split(" ");
            String op = parts[0];
            String fileName = parts[1];
            if (op.equals("put")) {
                int fileSize = Integer.parseInt(parts[2]);
                fc.put(fileName, fileSize);
            } else if (op.equals("get")) {
                fc.get(fileName);
            }
        }

        List<String> files = fc.getFileList();
        System.out.println(files.isEmpty() ? "NONE" : String.join(",", files));
    }
}

题目内容

请设计一个文件缓存系统，该文件缓存系统可以指定缓存的最大值（单位为字节）。

文件缓存系统有两种操作：

• 存储文件（put）

• 读取文件（get）

操作命令为：

• put fileName fileSize

• get fileName

存储文件是把文件放入文件缓存系统中；

读取文件是从文件缓存系统中访问已存在，如果文件不存在，则不作任何操作。

当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小位置，再存放新文件。

具体的删除规则为：

文件访问过后，会更新文件的最近访问时间和总的访问次数，当缓存不够时，按照第一优先顺序为访问次数从少到多，第二顺序为时间从老到新的方式来删除文件。

输入描述

第一行为缓存最大值 $m$（整数，取值范围为 $0 < m ≤ 52428800$）

第二行为文件操作序列个数 $n（0 ≤ n ≤ 300000）$

从第三行起为文件操作序列，每个序列单独一行，文件操作定义为：

op file_name file_size

file_name 是文件名，file_size 是文件大小

输出描述

输出当前文件缓存中的文件名列表，文件名用英文逗号分隔，按字典顺序排序，如：

a,c

如果文件缓存中没有文件，则输出NONE

备注

1.如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中

2.新的文件第一次存入到文件缓存中时，文件的总访问次数不会变化，文件的最近访问时间会更新到最新时间

3.每次文件访问后，总访问次数加1，最近访问时间更新到最新时间

4.任何两个文件的最近访问时间不会重复

5.文件名不会为空，均为小写字母，最大长度为10

6.缓存空间不足时，不能存放新文件

7.每个文件大小都是大于 0 的整数

样例1

输入

50
6
put a 10
put b 20
get a
get a
get b
put c 30

输出

a,c

样例2

输入

50
1
get file

输出

NONE