package leetcode;

/**
 * https://leetcode.com/problems/lfu-cache/
 */
public class Problem460 {
    static class LFUCache {
        public LFUCache(int capacity) {
            // TODO
        }

        public int get(int key) {
            // TODO
            return 0;
        }

        public void put(int key, int value) {
            // TODO
        }
    }

    public static void main(String[] args) {
    }
}

@@ -12,16 +12,97 @@
 tcode;%0A%0A
+import java.util.HashMap;%0Aimport java.util.LinkedHashSet;%0Aimport java.util.Map;%0A%0A
 /**%0A * h
@@ -199,16 +199,376 @@
 Cache %7B%0A
+        private final Map%3CInteger /*key*/, Integer /*value*/%3E keyValues = new HashMap%3C%3E();%0A        private final Map%3CInteger /*key*/, Integer /*count*/%3E keyCounts = new HashMap%3C%3E();%0A        private final Map%3CInteger /*count*/, LinkedHashSet%3CInteger%3E /*keys*/%3E countKeys = new HashMap%3C%3E();%0A        private final int capacity;%0A        private int minCount = 0;%0A%0A
         
@@ -603,39 +603,57 @@
 ) %7B%0A            
-// TODO
+this.capacity = capacity;
 %0A        %7D%0A%0A    
@@ -698,115 +698,1324 @@
     
-// TODO%0A            return 0;%0A        %7D%0A%0A        public void put(int key, int value) %7B%0A            // TODO%0A
+if (capacity == 0 %7C%7C !keyValues.containsKey(key)) %7B%0A                return -1;%0A            %7D%0A            int oldCount = keyCounts.get(key);%0A            int newCount = oldCount + 1;%0A%0A            // Remove the old count for the given key.%0A            keyCounts.remove(key);%0A            // Update the new count for the given key.%0A            keyCounts.put(key, newCount);%0A%0A            // Remove the key from the old counts.%0A            LinkedHashSet%3CInteger%3E keys = countKeys.get(oldCount);%0A            keys.remove(key);%0A            if (keys.isEmpty()) %7B%0A                countKeys.remove(oldCount);%0A                // If the old count is no longer the min count, we go to the next min count.%0A                if (minCount == oldCount) %7B%0A                    minCount++;%0A                %7D%0A            %7D%0A            // Add a new key into the new counts.%0A            countKeys.putIfAbsent(newCount, new LinkedHashSet%3C%3E());%0A            countKeys.get(newCount).add(key);%0A%0A            return keyValues.get(key);%0A        %7D%0A%0A        public void put(int key, int value) %7B%0A            if (capacity == 0) %7B%0A                return;%0A            %7D%0A            if (keyValues.containsKey(key)) %7B%0A                // Overwrite the old value.%0A                keyValues.put(key, value);%0A                get(key);%0A                return;%0A    
     
@@ -2028,55 +2028,726 @@
     
+ 
-%7D%0A%0A    public static void main(String%5B%5D args) %7B
+       if (keyValues.size() == capacity) %7B%0A                // Evict.%0A                LinkedHashSet%3CInteger%3E keys = countKeys.get(minCount);%0A                int evictedKey = keys.iterator().next();%0A                keys.remove(evictedKey);%0A                if (keys.isEmpty()) %7B%0A                    countKeys.remove(minCount);%0A                %7D%0A                keyCounts.remove(evictedKey);%0A                keyValues.remove(evictedKey);%0A            %7D%0A            int count = 1; // initial count%0A            keyValues.put(key, value);%0A            keyCounts.put(key, count);%0A            countKeys.putIfAbsent(count, new LinkedHashSet%3C%3E());%0A            countKeys.get(count).add(key);%0A            minCount = count;%0A        %7D
 %0A   

Solve problem 460