返回目录

题目描述

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

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

• 存储文件（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 的整数输入

题目解析

本题中的：

• get(key)操作：

      如果 key 不存在，不需要做任何操作
  
      如果 key 存在，则仅增加key的访问次数

• put(key, val)操作：

      如果 key 存在，不需要做任何操作
  
      如果 key 不存在，则进行新增操作，这里可以初始化访问次数为1

Python算法源码

class Node:
    def __init__(self, key, val, 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 add_last(self, 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):
        """从链表中移除节点"""
        if self.size == 0:
            return
        if self.size == 1:
            self.head = None
            self.tail = None
        elif node == self.head:
            self.head = self.head.next
            self.head.prev = None
        elif node == self.tail:
            self.tail = self.tail.prev
            self.tail.next = None
        else:
            node.prev.next = node.next
            node.next.prev = node.prev
        self.size -= 1

class LFUCache:
    def __init__(self, capacity):
        self.capacity = capacity  # 缓存容量
        self.min_freq = 0  # 最小访问频率
        self.key_map = {}  # 键到节点的映射
        self.freq_map = {}  # 频率到链表的映射

    def get(self, key):
        """获取键对应的值"""
        if key not in self.key_map:
            return
        node = self.key_map[key]
        self._inc_node_freq(node)

    def put(self, key, val):
        """存储键值对"""
        if key in self.key_map:
            return
        while self.capacity < val:
            if self.min_freq == 0:
                return
            min_freq_link = self.freq_map[self.min_freq]
            remove_node = min_freq_link.head
            self.capacity += remove_node.val
            min_freq_link.remove(remove_node)
            del self.key_map[remove_node.key]
            if min_freq_link.size == 0:
                del self.freq_map[self.min_freq]
                if self.freq_map:
                    self.min_freq = min(self.freq_map)
                else:
                    self.min_freq = 0
        self.capacity -= val
        self.min_freq = 1
        node = Node(key, val, self.min_freq)
        self.freq_map.setdefault(self.min_freq, Link()).add_last(node)
        self.key_map[key] = node

    def _inc_node_freq(self, node):
        """增加节点的频率"""
        link = self.freq_map[node.freq]
        link.remove(node)
        if link.size == 0:
            del self.freq_map[node.freq]
            if node.freq == self.min_freq:
                self.min_freq += 1
        node.freq += 1
        self.freq_map.setdefault(node.freq, Link()).add_last(node)

if __name__ == "__main__":
    m = int(input())  # 缓存容量
    lfu_cache = LFUCache(m)
    n = int(input())  # 操作数
    for _ in range(n):
        operation = input().split()
        op = operation[0]  # 操作类型
        file_name = operation[1]  # 文件名
        if op == "put":
            file_size = int(operation[2])  # 文件大小
            lfu_cache.put(file_name, file_size)
        else:
            lfu_cache.get(file_name)

    if lfu_cache.capacity == m:
        print("NONE")
    else:
        files = sorted(lfu_cache.key_map.keys())
        print(",".join(files))  # 输出最近访问的文件名

Java算法源码

import java.util.*;

// 双向链表节点
class Node {
    String key; // 键
    int val; // 值
    int freq; // 频率
    Node prev; // 前一个节点
    Node next; // 后一个节点

    // 构造函数
    Node(String key, int val, int freq) {
        this.key = key;
        this.val = val;
        this.freq = freq;
    }
}

// 双向链表
class Link {
    int size; // 链表大小
    Node head; // 头节点
    Node tail; // 尾节点

    // 构造函数
    Link() {
        this.size = 0;
        this.head = null;
        this.tail = null;
    }

    // 在链表末尾添加节点
    void addLast(Node node) {
        if (size == 0) {
            this.head = node;
            this.tail = node;
        } else {
            this.tail.next = node;
            node.prev = this.tail;
            this.tail = node;
        }
        size++;
    }

    // 从链表中移除节点
    void remove(Node node) {
        if (size == 0)
            return;
        if (size == 1) {
            this.head = null;
            this.tail = null;
        } else if (this.head == node) {
            this.head = this.head.next;
            this.head.prev = null;
        } else if (this.tail == node) {
            this.tail = this.tail.prev;
            this.tail.next = null;
        } else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }
        size--;
    }
}

// LFU缓存
class LFUCache {
    HashMap<String, Node> keyMap; // 存储键值对应关系的哈希表
    HashMap<Integer, Link> freqMap; // 存储频率对应链表的哈希表
    int capacity; // 缓存容量
    int minFreq; // 最小频率

    // 构造函数
    LFUCache(int capacity) {
        this.keyMap = new HashMap<>();
        this.freqMap = new HashMap<>();
        this.capacity = capacity;
        this.minFreq = 0;
    }

    // 获取键对应的值
    void get(String key) {
        if (!keyMap.containsKey(key))
            return;
        Node node = keyMap.get(key);
        incNodeFreq(node);
    }

    // 添加键值对到缓存
    void put(String key, int val) {
        if (keyMap.containsKey(key))
            return;

        // 如果缓存容量不足，删除频率最低的节点直到容量足够
        while (this.capacity < val) {
            if (this.minFreq == 0)
                return;

            Link minFreqLink = this.freqMap.get(this.minFreq);
            Node removeNode = minFreqLink.head;

            this.capacity += removeNode.val;
            minFreqLink.remove(removeNode);
            keyMap.remove(removeNode.key);

            if (minFreqLink.size == 0) {
                this.freqMap.remove(this.minFreq);
                if (!this.freqMap.isEmpty())
                    this.minFreq = Collections.min(this.freqMap.keySet());
                else
                    this.minFreq = 0;
            }
        }

        // 更新缓存容量和最小频率
        this.capacity -= val;
        this.minFreq = 1;
        Node node = new Node(key, val, this.minFreq);
        this.freqMap.computeIfAbsent(this.minFreq, k -> new Link()).addLast(node);
        this.keyMap.put(key, node);
    }

    // 增加节点的频率
    void incNodeFreq(Node node) {
        this.freqMap.get(node.freq).remove(node);

        if (this.freqMap.get(node.freq).size == 0) {
            this.freqMap.remove(node.freq);
            if (node.freq == this.minFreq)
                this.minFreq++;
        }

        node.freq++;
        this.freqMap.computeIfAbsent(node.freq, k -> new Link()).addLast(node);
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int m = scanner.nextInt(); // 缓存容量
        LFUCache lfu = new LFUCache(m);
        int n = scanner.nextInt(); // 操作数
        for (int i = 0; i < n; i++) {
            String operation = scanner.next(); // 操作类型
            String fileName = scanner.next(); // 文件名
            if (operation.equals("put")) {
                int fileSize = scanner.nextInt(); // 文件大小
                lfu.put(fileName, fileSize);
            } else {
                lfu.get(fileName);
            }
        }
        // 输出剩余缓存中的键
        if (lfu.capacity == m)
            System.out.println("NONE");
        else {
            List<String> ans = new ArrayList<>(lfu.keyMap.keySet());
            Collections.sort(ans);
            System.out.println(String.join(",", ans));
        }
    }
}