java - 做LeetCode刷题。LFU算法老是通不过所有的测试用例

Question

最近做Leetcode，里面有一道关于LFU的算法。但是老是通不过所有的测试用例。我感觉自己写的代码没有问题，但是他的测试用例确实又通不过（能通过大部分）。

package demo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.ListIterator;
import java.util.Map;
import java.util.Map.Entry;
import java.util.Set;

public class LFUCache {

    private Map<String, Node> cache = null;
    private Map<Long, List<Node>> countRecord = null;
    private int capacity = 0;
    private int used = 0;

    public LFUCache(int capacity) {
        cache = new LinkedHashMap<>(capacity, 0.75f, true);
        this.capacity = capacity;
        this.countRecord = new HashMap<>();
    }

    public int get(int key) {
        Node node = cache.get(String.valueOf(key));
        if (node == null) {
            return -1;
        }
        node.useCount++;
        node.lastGetTime = System.nanoTime();
        cache.put(String.valueOf(key), node);
        List<Node> list = countRecord.get(node.useCount);
        if (list == null || list.size() == 0) {
            list = new ArrayList<>();
        }
        list.add(node);
        countRecord.put(Long.valueOf(node.useCount), list);
        return node.value;
    }

    public void set(int key, int value) {
        used++;
        if (cache.get(String.valueOf(key)) != null) {
            cache.remove(String.valueOf(key));
            used--;
        }
        Node node = new Node();
        node.value = value;
        node.useCount = 0;
        node.lastGetTime = System.currentTimeMillis();
        if (used <= this.capacity) {
            cache.put(String.valueOf(key), node);
        } else {
            removeLast();
            if (cache.size() < this.capacity) {
                cache.put(String.valueOf(key), node);
            }
        }

    }

    // 淘汰最少使用的缓存
    private void removeLast() {
        int minCount = 0;
        long getTime = 0;
        int flag = 0;
        String waitRemoveKey = null;
        Set<Entry<String, Node>> set = this.cache.entrySet();
        ArrayList<Entry<String, Node>> list = new ArrayList<>(set);
        ListIterator<Entry<String, Node>> itera = list.listIterator();
        while (itera.hasNext()) {
            Map.Entry<String, Node> entry = itera.next();
            flag++;
            String key = entry.getKey();
            Integer count = entry.getValue().useCount;
            long lastGetTime = entry.getValue().lastGetTime;
            if (flag == 1) {
                minCount = count;
                waitRemoveKey = key;
                getTime = entry.getValue().lastGetTime;
                if (minCount == 0) {
                    break;
                }
            }
            if (count < minCount) {
                minCount = count;
                waitRemoveKey = key;
                getTime = lastGetTime;
            }
            if (minCount == count) {
                if (getTime > lastGetTime) {
                    minCount = count;
                    waitRemoveKey = key;
                    getTime = lastGetTime;
                }
            }
        }

        if (waitRemoveKey != null) {
            this.cache.remove(waitRemoveKey);
        }

    }

    public class Node {

        public int value;
        public int useCount;
        public long lastGetTime;

    }

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.set(1, 1);
        cache.set(2, 2);
        cache.set(3, 3);
        System.out.println(cache.get(3));
        System.out.println(cache.get(2));
        cache.set(4, 1);
        System.out.println(cache.get(3));
        System.out.println(cache.get(4));
        System.out.println(cache.get(2));
    }

}

请问这是为什么？
原链接：https://leetcode.com/problems...

报告：https://leetcode.com/submissi...

Answer 1

你写的没看懂，有的地方System.nanoTime()写成了System.currentTimeMillis()，还有set的时候无论是否是已存在的key，你把useCount还是设置成了0，这里肯定是错了。改了你下你的提交：

import java.util.Date;
import java.util.HashMap;
import java.util.Iterator;
import java.util.Map;

public class LFUCache {

    private Map<String, Node> cache = null;
    private int capacity = 0;
    private int used = 0;

    public LFUCache(int capacity) {
        cache = new HashMap<String, Node>(capacity, 0.75f);
        this.capacity = capacity;
    }

    public int get(int key) {
        Node node = cache.get(String.valueOf(key));
        if (node == null) {
            return -1;
        }
        node.useCount++;
        node.lastGetTime = System.nanoTime();
        return node.value;
    }

    public void set(int key, int value) {
        Node n = cache.get(String.valueOf(key));
        if (n != null) {
            n.useCount ++;
            n.lastGetTime = System.nanoTime();
            n.value = value;
            return;
        }else{
            Node node = new Node();
            node.value = value;
            node.useCount = 0;
            node.lastGetTime = System.nanoTime();
            if(this.capacity == 0)return;
            if (used < this.capacity) {
                used ++;
                cache.put(String.valueOf(key), node);
            } else {
                removeLast();
                cache.put(String.valueOf(key), node);
            }
        }
    }

    // 淘汰最少使用的缓存
    private void removeLast() {
        int minCount = Integer.MAX_VALUE;
        long getTime = System.nanoTime();
        String t = null;
        
        Iterator<String> it = cache.keySet().iterator();
        while(it.hasNext()){
            String key = it.next();
            Node node = cache.get(key);
            if(node.useCount < minCount || (node.useCount == minCount && node.lastGetTime < getTime)){
                t = key;
                minCount = node.useCount;
                getTime = node.lastGetTime;
            }
        }
        cache.remove(t);

    }

    public class Node {

        public int value;
        public int useCount;
        public long lastGetTime;

    }

    public static void main(String[] args) {
        LFUCache cache = new LFUCache(2);
        cache.set(1, 1);
        cache.set(2, 2);
        System.out.println(cache.get(1));
        cache.set(3,3);
        System.out.println(cache.get(2));
        System.out.println(cache.get(3));
        cache.set(4, 4);
        System.out.println(cache.get(1));
    }

}

Answer 2

我看题目的意思并不是按使用频率的高低，而是看有最近有没有使用。

基于这个思路，可以用 LinkedList 来实现，如果 get 或 set 访问到了这个 key，就把相应的 Node 挪到链表第一个节点上去。在 set 的时候，如果这个 key 的节点不存在，就插入到第1个位置，如果长度大于 capacity 就把最后一个挤掉。

……好吧，我理解错了，还是要按使用频率来排序……我还是把这个回答隐藏了免得误导