460. LFU Cache

LeetCode hard original: C# #csharp #design #hard #hash-table #leetcode #linked-list

O texto da tarefa é traduzido do russo para o idioma selecionado. O código permanece sem alterações.

LeetCode Static

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

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

LFUCache(int capacity): Инициализирует объект с указанной вместимостью структуры данных.

int get(int key): returns значение ключа, если ключ существует в кеше. В противном случае returns -1.

void put(int key, int value): Обновляет значение ключа, если он уже присутствует, или вставляет ключ, если его еще нет. Когда кеш достигает своей вместимости, он должен аннулировать и удалить ключ, используемый наименее часто, перед вставкой нового elementа. В этой задаче, если имеется несколько ключей с одинаковой частотой использования, аннулируется наименее недавно использованный ключ.

Чтобы определить наименее часто используемый ключ, для каждого ключа в кеше поддерживается счетчик использования. Ключ с наименьшим счетчиком использования является наименее часто используемым ключом.

Когда ключ впервые вставляется в кеш, его счетчик использования устанавливается на 1 (из-за операции put). Счетчик использования для ключа в кеше увеличивается при вызове операции get или put для этого ключа.

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

Exemplo:

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]

C# solução

correspondente/original

using System;
using System.Collections.Generic;
public class LFUCache {
    private Dictionary<int, LinkedList<(int, int)>> frequencies = new Dictionary<int, LinkedList<(int, int)>>();
    private Dictionary<int, (int, LinkedListNode<(int, int)>)> cache = new Dictionary<int, (int, LinkedListNode<(int, int)>)>();
    private int capacity;
    private int minf;
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minf = 0;
    }
    private void Insert(int key, int frequency, int value) {
        if (!frequencies.ContainsKey(frequency)) {
            frequencies[frequency] = new LinkedList<(int, int)>();
        }
        frequencies[frequency].AddLast((key, value));
        cache[key] = (frequency, frequencies[frequency].Last);
    }
    public int Get(int key) {
        if (!cache.ContainsKey(key)) return -1;
        var (frequency,        node) = cache[key];
        frequencies[frequency].Remove(node);
        if (frequencies[frequency].Count == 0) {
            frequencies.Remove(frequency);
            if (minf == frequency) minf++;
        }
        Insert(key, frequency + 1, node.Value.Item2);
        return node.Value.Item2;
    }
    public void Put(int key, int value) {
        if (capacity <= 0) return;
        if (cache.ContainsKey(key)) {
            cache[key].node.Value = (key, value);
            Get(key);
            return;
        }
        if (cache.Count == capacity) {
            var oldest = frequencies[minf].First.Value;
            frequencies[minf].RemoveFirst();
            cache.Remove(oldest.Item1);
            if (frequencies[minf].Count == 0) frequencies.Remove(minf);
        }
        minf = 1;
        Insert(key, 1, value);
    }
}

C++ solução

rascunho automático, revisar antes de enviar

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
public class LFUCache {
    private unordered_map<int, LinkedList<(int, int)>> frequencies = new unordered_map<int, LinkedList<(int, int)>>();
    private unordered_map<int, (int, LinkedListNode<(int, int)>)> cache = new unordered_map<int, (int, LinkedListNode<(int, int)>)>();
    private int capacity;
    private int minf;
    public LFUCache(int capacity) {
        this.capacity = capacity;
        this.minf = 0;
    }
    private void Insert(int key, int frequency, int value) {
        if (!frequencies.count(frequency)) {
            frequencies[frequency] = new LinkedList<(int, int)>();
        }
        frequencies[frequency].AddLast((key, value));
        cache[key] = (frequency, frequencies[frequency].Last);
    }
    public int Get(int key) {
        if (!cache.count(key)) return -1;
        var (frequency,        node) = cache[key];
        frequencies[frequency].Remove(node);
        if (frequencies[frequency].size() == 0) {
            frequencies.Remove(frequency);
            if (minf == frequency) minf++;
        }
        Insert(key, frequency + 1, node.Value.Item2);
        return node.Value.Item2;
    }
    public void Put(int key, int value) {
        if (capacity <= 0) return;
        if (cache.count(key)) {
            cache[key].node.Value = (key, value);
            Get(key);
            return;
        }
        if (cache.size() == capacity) {
            var oldest = frequencies[minf].First.Value;
            frequencies[minf].RemoveFirst();
            cache.Remove(oldest.Item1);
            if (frequencies[minf].size() == 0) frequencies.Remove(minf);
        }
        minf = 1;
        Insert(key, 1, value);
    }
}

Java solução

correspondente/original

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);
    }
}

JavaScript solução

correspondente/original

class LFUCache {
    constructor(capacity) {
        this.capacity = capacity;
        this.minf = 0;
        this.cache = new Map();
        this.frequencies = new Map();
    }

    insert(key, frequency, value) {
        if (!this.frequencies.has(frequency)) {
            this.frequencies.set(frequency, new Set());
        }
        this.frequencies.get(frequency).add(key);
        this.cache.set(key, { frequency, value });
    }

    get(key) {
        if (!this.cache.has(key)) return -1;
        let { frequency, value } = this.cache.get(key);
        this.frequencies.get(frequency).delete(key);
        if (this.frequencies.get(frequency).size === 0) {
            this.frequencies.delete(frequency);
            if (this.minf === frequency) this.minf++;
        }
        this.insert(key, frequency + 1, value);
        return value;
    }

    put(key, value) {
        if (this.capacity <= 0) return;
        if (this.cache.has(key)) {
            this.cache.get(key).value = value;
            this.get(key);
            return;
        }
        if (this.cache.size === this.capacity) {
            let oldest = Array.from(this.frequencies.get(this.minf))[0];
            this.cache.delete(oldest);
            this.frequencies.get(this.minf).delete(oldest);
            if (this.frequencies.get(this.minf).size === 0) this.frequencies.delete(this.minf);
        }
        this.minf = 1;
        this.insert(key, 1, value);
    }
}

Python solução

correspondente/original

from collections import defaultdict, OrderedDict

class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.minf = 0
        self.cache = {}
        self.frequencies = defaultdict(OrderedDict)

    def insert(self, key: int, frequency: int, value: int):
        self.frequencies[frequency][key] = value
        self.cache[key] = (frequency, self.frequencies[frequency])

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        frequency, freq_map = self.cache[key]
        value = freq_map.pop(key)
        if not freq_map:
            del self.frequencies[frequency]
            if self.minf == frequency: self.minf += 1
        self.insert(key, frequency + 1, value)
        return value

    def put(self, key: int, value: int) -> None:
        if self.capacity <= 0: return
        if key in self.cache:
            self.cache[key][1][key] = value
            self.get(key)
            return
        if len(self.cache) == self.capacity:
            del_key, _ = self.frequencies[self.minf].popitem(last=False)
            del self.cache[del_key]
        self.minf = 1
        self.insert(key, 1, value)

Go solução

correspondente/original

package main
type LFUCache struct {
    cache       map[int][2]int
    frequencies map[int][]int
    capacity    int
    minf        int
}
func Constructor(capacity int) LFUCache {
    return LFUCache{
        cache:       make(map[int][2]int),
        frequencies: make(map[int][]int),
        capacity:    capacity,
    }
}
func (c *LFUCache) insert(key, freq, value int) {
    c.frequencies[freq] = append(c.frequencies[freq], key)
    c.cache[key] = [2]int{freq, value}
}
func (c *LFUCache) Get(key int) int {
    if val, found := c.cache[key]; !found {
        return -1
    } else {
        freq, value := val[0], val[1]
        c.frequencies[freq] = removeKey(c.frequencies[freq], key)
        if len(c.frequencies[freq]) == 0 {
            delete(c.frequencies, freq)
            if c.minf == freq {
                c.minf++
            }
        }
        c.insert(key, freq+1, value)
        return value
    }
}
func (c *LFUCache) Put(key int, value int) {
    if c.capacity <= 0 {
        return
    }
    if val, found := c.cache[key]; found {
        c.cache[key] = [2]int{val[0], value}
        c.Get(key)
        return
    }
    if len(c.cache) == c.capacity {
        minFreqKeys := c.frequencies[c.minf]
        delete(c.cache, minFreqKeys[0])
        c.frequencies[c.minf] = minFreqKeys[1:]
        if len(c.frequencies[c.minf]) == 0 {
            delete(c.frequencies, c.minf)
        }
    }
    c.minf = 1
    c.insert(key, 1, value)
}
func removeKey(slice []int, key int) []int {
    for i, v := range slice {
        if v == key {
            return append(slice[:i], slice[i+1:]...)
        }
    }
    return slice
}

Algorithm

insert(int key, int frequency, int value):

Вставить пару частота-значение в cache с заданным ключом.

Получить LinkedHashSet, соответствующий данной частоте (по умолчанию пустой Set), и вставить в него ключ.

int get(int key):

Если ключа нет в кеше, вернуть -1.

Получить частоту и значение из кеша.

Удалить ключ из LinkedHashSet, связанного с частотой.

Если minf == frequency и LinkedHashSet пуст, увеличить minf на 1 и удалить запись частоты из frequencies.

Вызвать insert(key, frequency + 1, value).

Вернуть значение.

void put(int key, int value):

Если capacity <= 0, выйти.

Если ключ существует, обновить значение и вызвать get(key).

Если размер кеша равен capacity, удалить первый element из LinkedHashSet, связанного с minf, и из кеша.

Установить minf в 1.

Вызвать insert(key, 1, value).

😎

Vacancies for this task

vagas ativas with overlapping task tags are mostradas.

Todas as vagas

Ainda não há vagas ativas.