Java | LeetCode

Задача: 460. LFU Cache
Сложность: hard

Спроектируйте и реализуйте структуру данных для кеша с наименьшим количеством использования (Least Frequently Used, LFU).

Реализуйте класс LFUCache:

LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.
int get(int key): Возвращает значение ключа, если ключ существует в кеше. В противном случае возвращает -1.
void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового элемента. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.
Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.
Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.

Функции get и put должны иметь среднюю временную сложность O(1).

Пример:

Input
["LFUCache", "put", "put", "get", "put", "get", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [3], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, 3, null, -1, 3, 4]

👨‍💻 Алгоритм:

1⃣insert(int key, int frequency, int value):
Вставить пару частота-значение в cache с заданным ключом.
Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

2⃣int get(int key):
Если ключа нет в кеше, вернуть -1.
Получить частоту и значение из кеша.
Удалить ключ из LinkedHashSet, связанного с частотой.
Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.
Вызвать insert(key, frequency + 1, value).
Вернуть значение.

3⃣void put(int key, int value):
Если capacity <= 0, выйти.
Если ключ существует, обновить значение и вызвать get(key).
Если размер кеша равен capacity, удалить первый элемент из LinkedHashSet, связанного с minf, и из кеша.
Установить minf в 1.
Вызвать insert(key, 1, value).

😎 Решение:

import java.util.*;

class LFUCache {
    private Map<Integer, LinkedHashSet<int[]>> frequencies;
    private Map<Integer, int[]> cache;
    private int capacity;
    private int minf;

    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minf = 0;
        this.cache = new HashMap<>();
        this.frequencies = new HashMap<>();
    }

    private void insert(int key, int frequency, int value) {
        frequencies.computeIfAbsent(frequency, k -> new LinkedHashSet<>()).add(new int[]{key, value});
        cache.put(key, new int[]{frequency, value});
    }

    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        int[] entry = cache.get(key);
        int frequency = entry[0];
        int value = entry[1];
        frequencies.get(frequency).remove(entry);
        if (frequencies.get(frequency).isEmpty()) {
            frequencies.remove(frequency);
            if (minf == frequency) minf++;
        }
        insert(key, frequency + 1, value);
        return value;
    }

    public void put(int key, int value) {
        if (capacity <= 0) return;
        if (cache.containsKey(key)) {
            cache.get(key)[1] = value;
            get(key);
            return;
        }
        if (cache.size() == capacity) {
            int[] leastUsed = frequencies.get(minf).iterator().next();
            frequencies.get(minf).remove(leastUsed);
            if (frequencies.get(minf).isEmpty()) frequencies.remove(minf);
            cache.remove(leastUsed[0]);
        }
        minf = 1;
        insert(key, 1, value);
    }
}

Ставь 👍 и забирай 📚 Базу знаний

595 views09:01