(C卷,200分)- 文件缓存系统（Java & JS & Python）

题目描述

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

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

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

用例

题目解析

本题其实就是让我们实现一个LFU缓存，关于LFU缓存的实现，大家可以先看下：

只有看懂上面博客实现后，才能继续做本题。

本题中的：

• fileName 相当于 key
• fileSize 相当于 val

本题中的：

• get(key)操作：
          
          如果 key 不存在，不需要做任何操作

          如果 key 存在，则仅增加key的访问次数

• put(key, val)操作：

          如果 key 存在，不需要做任何操作

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

本题还有一个变化点就是，put新增操作时，检查到LFU缓存的容量不足，LFUCache.capacity 小于 put的val值（文件大小），此时我们需要删除LFU缓存中最少，最远使用的key（文件名），此时可能需要进行多次删除，直到LFUCache.capacity >= put的val值。

JS算法源码

/** 双向链表节点 */
class Node {
  constructor(key, val, freq) {
    /** 记录本题的键 */
    this.key = key;
    /** 记录本题的值 */
    this.val = val;
    /** 记录该键被访问的次数 */
    this.freq = freq;
    /** 当前节点的上一个节点 */
    this.prev = null;
    /** 当前节点的下一个节点 */
    this.next = null;
  }
}

/** 双向链表 */
class Link {
  constructor() {
    /** 链表中节点个数 */
    this.size = 0;
    /** 链表头节点 */
    this.head = null;
    /** 链表尾节点 */
    this.tail = null;
  }

  /**
   * 尾插
   * @param {*} node 要被插入的节点
   */
  addLast(node) {
    if (this.size == 0) {
      // 空链表，则node节点插入后，即为头、尾节点
      this.head = node;
      this.tail = node;
    } else {
      // 非空链表，则node节点插入到tail节点后面
      this.tail.next = node;
      node.prev = this.tail;
      this.tail = node;
    }
    this.size++;
  }

  /**
   * 删除指定节点
   * @param {*} node 要删除的节点
   */
  remove(node) {
    // 空链表没有节点，所以无法删除
    if (this.size == 0) return;

    if (this.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;
    }

    this.size--;
  }
}

/** LFU缓存 */
class LFUCache {
  constructor(capacity) {
    /** keyMap用于记录key对应的node */
    this.keyMap = new Map();
    /** freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的 */
    this.freqMap = new Map();
    /** LFU缓存中能记录的最多key的数量 */
    this.capacity = capacity;
    /** LFU缓存中所有的key中最少的访问次数 */
    this.minFreq = 0;
  }

  get(key) {
    // 如果文件不存在，则不作任何操作。
    if (!this.keyMap.has(key)) return;

    const node = this.keyMap.get(key);
    // 每次文件访问后，总访问次数加1，最近访问时间更新到最新时间
    this.incNodeFreq(node);
  }

  put(key, val) {
    // 如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中
    if (this.keyMap.has(key)) return;

    // 当缓存空间不足以存放新的文件时，根据规则删除文件，直到剩余空间满足新的文件大小位置，再存放新文件。
    while (this.capacity < val) {
      if (this.minFreq == 0) {
        // 文件系统空了，也放不下该文件，则不放入
        return;
      }

      // 找出最少访问次数对应的链表
      let minFreqLink = this.freqMap.get(this.minFreq);

      // 链表头部节点是最少访问次数中，最远访问的文件，我们需要删除它
      const removeNode = minFreqLink.head;
      // 删除对应文件后，文件系统容量新增
      this.capacity += removeNode.val;

      // 执行删除操作，freqMap和keyMap都要删除掉对应文件的记录
      minFreqLink.remove(removeNode);
      this.keyMap.delete(removeNode.key);

      // 如果删除后，最少访问次数的链表空了，则需要找到下一个最少访问次数的链表
      if (minFreqLink.size == 0) {
        // 最少次数的链表空了，则删除对应最少次数的记录
        this.freqMap.delete(this.minFreq);

        // 更新最少次数
        if (this.freqMap.size > 0) {
          this.minFreq = Math.min(...this.freqMap.keys());
        } else {
          // 文件系统没有缓存文件了，则最少次数为0，表示文件系统空了
          this.minFreq = 0;
        }
      }
    }

    // 新增文件，则文件系统容量减少
    this.capacity -= val;
    // 新增文件的访问次数为1，因此最少访问次数变为了1
    this.minFreq = 1;
    const node = new Node(key, val, this.minFreq);

    // 执行新增操作，freqMap和keyMap都要新增对应文件的记录
    if (!this.freqMap.has(this.minFreq)) {
      this.freqMap.set(this.minFreq, new Link());
    }

    this.freqMap.get(this.minFreq).addLast(node);
    this.keyMap.set(key, node);
  }

  incNodeFreq(node) {
    const link = this.freqMap.get(node.freq);

    // 由于要更新文件的访问次数，因此需要将node从当前访问次数的链表中删除
    link.remove(node);

    // 如果当前访问次数链表只有当前node，则继续看当前链表对应的访问次数是否位最少访问次数，若是，则说明删除当前节点后，最少访问次数对应的文件没了
    if (link.size == 0) {
      // 当前访问次数没有对应文件（链表为空），则删除当前访问次数的记录（freqMap的key）
      this.freqMap.delete(node.freq);

      if (node.freq == this.minFreq) {
        // 此时我们应该更新最少访问次数
        this.minFreq++;
      }
    }

    node.freq++; // 总访问次数加1

    if (!this.freqMap.has(node.freq)) {
      this.freqMap.set(node.freq, new Link());
    }

    // 将node插入到对应freq的链表中
    // 尾插 是为了实现：最近访问时间更新到最新时间，即这里认为：链表尾部是最近的，链表头部是最远的
    this.freqMap.get(node.freq).addLast(node);
  }
}

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

// 输入输出处理
void (async function () {
  const m = parseInt(await readline());

  const lfuCache = new LFUCache(m);

  const n = parseInt(await readline());
  for (let i = 0; i < n; i++) {
    const operation = (await readline()).split(" ");

    const op = operation[0];
    const fileName = operation[1];

    if ("put" == op) {
      const fileSize = parseInt(operation[2]);
      lfuCache.put(fileName, fileSize);
    } else {
      lfuCache.get(fileName);
    }
  }

  if (lfuCache.capacity == m) {
    console.log("NONE");
  } else {
    console.log([...lfuCache.keyMap.keys()].sort().join(","));
  }
})();

Java算法源码

import java.util.HashMap;
import java.util.Scanner;
import java.util.StringJoiner;

public class Main {
  /** 双向链表节点 */
  static class Node {
    /** 记录本题的文件名 */
    String key;
    /** 记录本题的文件大小 */
    int val;
    /** 记录该文件的访问次数 */
    int freq;
    /** 当前节点的前一个节点 */
    Node prev;
    /** 当前节点的后一个节点 */
    Node next;

    public Node(String key, int val, int freq) {
      this.key = key;
      this.val = val;
      this.freq = freq;
      this.prev = null;
      this.next = null;
    }
  }

  /** 双向链表 */
  static class Link {
    /** 链表节点数 */
    int size;
    /** 链表头节点 */
    Node head;
    /** 链表尾节点 */
    Node tail;

    /**
     * 尾插
     *
     * @param node 要插入的节点
     */
    public void addLast(Node node) {
      if (this.size == 0) {
        this.head = node;
        this.tail = node;
      } else {
        this.tail.next = node;
        node.prev = this.tail;
        this.tail = node;
      }

      this.size++;
    }

    /**
     * 删除指定节点
     *
     * @param node 指定删除的节点
     */
    public void remove(Node node) {
      // 如果是空链表，则没法删除
      if (this.size == 0) return;

      if (this.size == 1) {
        // 如果是单节点链表，则删除完，链表为空
        this.head = null;
        this.tail = null;
      } else if (node == this.head) {
        // 被删除节点是链表头节点
        this.head = this.head.next;
        this.head.prev = null;
      } else if (node == this.tail) {
        // 被删除节点是链表尾节点
        this.tail = this.tail.prev;
        this.tail.next = null;
      } else {
        // 被删除节点是链表中间节点
        node.prev.next = node.next;
        node.next.prev = node.prev;
      }

      this.size--;
    }
  }

  static class LFUCache {
    /** key是文件名，value是文件信息（key.value本质是freqMap.value对应的链表中节点Node的对象地址） */
    HashMap<String, Node> keyMap;

    /** key是访问次数，value是访问次数位key的文件（Node）组成的链表（Link） */
    HashMap<Integer, Link> freqMap;

    /** 文件系统总容量 */
    int capacity;

    /** 最少访问次数（记录自各个文件访问次数中最少的那个） */
    int minFreq;

    public LFUCache(int capacity) {
      this.capacity = capacity;
      this.minFreq = 0;
      this.keyMap = new HashMap<>();
      this.freqMap = new HashMap<>();
    }

    /**
     * @param key 对应本题的文件名
     */
    public void get(String key) {
      // 如果文件不存在，则不作任何操作。
      if (!this.keyMap.containsKey(key)) return;

      Node node = this.keyMap.get(key);
      // 每次文件访问后，总访问次数加1，最近访问时间更新到最新时间
      incNodeFreq(node);
    }

    /**
     * @param key 对应本题的文件名
     * @param val 对应本题的文件大小
     */
    public void put(String key, int val) {
      // 如果新文件的文件名和文件缓存中已有的文件名相同，则不会放在缓存中
      if (this.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;

        // 执行删除操作，freqMap和keyMap都要删除掉对应文件的记录
        minFreqLink.remove(removeNode);
        this.keyMap.remove(removeNode.key);

        // 如果删除后，最少访问次数的链表空了，则需要找到下一个最少访问次数的链表
        if (minFreqLink.size == 0) {
          // 最少访问次数没有对应文件（链表为空），则删除最少访问次数的记录（freqMap的key）
          this.freqMap.remove(this.minFreq);

          if (this.freqMap.size() > 0) {
            this.minFreq = this.freqMap.keySet().stream().min((a, b) -> a - b).get();
          } else {
            // 文件系统没有缓存文件了，则最少次数为0，表示文件系统空了
            this.minFreq = 0;
          }
        }
      }

      // 新增文件，则文件系统容量减少
      this.capacity -= val;
      // 新增文件的访问次数为1，因此最少访问次数变为了1
      this.minFreq = 1;
      Node node = new Node(key, val, this.minFreq);
      // 执行新增操作，freqMap和keyMap都要新增对应文件的记录
      this.freqMap.putIfAbsent(this.minFreq, new Link());
      this.freqMap.get(this.minFreq).addLast(node);
      this.keyMap.put(key, node);
    }

    public void incNodeFreq(Node node) {
      Link link = this.freqMap.get(node.freq);

      // 由于要更新文件的访问次数，因此需要将node从当前访问次数的链表中删除
      link.remove(node);
      // 如果当前访问次数链表只有当前node，则继续看当前链表对应的访问次数是否位最少访问次数，若是，则说明删除当前节点后，最少访问次数对应的文件没了
      if (link.size == 0) {
        // 当前访问次数没有对应文件（链表为空），则删除当前访问次数的记录（freqMap的key）
        this.freqMap.remove(node.freq);

        if (node.freq == this.minFreq) {
          // 此时我们应该更新最少访问次数
          this.minFreq++;
        }
      }

      node.freq++; // 总访问次数加1
      this.freqMap.putIfAbsent(node.freq, new Link());
      // 将node插入到对应freq的链表中
      // 尾插 是为了实现：最近访问时间更新到最新时间，即这里认为：链表尾部是最近的，链表头部是最远的
      this.freqMap.get(node.freq).addLast(node);
    }
  }

  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);

    int m = Integer.parseInt(sc.nextLine());
    LFUCache lfuCache = new LFUCache(m);

    int n = Integer.parseInt(sc.nextLine());
    for (int i = 0; i < n; i++) {
      String[] operation = sc.nextLine().split(" ");

      String op = operation[0];
      String fileName = operation[1];

      if ("put".equals(op)) {
        int fileSize = Integer.parseInt(operation[2]);
        lfuCache.put(fileName, fileSize);
      } else {
        lfuCache.get(fileName);
      }
    }

    if (lfuCache.capacity == m) {
      // 如果文件系统容量没有减少，则没有文件被缓存
      System.out.println("NONE");
    } else {
      // 否则取出文件系统中的文件名，按照字典序输出
      StringJoiner sj = new StringJoiner(",");
      lfuCache.keyMap.keySet().stream().sorted().forEach(sj::add);
      System.out.println(sj);
    }
  }
}

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:
            # 空链表，则node节点插入后，即为头、尾节点
            self.head = node
            self.tail = node
        else:
            # 非空链表，则node节点插入到tail节点后面
            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 = {}  # keyMap用于记录key对应的node
        self.freqMap = {}  # freqMap的key是访问次数，value是具有相同访问次数的key对应的node组成的链表，链表头是最远访问的，链表尾是最近访问的
        self.capacity = capacity  # LFU缓存中能记录的最多key的数量
        self.minFreq = 0  # LFU缓存中所有的key中最少的访问次数

    def get(self, key):
        # 如果文件不存在，则不作任何操作。
        if key not in self.keyMap:
            return

        # 每次文件访问后，总访问次数加1，最近访问时间更新到最新时间
        node = self.keyMap[key]
        self.incNodeFreq(node)

    def put(self, key, 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

            # 执行删除操作，freqMap和keyMap都要删除掉对应文件的记录
            minFreqLink.remove(removeNode)
            self.keyMap.pop(removeNode.key)

            # 如果删除后，最少访问次数的链表空了，则需要找到下一个最少访问次数的链表
            if minFreqLink.size == 0:
                # 最少次数的链表空了，则删除对应最少次数的记录
                del self.freqMap[self.minFreq]

                # 更新最少次数
                if len(self.freqMap.keys()) > 0:
                    self.minFreq = min(self.freqMap.keys())
                else:
                    # 文件系统没有缓存文件了，则最少次数为0，表示文件系统空了
                    self.minFreq = 0

        # 新增文件，则文件系统容量减少
        self.capacity -= val
        # 新增文件的访问次数为1，因此最少访问次数变为了1
        self.minFreq = 1
        node = Node(key, val, self.minFreq)
        # 执行新增操作，freqMap和keyMap都要新增对应文件的记录
        self.freqMap.setdefault(self.minFreq, Link())
        self.freqMap.get(self.minFreq).addLast(node)
        self.keyMap[key] = node

    def incNodeFreq(self, node):
        """
        增加key的访问次数
        :param node: key对应的node
        """
        # 由于key的访问次数增加，因此要从原访问次数的链表中删除
        self.freqMap[node.freq].remove(node)

        # 如果原链表删除当前key对应的节点后为空，且原链表对应的访问次数就是最少访问次数
        if self.freqMap[node.freq].size == 0:
            # 最少次数的链表空了，则删除对应最少次数的记录
            del self.freqMap[node.freq]

            # 则最少访问次数对应的key没有了，因此最少访问次数++（即当前key访问次数++后，当前key的访问次数还是最少访问次数）
            if node.freq == self.minFreq:
                self.minFreq += 1

        # 当前key访问次数++
        node.freq += 1

        # 将当前key对应的node转移到对应增加后的访问次数对应的链表尾部（最近访问）
        self.freqMap.setdefault(node.freq, Link())
        self.freqMap[node.freq].addLast(node)


# 输入获取
m = int(input())

lfu = LFUCache(m)

n = int(input())

for _ in range(n):
    operation = input().split()

    op = operation[0]
    fileName = operation[1]

    if "put" == op:
        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))