146. LRU Cache

source: https://leetcode.com/problems/lru-cache/

Question

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 size capacity. int get(int key) Return the value of the key if the key exists, otherwise return -1. void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key. The functions get and put must each run in O(1) average time complexity.

初想法

这题的难点主要在于如何以更新顺序对数据排序，同时完成其对于hashmap的映射。

第一想法是基于队列去做，每次get/put都会更新队列的队首，在put的时候再多检查一次capacity是否超过，然后一个hashmap存储key和引用地址。

这个想法比较直观和粗暴，代码如下：

interface LinkedListNode {
  value: number;
  key: number;
}

class LRUCache {
  private capacity: number;
  private cache: Record<number, LinkedListNode>;
  private queue: LinkedListNode[];

  constructor(capacity: number) {
    this.capacity = capacity;
    this.cache = {};
    this.queue = [];
  }

  private updateQueue(node: LinkedListNode) {
    const index = this.queue.findIndex(item => item === node);
    this.queue.splice(index, 1);
    this.queue.unshift(node);
  }

  get(key: number): number {
    const node = this.cache[key];
    if (!node) return -1;
    this.updateQueue(node);
    return node.value;
  }

  put(key: number, value: number): void {
    if (this.cache[key]) {
      this.cache[key].value = value;
      return this.updateQueue(this.cache[key]);
    }
    const node = { value, key };
    this.cache[key] = node;
    this.queue.unshift(node);
    if (this.queue.length > this.capacity) this.cache[this.queue.pop().key] = undefined;
  }
}

但是这个方法最大的问题是要去寻找index然后做操作，会将时间复杂度拖累到O(n).

双向链表

如果用双向链表的方式，目的其实是为了省去O(n)的find操作，但是双向链表本身其实是不能提供这样的能力的。

这道题比较特殊的地方是，要操作的节点是头部和尾部节点，可以用dummy head和dummy tail的技巧，避免掉find操作。

ts代码如下：

interface IListNode {
    prev?: IListNode;
    key?: number;
    next?: IListNode;
    value?: number;
}

class LRUCache {
    private capacity: number;
    private cache: Record<number, IListNode>;
    private head: IListNode;
    private tail: IListNode;
    private size: number;

    constructor(capacity: number) {
        this.capacity = capacity;
        this.size = 0;
        this.cache = {};
        this.head = {};
        this.tail = {};
        this.head.next = this.tail;
        this.tail.prev = this.head;
    }

    
    private remove(node: IListNode) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
        this.size -= 1;
        delete this.cache[node.key];
    }

    private addToHead(node: IListNode) {
        const head = this.head.next;
        node.next = head;
        node.prev = this.head;
        this.head.next = node;
        head.prev = node;
        this.size += 1;
        this.cache[node.key] = node;
    }

    get(key: number): number {
        const node = this.cache[key];
        if (!node) return -1;
        this.remove(node);
        this.addToHead(node);
        return node.value;
    }

    put(key: number, value: number): void {
        const node = this.cache[key];
        if (node) {
            node.value = value;
            this.remove(node);
            this.addToHead(node);
        } else {
            const newNode = { value, key };
            this.cache[key] = newNode;
            this.addToHead(newNode);
            if (this.size > this.capacity) {
                this.remove(this.tail.prev);
            }
        }
    }
}

rust代码如下:

use std::cell::RefCell;
use std::collections::HashMap;
use std::rc::Rc;

#[derive(Debug)]
struct LinkedNode {
  key: i32,
  value: i32,
  prev: Option<Rc<RefCell<LinkedNode>>>,
  next: Option<Rc<RefCell<LinkedNode>>>,
}

#[derive(Debug)]
struct LinkedList {
  size: i32,
  head: Option<Rc<RefCell<LinkedNode>>>,
  tail: Option<Rc<RefCell<LinkedNode>>>,
}

fn wrap<T>(node: T) -> Option<Rc<RefCell<T>>> {
  return Some(Rc::from(RefCell::from(node)));
}

impl LinkedList {
  fn new() -> Self {
    let head = wrap(LinkedNode {
      key: -1,
      value: -1,
      prev: None,
      next: None,
    });
    let tail = wrap(LinkedNode {
      key: -1,
      value: -1,
      prev: None,
      next: None,
    });
    head.clone().unwrap().borrow_mut().next = tail.clone();
    tail.clone().unwrap().borrow_mut().prev = head.clone();
    LinkedList {
      size: 0,
      head,
      tail,
    }
  }

  fn add_to_head(&mut self, node: Rc<RefCell<LinkedNode>>) {
    node.borrow_mut().prev = self.head.clone();
    node.borrow_mut().next = self.head.clone().unwrap().borrow().next.clone();
    self
      .head
      .clone()
      .unwrap()
      .borrow_mut()
      .next
      .clone()
      .unwrap()
      .borrow_mut()
      .prev = Some(node.clone());
    self.head.clone().unwrap().borrow_mut().next = Some(node.clone());
    self.size += 1;
  }

  fn remove_node(&mut self, node: Rc<RefCell<LinkedNode>>) {
    node
      .clone()
      .borrow()
      .prev
      .clone()
      .unwrap()
      .borrow_mut()
      .next = node.clone().borrow().next.clone();
    node
      .clone()
      .borrow()
      .next
      .clone()
      .unwrap()
      .borrow_mut()
      .prev = node.clone().borrow().prev.clone();
    self.size -= 1;
  }

  fn move_to_head(&mut self, node: Rc<RefCell<LinkedNode>>) {
    self.remove_node(node.clone());
    self.add_to_head(node.clone());
  }

  fn remove_tail(&mut self) -> Rc<RefCell<LinkedNode>> {
    let last = self.tail.clone().unwrap().borrow().prev.clone().unwrap();
    self.remove_node(last.clone());
    last.clone()
  }
}

#[derive(Debug)]
pub struct LRUCache {
  list: LinkedList,
  capacity: i32,
  cache: HashMap<i32, Option<Rc<RefCell<LinkedNode>>>>,
}

/**
 * `&self` means the method takes an immutable reference.
 * If you need a mutable reference, change it to `&mut self` instead.
 */
impl LRUCache {
  fn new(capacity: i32) -> Self {
    LRUCache {
      capacity: capacity,
      cache: HashMap::new(),
      list: LinkedList::new(),
    }
  }

  fn get(&mut self, key: i32) -> i32 {
    let v = self.cache.get(&key);
    if !v.is_none() {
      if let Some(node) = v.unwrap() {
        self.list.move_to_head(node.clone());
        return node.clone().borrow().value;
      }
    }
    return -1;
  }

  fn put(&mut self, key: i32, value: i32) {
    let v = self.cache.get(&key);
    if !v.is_none() {
      if let Some(node) = v.unwrap() {
        node.clone().borrow_mut().value = value;
        self.list.move_to_head(node.clone());
        return;
      }
    }
    let node = wrap(LinkedNode {
      key,
      value,
      prev: None,
      next: None,
    });
    self.list.add_to_head(node.clone().unwrap());
    self.cache.insert(key, node.clone());
    if self.list.size > self.capacity {
      let removed_node = self.list.remove_tail();
      self.cache.remove(&removed_node.clone().borrow().key);
    }
  }
}

总结

单纯的数据结构改变有时候其实不能达到我们的目的，但是配合一些技巧，可以达到优化的目的。