华为OD机试 - 文件缓存系统——优先队列解法

题目描述

题目描述链接🔗

题目分析

• 这题需要我们实现一个LFUCache的自定义数据结构，根据题意，需要分别定义一个put和get方法，用于存储缓存和获取缓存。
• 本题难点在于put方法中，如果当前缓存空间如果不够存放新加入的缓存，则需要将已有缓存根据条件进行删除，直到可以存放新加的缓存。这里的条件是两个维度，分别是访问次数（少->多）、访问时间（老->新）。
• 我们需要一个数据结构来通过这两个条件，对加入的缓存进行排序，方便我们快速获取要删除的缓存，这里我们选择优先队列进行存储。并将访问次数和访问时间这两个属性将缓存封装为Cache的数据结构，通过这两个属性对Cache进行排序即可。

代码解析

代码已AC，细节见下面注释👇🏻

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int capacity = Integer.parseInt(sc.nextLine());
        int n = Integer.parseInt(sc.nextLine());
        LFUCache lfuCache = new LFUCache(capacity);
        //读取后续n个操作
        for (int i = 1; i <= n; i++) {
            String[] str = sc.nextLine().split(" ");
            //这里通过数组长度判断put/get操作，也可以通过第0个索引的字符串判断
            if (str.length == 3) {
                lfuCache.put(str[1], Integer.parseInt(str[2]), i);
            } else if (str.length == 2) {
                lfuCache.get(str[1], i);
            }
        }
        lfuCache.printCaches();
    }

    private static class LFUCache {
        private static int capacity;

        //缓存中剩余的空间
        private static int freeCap;

        private static final HashMap<String, Cache> name2File = new HashMap<>();

        //按访问次数从少到多，访问时间从老到新（从小到大）对缓存排序
        private static final PriorityQueue<Cache> pq = new PriorityQueue<>((a, b) ->
                a.visitCount == b.visitCount ? (a.visitTime - b.visitTime)
                        : a.visitCount - b.visitCount);

        public LFUCache(int capacity) {
            LFUCache.capacity = capacity;
            freeCap = capacity;
        }

        public void put(String fileName, int fileSize, int visitTime) {
            if (name2File.containsKey(fileName) || fileSize > capacity) {
                return;
            }
            Cache cache = new Cache(fileName, fileSize, visitTime);
            if (freeCap < cache.size) {
                //LFUCache剩余空间不够时，需要将已有缓存移除，直到满足当前新缓存cache
                while (freeCap < cache.size) {
                    if (pq.size() == 0) {
                        return;
                    }
                    //移除时需要将map和pq中的同一个对象都移除
                    Cache removed = pq.poll();
                    name2File.remove(removed.name);
                    freeCap += removed.size;
                }
            }
            //新加入时也要分别存储
            name2File.put(fileName, cache);
            pq.offer(cache);
            freeCap -= fileSize;
        }

        public void get(String fileName, int visitTime) {
            Cache cache = name2File.get(fileName);
            if (cache == null) {
                return;
            }
            //更新cache访问次数和时间
            cache.visitCount++;
            cache.visitTime = visitTime;
            //这个cache在map和优先队列中是同一个对象，修改了上面两个属性后优先队列并未重新排序
            //因此这里通过将cache重新加入队列的方式进行重新排序
            pq.remove(cache);
            pq.add(cache);
        }

        public void printCaches() {
            Collection<Cache> values = name2File.values();
            //没有缓存时，打印NONE
            if (values.size() == 0) {
                System.out.println("NONE");
            }
            StringJoiner sj = new StringJoiner(",");
            //剩余缓存字典序排序输出
            values.stream().sorted((a, b) -> a.name.compareTo(b.name))
                    .forEach(a -> sj.add(a.name));
            System.out.println(sj);
        }
    }

    private static class Cache {
        String name;
        int size;
        int visitCount;
        //访问时间，值越大访问时间越新
        int visitTime;

        public Cache(String name, int size, int visitTime) {
            this.name = name;
            this.size = size;
            this.visitCount = 0;
            this.visitTime = visitTime;
        }
    }
}

复杂度分析

时间复杂度：O(nlogn)，优先队列一次put或get操作需要O(logn)的时间，n个元素共需要O(nlogn)，n是操作数量。
空间复杂度：O(n)，n是操作数量，主要是一个哈希表和优先队列所占空间。