You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
* Design and implement a data structure for Least Recently Used (LRU) cache.
* It should support the following operations: get and set.
* get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
* set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
*/
publicclassSolution48 {
/*Time Limit Exceeded
private int capacity;
private HashMap<Integer, Integer> map;
private HashMap<Integer, Integer> gets;
public Solution48(int capacity) {
this.capacity = capacity;
map = new HashMap<Integer, Integer>();
gets = new HashMap<Integer, Integer>();
}
public int get(int key) {
if (map.containsKey(key)) {
int temp = gets.get(key);
gets.remove(key);
gets.put(key, ++temp);
return map.get(key);
}
return -1;
}
public void set(int key, int value) {
if (map.containsKey(key)) {
map.remove(key);
map.put(key, value);
} else {
if (capacity > 0) {
map.put(key, value);
gets.put(key, 0);
capacity--;
} else {
int min = 0;
int k = 0;
Iterator<Entry<Integer, Integer>> iter = map.entrySet().iterator() ;
while (iter.hasNext()) {
Map.Entry<Integer, Integer> entry = iter.next();
k = (min > entry.getValue() ? entry.getKey() : k);
min = (min > entry.getValue() ? entry.getValue() : min);