JAVA Easy Solution for Reference


  • 0
    C

    The difference between HashSet and LinkedHashSet in Java is LinkedHashSet will keep the adding order of all elements, which is a little bit like a queue where the oldest elements will come out first. Therefore we could take advantage of this data structure and come up with this easy solution.
    (More detail on HashSet VS TreeSet VS LinkedHashSet on this post https://beginnersbook.com/2013/12/linkedhashset-class-in-java-with-example/)

    class LRUCache {
        
        int count = 0;
        int capacity = 0;
        Map<Integer,Integer> valueMap = new HashMap<>();
        LinkedHashSet<Integer> keySet = new LinkedHashSet<>();
        public LRUCache(int capacity) {
            this.capacity = capacity;
        }
        
        public int get(int key) {
            Integer result = valueMap.get(key);
            if(result == null)return -1; 
            else{
                keySet.remove(key);
                keySet.add(key);
                return result; 
            }
        }
        
        public void put(int key, int value) {
            if(keySet.contains(key)){
                keySet.remove(key);
                keySet.add(key);
                valueMap.put(key,value);
            }
            else{
                if(count >= capacity){
                    int oldest = keySet.iterator().next();
                    valueMap.remove(oldest);
                    keySet.remove(oldest);
                    count -= 1;
                }
                valueMap.put(key,value);
                keySet.add(key);
                count += 1;
            }
        }
    }
    

Log in to reply
 

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