Java中的LRU缓存

Question

Problem 描述：

设计并实现了一种用于最小最近使用(LRU)缓存的数据结构。它应该支持以下操作: get和put。获取(键)-如果键存在于缓存中，则获取键的值(将始终为正)，否则返回-1。放置(键，值)-设置或插入的值，如果键还没有出现。当缓存达到其容量时，它应该在插入新项之前使最近使用最少的项失效。后续:您能在O(1)时间复杂度中同时执行这两种操作吗？

我通过了17/18的测试用例，但由于时间的限制，最后一个测试用例失败了。我猜这里有些东西不是O(1)？我花了好几个小时，但无法辨认。

class LRUCache {
    Map<Integer, Integer> cache;
    Queue<Integer> q;
    int capacity;

    public LRUCache(int capacity) {
        cache = new HashMap<>();
        q = new LinkedList<Integer>();
        this.capacity = capacity;
    }

    public int get(int key) {
        if (cache.get(key) == null || cache.get(key) == -1) return -1;
        int value = cache.get(key);
        q.remove(key);
        q.add(key);
        System.out.println("get() - key: " + key + " value: " + value);
        return value;
    }

    public void put(int key, int value) {
        if (cache.get(key) == null || cache.get(key) == -1) {
            if (q.size() >= capacity) {
                evict();
            }
        } else {
            q.remove(key);
        }
        q.add(key);
        cache.put(key, value);
        System.out.println("put()...key: " + key + " queue size: " + q.size());
    }

    private void evict() {
        int toRemove = q.remove();
        cache.put(toRemove, -1);
        System.out.println("Evict: " + toRemove + " queue size: " + q.size());
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

Answer 1

类LRUCache { Map缓存；Queue q；int容量；

是否有任何理由不使这些字段private？

public int get(int key) { if (cache.get(key) == null || cache.get(key) == -1) return -1;

为什么是特例如果cache.get(key) == -1？我在规范里没看到这个。

int value = cache.get(key);

这个方法现在已经调用cache.get(key)三次了。我认为这是可以优化的.

q.remove(key);

这不是O(1)。我怀疑您需要实现自己的链接列表才能从中间删除O(1)。

System.out.println("get() - key: " + key + " value: " + value);

我建议在要求检查代码之前删除调试打印。

public void put(int key, int value) {

我的观察结果与get上的观察结果相似。

private void evict() { int toRemove = q.remove(); cache.put(toRemove, -1);

哈?这回答了我先前提出的关于特殊情况的问题，但提出了一个更基本的问题。你明白LRU缓存的意义吗？你不应该拥有cache.size() > capacity。