146. LRU Cache
設計一個遵循最近最少使用（LRU）緩存約束的數據結構。
實現 LRUCache 類：LRUCache(int capacity) 初始化 LRU 緩存，具有正整數容量。
int get(int key) 如果鍵存在，則返回鍵的值，否則返回 -1。
void put(int key, int value) 更新鍵的值（如果鍵存在）。否則，將鍵值對添加到緩存中。如果此操作導致鍵的數量超過容量，則驅逐最近最少使用的鍵。
函數 get 和 put 必須以 O(1) 平均時間複雜度運行。
範例 :
輸入:
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
輸出:
[null, null, null, 1, null, -1, null, -1, 3, 4]
說明:
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); 緩存是 {1=1}
lRUCache.put(2, 2); 緩存是 {1=1, 2=2}
lRUCache.get(1); 返回 1
lRUCache.put(3, 3); 最近最少使用的鍵是 2，驅逐鍵 2，緩存是 {1=1, 3=3}
lRUCache.get(2); 返回 -1（未找到）
lRUCache.put(4, 4); 最近最少使用的鍵是 1，驅逐鍵 1，緩存是 {4=4, 3=3}
lRUCache.get(1); 返回 -1（未找到）
lRUCache.get(3); 返回 3
lRUCache.get(4); 返回 4
Python
from collections import OrderedDict
class LRUCache:
def __init__(self, capacity: int):
self.capacity = capacity
self.cache = OrderedDict()
def get(self, key: int) -> int:
if key not in self.cache:
return -1
else:
self.cache.move_to_end(key) # Mark as recently used
return self.cache[key]
def put(self, key: int, value: int) -> None:
if key in self.cache:
self.cache.move_to_end(key) # Mark as recently used
self.cache[key] = value
if len(self.cache) > self.capacity:
self.cache.popitem(last=False) # Remove least recently used item
78.28MB, 549ms
C++
#include <unordered_map>
#include <list>
using namespace std;
class LRUCache {
public:
LRUCache(int capacity) : capacity(capacity) {}
int get(int key) {
auto it = cache.find(key);
if (it == cache.end()) {
return -1; // Key not found
} else {
// Move the accessed key to the front of the usage list
usage.splice(usage.begin(), usage, it->second.second);
return it->second.first;
}
}
void put(int key, int value) {
auto it = cache.find(key);
if (it != cache.end()) {
// Key already exists, update value and move to front of usage list
usage.splice(usage.begin(), usage, it->second.second);
it->second.first = value;
} else {
// Key does not exist, insert new key-value pair
if (cache.size() == capacity) {
// Cache is full, remove the least recently used key
cache.erase(usage.back());
usage.pop_back();
}
usage.push_front(key);
cache[key] = {value, usage.begin()};
}
}
private:
int capacity;
list<int> usage; // List to track the order of usage
unordered_map<int, pair<int, list<int>::iterator>> cache; // Map of key to (value, iterator)
};
168.52MB, 312ms
Javascript
/**
* @param {number} capacity
*/
var LRUCache = function(capacity) {
this.capacity = capacity;
this.cache = new Map();
};
/**
* @param {number} key
* @return {number}
*/
LRUCache.prototype.get = function(key) {
if (!this.cache.has(key)) {
return -1;
}
// Move the accessed key to the end to show that it was recently used
let value = this.cache.get(key);
this.cache.delete(key);
this.cache.set(key, value);
return value;
};
/**
* @param {number} key
* @param {number} value
* @return {void}
*/
LRUCache.prototype.put = function(key, value) {
if (this.cache.has(key)) {
// Remove the old value
this.cache.delete(key);
}
// If the cache exceeds capacity, remove the first key-value pair
if (this.cache.size === this.capacity) {
this.cache.delete(this.cache.keys().next().value);
}
// Add the new key-value pair
this.cache.set(key, value);
};
105.86MB, 496ms
