146. LRU Cache
Реализуйте класс LRUCache:
LRUCache(int capacity) - инициализирует LRU-кэш с положительным размером capacity.
int get(int key) - returns значение по ключу, если ключ существует, в противном случае returns -1.
void put(int key, int value) - обновляет значение по ключу, если ключ существует. В противном случае добавляет пару ключ-значение в кэш. Если количество ключей превышает установленную емкость после этой операции, удаляет наименее недавно использованный ключ.
Функции get и put должны выполняться за среднее время O(1).
Beispiel:
Input
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
Output
[null, null, null, 1, null, -1, null, -1, 3, 4]
C# Lösung
zugeordnet/originalpublic class Node {
public int key { get; set; }
public int value { get; set; }
public Node next { get; set; }
public Node prev { get; set; }
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public class LRUCache {
private int capacity;
private Dictionary<int, Node> dic;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
dic = new Dictionary<int, Node>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public int Get(int key) {
if (!dic.ContainsKey(key)) {
return -1;
}
Node node = dic[key];
Remove(node);
Add(node);
return node.value;
}
public void Put(int key, int value) {
if (dic.ContainsKey(key)) {
Node oldNode = dic[key];
Remove(oldNode);
}
Node node = new Node(key, value);
dic[key] = node;
Add(node);
if (dic.Count > capacity) {
Node nodeToDelete = head.next;
Remove(nodeToDelete);
dic.Remove(nodeToDelete.key);
}
}
private void Add(Node node) {
Node previousEnd = tail.prev;
previousEnd.next = node;
node.prev = previousEnd;
node.next = tail;
tail.prev = node;
}
private void Remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}C++ Lösung
Auto-Entwurf, vor dem Einreichen prüfen#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 Node {
public int key { get; set; }
public int value { get; set; }
public Node next { get; set; }
public Node prev { get; set; }
public Node(int key, int value) {
this.key = key;
this.value = value;
}
}
public class LRUCache {
private int capacity;
private unordered_map<int, Node> dic;
private Node head;
private Node tail;
public LRUCache(int capacity) {
this.capacity = capacity;
dic = new unordered_map<int, Node>();
head = new Node(-1, -1);
tail = new Node(-1, -1);
head.next = tail;
tail.prev = head;
}
public int Get(int key) {
if (!dic.count(key)) {
return -1;
}
Node node = dic[key];
Remove(node);
Add(node);
return node.value;
}
public void Put(int key, int value) {
if (dic.count(key)) {
Node oldNode = dic[key];
Remove(oldNode);
}
Node node = new Node(key, value);
dic[key] = node;
Add(node);
if (dic.size() > capacity) {
Node nodeToDelete = head.next;
Remove(nodeToDelete);
dic.Remove(nodeToDelete.key);
}
}
private void Add(Node node) {
Node previousEnd = tail.prev;
previousEnd.next = node;
node.prev = previousEnd;
node.next = tail;
tail.prev = node;
}
private void Remove(Node node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}Java Lösung
zugeordnet/originalclass ListNode {
int key;
int val;
ListNode next;
ListNode prev;
public ListNode(int key, int val) {
this.key = key;
this.val = val;
}
}
class LRUCache {
int capacity;
Map<Integer, ListNode> dic;
ListNode head;
ListNode tail;
public LRUCache(int capacity) {
this.capacity = capacity;
dic = new HashMap<>();
head = new ListNode(-1, -1);
tail = new ListNode(-1, -1);
head.next = tail;
tail.prev = head;
}
public int get(int key) {
if (!dic.containsKey(key)) {
return -1;
}
ListNode node = dic.get(key);
remove(node);
add(node);
return node.val;
}
public void put(int key, int value) {
if (dic.containsKey(key)) {
ListNode oldNode = dic.get(key);
remove(oldNode);
}
ListNode node = new ListNode(key, value);
dic.put(key, node);
add(node);
if (dic.size() > capacity) {
ListNode nodeToDelete = head.next;
remove(nodeToDelete);
dic.remove(nodeToDelete.key);
}
}
public void add(ListNode node) {
ListNode previousEnd = tail.prev;
previousEnd.next = node;
node.prev = previousEnd;
node.next = tail;
tail.prev = node;
}
public void remove(ListNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
}JavaScript Lösung
zugeordnet/originalclass Node {
constructor(key, value) {
this.key = key;
this.value = value;
this.next = null;
this.prev = null;
}
}
class LRUCache {
constructor(capacity) {
this.capacity = capacity;
this.dic = new Map();
this.head = new Node(-1, -1);
this.tail = new Node(-1, -1);
this.head.next = this.tail;
this.tail.prev = this.head;
}
get(key) {
if (!this.dic.has(key)) {
return -1;
}
let node = this.dic.get(key);
this.remove(node);
this.add(node);
return node.value;
}
put(key, value) {
if (this.dic.has(key)) {
this.remove(this.dic.get(key));
}
let node = new Node(key, value);
this.add(node);
this.dic.set(key, node);
if (this.dic.size > this.capacity) {
let nodeToDelete = this.head.next;
this.remove(nodeToDelete);
this.dic.delete(nodeToDelete.key);
}
}
add(node) {
let pre = this.tail.prev;
pre.next = node;
node.prev = pre;
node.next = this.tail;
this.tail.prev = node;
}
remove(node) {
let pre = node.prev;
let nxt = node.next;
pre.next = nxt;
nxt.prev = pre;
}
}Python Lösung
zugeordnet/originalclass ListNode:
def __init__(self, key, val):
self.key = key
self.val = val
self.next = None
self.prev = None
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.dic = {}
self.head = ListNode(-1, -1)
self.tail = ListNode(-1, -1)
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key: int) -> int:
if key not in self.dic:
return -1
node = self.dic[key]
self.remove(node)
self.add(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.dic:
old_node = self.dic[key]
self.remove(old_node)
node = ListNode(key, value)
self.dic[key] = node
self.add(node)
if len(self.dic) > self.capacity:
node_to_delete = self.head.next
self.remove(node_to_delete)
del self.dic[node_to_delete.key]
def add(self, node):
previous_end = self.tail.prev
previous_end.next = node
node.prev = previous_end
node.next = self.tail
self.tail.prev = node
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prevGo Lösung
zugeordnet/originaltype LRUCache struct {
Cap int
L *list.List
M map[int]*list.Element
}
type Node struct {
Key int
Value int
}
func Constructor(capacity int) LRUCache {
return LRUCache{
Cap: capacity,
L: list.New(),
M: make(map[int]*list.Element, capacity),
}
}
func (this *LRUCache) Get(key int) int {
if node, ok := this.M[key]; ok {
val := node.Value.(*Node).Value
this.L.MoveToBack(node)
return val
}
return -1
}
func (this *LRUCache) Put(key int, value int) {
if node, ok := this.M[key]; ok {
this.L.MoveToBack(node)
node.Value.(*Node).Value = value
return
}
node := &Node{
Key: key,
Value: value,
}
ptr := this.L.PushBack(node)
this.M[key] = ptr
if this.L.Len() > this.Cap {
idx := this.L.Front().Value.(*Node).Key
delete(this.M, idx)
this.L.Remove(this.L.Front())
}
}Algorithm
1️⃣
Метод добавления узла в конец связного списка (add):
Получите текущий узел в конце списка, это "реальный" хвост: tail.prev, обозначим его как previousEnd.
Вставьте node после previousEnd, установив
previousEnd.next
= node.
Настройте указатели узла: node.prev = previousEnd и
node.next
= tail.
Обновите tail.prev = node, делая node новым "реальным" хвостом списка.
2️⃣
Метод удаления узла из связного списка (remove):
Узел node должен быть удален из списка. Для этого определите узлы nextNode =
node.next
и prevNode = node.prev.
Чтобы удалить node, переназначьте
prevNode.next
= nextNode и nextNode.prev = prevNode, эффективно исключая node из списка.
Это превратит, наBeispiel, последовательность A <-> B <-> C в A <-> C, где prevNode = A и nextNode = C.
3️⃣
Методы get и put:
get(int key): Проверьте, существует ли ключ в хэш-карте. Если нет, return -1. Иначе, получите узел, связанный с ключом, переместите его в конец списка с помощью remove(node) и add(node). return node.val.
put(int key, int value): Если ключ уже существует, find соответствующий узел и удалите его методом remove. Создайте новый узел с key и value, добавьте его в хэш-карту и в конец списка методом add(node). Если размер кэша превышает установленную емкость после добавления, удалите самый редко используемый узел (который находится в голове списка после фиктивного узла head), затем удалите соответствующий ключ из хэш-карты.
😎
Stellen zu dieser Aufgabe
aktive Stellen with overlapping task tags are angezeigt.