Could anyone tell me why my solution with Java Hashtable + PriorityQueue is wrong?


  • 0
    D
    public class LRUCache {
        private Map<Integer, Integer> map;
        private PriorityQueue<Pair> pri;
        private int capacity;
        private int timestamp;
        public LRUCache(int capacity) {
            map = new HashMap<>();
            pri = new PriorityQueue<Pair>(capacity, (x, y) -> (x.use - y.use));
            this.capacity = capacity;
            timestamp = 0;
        }
        
        public int get(int key) {
            if (!map.containsKey(key)) {
                return -1;
            }
            increase_use(key);
            return map.get(key);
        }
        
        public void set(int key, int value) {
            if (capacity == 0) return;
            increase_use(key);
            map.put(key, value);
            if (map.size() == capacity + 1) {
                Pair least_used = pri.poll();
                System.out.println(least_used.key);
                map.remove(least_used.key);
            } 
        }
        
        private void increase_use(int key) {
            boolean has_key = false;
            for (Pair each: pri) {
                if (each.key == key) {
                    each.use = timestamp;
                    has_key = true;
                }
            }
            if (!has_key) pri.add(new Pair(key, timestamp));
            ++timestamp;
        }
        
       class Pair {
            int key;
            int use;
            Pair(int key, int use) {
                this.key = key;
                this.use = use;
            }
        }
    }
    '''

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.