146. LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache
class:
LRUCache(int capacity)
Initialize the LRU cache with positive sizecapacity
.int get(int key)
Return the value of thekey
if the key exists, otherwise return-1
.void put(int key, int value)
Update the value of thekey
if thekey
exists. Otherwise, add thekey-value
pair to the cache. If the number of keys exceeds thecapacity
from this operation, evict the least recently used key.
Follow up:
Could you do get
and put
in O(1)
time complexity?
Example 1:
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] Explanation LRUCache lRUCache = new LRUCache(2); lRUCache.put(1, 1); // cache is {1=1} lRUCache.put(2, 2); // cache is {1=1, 2=2} lRUCache.get(1); // return 1 lRUCache.put(3, 3); // LRU key was 2, evicts key 2, cache is {1=1, 3=3} lRUCache.get(2); // returns -1 (not found) lRUCache.put(4, 4); // LRU key was 1, evicts key 1, cache is {4=4, 3=3} lRUCache.get(1); // return -1 (not found) lRUCache.get(3); // return 3 lRUCache.get(4); // return 4
Constraints:
1 <= capacity <= 3000
0 <= key <= 3000
0 <= value <= 104
- At most
3 * 104
calls will be made toget
andput
.
Rust Solution
use std::cell::RefCell;
use std::collections::HashMap;
use std::fmt::Debug;
use std::fmt::Error;
use std::fmt::Formatter;
use std::rc::{Rc, Weak};
type NodeRef = Rc<RefCell<Node>>;
type Link = Option<NodeRef>;
#[derive(Debug, Clone)]
struct Element {
key: i32,
val: i32,
}
impl Element {
fn new(key: i32, val: i32) -> Self {
Element { key, val }
}
}
#[derive(Debug)]
struct Node {
element: Element,
prev: Link,
next: Link,
}
impl Node {
fn new(element: Element) -> Self {
Node {
element,
prev: None,
next: None,
}
}
fn into_ref(self) -> NodeRef {
Rc::new(RefCell::new(self))
}
}
#[derive(Default)]
struct List {
head: Link,
tail: Link,
}
impl List {
fn new() -> Self {
List {
head: None,
tail: None,
}
}
fn push_back(&mut self, new_node_ref: NodeRef) {
new_node_ref.borrow_mut().prev = self.tail.clone();
match self.tail.clone() {
None => self.head = Some(new_node_ref.clone()),
Some(last_node_ref) => last_node_ref.borrow_mut().next = Some(new_node_ref.clone()),
}
self.tail = Some(new_node_ref);
}
fn pop_front(&mut self) -> Option<Element> {
self.head.clone().map(|node_ref| {
let mut node = node_ref.borrow_mut();
if let Some(next_node_ref) = node.next.take() {
let mut next_node = next_node_ref.borrow_mut();
next_node.prev = None;
self.head = Some(next_node_ref.clone());
} else {
self.head = None;
self.tail = None;
}
node.element.clone()
})
}
fn unlink_node(&mut self, node_ref: NodeRef) -> Element {
let mut node = node_ref.borrow_mut();
let prev = node.prev.take();
let next = node.next.take();
match prev.clone() {
Some(prev_node_ref) => prev_node_ref.borrow_mut().next = next.clone(),
None => self.head = next.clone(),
}
match next {
Some(next_node_ref) => next_node_ref.borrow_mut().prev = prev,
None => self.tail = prev,
}
node.element.clone()
}
fn iter(&self) -> ListIter {
ListIter::new(self.head.clone(), self.tail.clone())
}
}
impl Debug for List {
fn fmt(&self, f: &mut Formatter<'_>) -> Result<(), Error> {
f.debug_list().entries(self.iter()).finish()
}
}
impl Drop for List {
fn drop(&mut self) {
while self.pop_front().is_some() {}
}
}
struct ListIter {
head: Link,
tail: Link,
}
impl ListIter {
fn new(head: Link, tail: Link) -> Self {
ListIter { head, tail }
}
}
impl Iterator for ListIter {
type Item = Element;
fn next(&mut self) -> Option<Self::Item> {
self.head.clone().map(|node_ref| {
let node = node_ref.borrow();
self.head = node.next.clone();
node.element.clone()
})
}
}
#[derive(Debug)]
struct LRUCache {
hash_map: HashMap<i32, Weak<RefCell<Node>>>,
list: List,
length: usize,
capacity: usize,
}
impl LRUCache {
fn new(capacity: i32) -> Self {
let hash_map: HashMap<i32, Weak<RefCell<Node>>> = HashMap::new();
let list: List = List::new();
let length = 0;
let capacity = capacity as usize;
LRUCache {
hash_map,
list,
length,
capacity,
}
}
fn get(&mut self, key: i32) -> i32 {
if let Some(element) = self.get_element(key) {
element.val
} else {
-1
}
}
fn put(&mut self, key: i32, val: i32) {
if self.put_element(key, val).is_none() {
self.length += 1;
}
if self.length > self.capacity {
self.pop_element();
self.length -= 1;
}
}
fn pop_element(&mut self) -> Option<Element> {
if let Some(element) = self.list.pop_front() {
self.hash_map.remove(&element.key);
Some(element)
} else {
None
}
}
fn put_element(&mut self, key: i32, val: i32) -> Option<Element> {
if let Some(node_ref) = self.get_ref(key) {
let old_element = self.list.unlink_node(node_ref);
let new_element = Element::new(key, val);
let new_node_ref = Node::new(new_element).into_ref();
self.hash_map.insert(key, Rc::downgrade(&new_node_ref));
self.list.push_back(new_node_ref);
Some(old_element)
} else {
let new_element = Element::new(key, val);
let new_node_ref = Node::new(new_element).into_ref();
self.hash_map.insert(key, Rc::downgrade(&new_node_ref));
self.list.push_back(new_node_ref);
None
}
}
fn get_element(&mut self, key: i32) -> Option<Element> {
if let Some(node_ref) = self.get_ref(key) {
let old_element = self.list.unlink_node(node_ref);
let new_element = Element::new(old_element.key, old_element.val);
let new_node_ref = Node::new(new_element).into_ref();
self.hash_map.insert(key, Rc::downgrade(&new_node_ref));
self.list.push_back(new_node_ref);
Some(old_element)
} else {
None
}
}
fn get_ref(&mut self, key: i32) -> Option<NodeRef> {
if let Some(weak) = self.hash_map.remove(&key) {
if let Some(node_ref) = weak.upgrade() {
Some(node_ref)
} else {
None
}
} else {
None
}
}
}
#[test]
fn test() {
let mut obj = LRUCache::new(2);
assert_eq!(obj.get(2), -1);
obj.put(2, 6);
assert_eq!(obj.get(1), -1);
obj.put(1, 5);
obj.put(1, 2);
assert_eq!(obj.get(1), 2);
assert_eq!(obj.get(2), 6);
let mut obj = LRUCache::new(3);
obj.put(1, 1);
obj.put(2, 2);
obj.put(3, 3);
obj.put(4, 4);
assert_eq!(obj.get(4), 4);
assert_eq!(obj.get(3), 3);
assert_eq!(obj.get(2), 2);
assert_eq!(obj.get(1), -1);
obj.put(5, 5);
assert_eq!(obj.get(1), -1);
assert_eq!(obj.get(2), 2);
assert_eq!(obj.get(3), 3);
assert_eq!(obj.get(4), -1);
assert_eq!(obj.get(5), 5);
}
Having problems with this solution? Click here to submit an issue on github.