146. LRU 缓存机制

入选理由

暂无

题目地址

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

前置知识

暂无

题目描述

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：

LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

进阶：你是否可以在 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 作废，缓存是 {1=1, 3=3}
lRUCache.get(2);    // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1);    // 返回 -1 (未找到)
lRUCache.get(3);    // 返回 3
lRUCache.get(4);    // 返回 4

class Dlist:
    def __init__(self, val=None, key=None):
        self.val = val
        self.key = key
        self.pre = None
        self.next = None

class LRUCache:

    def __init__(self, capacity: int):
        self.map = {}
        self.capacity = capacity
        self.head = Dlist()
        self.tail = Dlist()
        self.head.next = self.tail
        self.tail.pre = self.head

    def move2tail(self, n):
        # if already at the end, take no action
        if n == self.tail.pre:
            return
        # find the node
        pre_n = n.pre
        next_n = n.next
        pre_tail = self.tail.pre
        # take out the node
        pre_n.next = next_n
        next_n.pre = pre_n
        # move to the end
        pre_tail.next = n
        n.pre = pre_tail
        n.next = self.tail
        self.tail.pre = n

    def add2tail(self, n):
        pre_tail = self.tail.pre
        pre_tail.next = n
        n.pre = pre_tail
        self.tail.pre = n
        n.next = self.tail

    def delete_head(self):
        self.top = self.head.next
        self.top_next = self.top.next
        # delete the top node
        self.head.next = self.top_next
        self.top_next.pre = self.head
        # set pointer to None
        self.top.pre = None
        self.top.next = None
        del self.map[self.top.key]

    def get(self, key: int) -> int:
        n = self.map.get(key, -1)
        if n == -1:
            return -1
        self.move2tail(n)
        return n.val

    def put(self, key: int, value: int) -> None:
        if key in self.map:
            self.map[key].val = value
            self.move2tail(self.map[key])
        else:
            if len(self.map) == self.capacity:
                self.delete_head()
            self.map[key] = Dlist(val=value, key=key)
            self.add2tail(self.map[key])

dict to store (key, double_linked_list_node)

time O(1) space O(capacity)

思路

LRU 要实现 get 和 set 操作复杂度为 O(1)，可以借助哈希表和双链表数据结构
LRU: 最近最少使用
- 即每次访问元素后，需要将其放到最前面
- 容量满了，添加的元素替换掉最后一个元素
哈希表存放的是节点，通过节点可以获取前驱和后继指针
通过哈希表实现 get 操作时间复杂度为 O(1) 的
通过双链表实现 push 操作为 O(1) 时间复杂度

代码

class DoubleListNode {
  constructor(key, val, next, prev) {
    this.key = key;
    this.val = val;
    this.next = next === undefined ? null : next;
    this.prev = prev === undefined ? null : prev;
  }
}

/**
 * @param {number} capacity
 */
var LRUCache = function (capacity) {
  this.capacity = capacity;
  this.hashMap = new Map();
  this.head = new DoubleListNode();
  this.tail = new DoubleListNode();
};

/**
 * @param {number} key
 * @return {number}
 */
LRUCache.prototype.get = function (key) {
  if (this.capacity === 1) {
    return this.hashMap.has(key) ? this.hashMap.get(key).val : -1;
  }
  if (this.hashMap.has(key)) {
    var currentNode = this.hashMap.get(key);
    var nextNode = currentNode.next;
    var prevNode = currentNode.prev;

    if (nextNode) {
      prevNode.next = nextNode;
      nextNode.prev = prevNode;
    } else {
      prevNode.next = null;
    }

    var headNextNode = this.head.next;
    currentNode.next = headNextNode;
    currentNode.prev = this.head;

    if (headNextNode) {
      headNextNode.prev = currentNode;
    }
    this.head.next = currentNode;

    var p2 = this.head.next;
    while (p2) {
      if (!p2.next) {
        this.tail.next = p2;
      }
      p2 = p2.next;
    }

    return this.hashMap.get(key).val;
  }
  return -1;
};

/**
 * @param {number} key
 * @param {number} value
 * @return {void}
 */
LRUCache.prototype.put = function (key, value) {
  // 容量为1
  if (this.capacity === 1) {
    this.hashMap.clear();
    this.hashMap.set(key, new DoubleListNode(key, value));
    return null;
  }
  // currentNode
  var currentNode = new DoubleListNode(key, value);

  if (this.capacity > this.hashMap.size) {
    if (this.hashMap.has(key)) {
      var temp = this.hashMap.get(key);
      temp.val = value;
      console.log("value:", key, value, temp.val, temp.key);
      this.hashMap.set(key, temp);
      this.get(key);
      return null;
    }
    // 容量不满
    // head <-> a <-> b
    var headNext = this.head.next;

    currentNode.next = headNext;
    if (headNext) {
      headNext.prev = currentNode;
    }

    this.head.next = currentNode;
    currentNode.prev = this.head;

    if (!this.tail.next) {
      this.tail.next = currentNode;
    }
    this.hashMap.set(key, currentNode);
  } else {
    if (this.hashMap.has(key)) {
      var temp = this.hashMap.get(key);
      temp.val = value;
      console.log("value:", key, value, temp.val, temp.key);
      this.hashMap.set(key, temp);
      this.get(key);
      return null;
    }

    // 容量满了，删除最后一个节点
    var lastNode = this.tail.next;

    const prevNode = lastNode.prev;
    prevNode.next = null;

    this.hashMap.delete(lastNode.key);

    this.tail.next = prevNode;

    // 头部插入
    var nextHeadNode = this.head.next;
    currentNode.next = nextHeadNode;

    if (nextHeadNode) {
      nextHeadNode.prev = currentNode;
    }
    currentNode.prev = this.head;
    this.head.next = currentNode;
    this.hashMap.set(key, currentNode);
  }
};

复杂度分析

时间复杂度: O(1)
空间复杂度: O(N)

/**

@param {number} capacity */ var LRUCache = function(capacity) { this.capacity = capacity; this.cache = new Map(); this.head = new ListNode(-1,-1); this.tail = new ListNode(-1,-1); this.head.next = this.tail; this.tail.prev = this.head; };

/**

@param {number} key
@return {number} */ LRUCache.prototype.get = function(key) { if(!this.cache.has(key)) return -1; const node = this.cache.get(key); this.remove(node); this.add(node); return node.val; };

/**

@param {number} key
@param {number} value
@return {void} */ LRUCache.prototype.put = function(key, value) { if(this.cache.has(key)) { const node = this.cache.get(key); this.remove(node); } const newNode = new ListNode(key, value); this.cache.set(key, newNode); this.add(newNode);

if(this.cache.size > this.capacity) { const nodeToDelete = this.head.next; this.remove(nodeToDelete); this.cache.delete(nodeToDelete.key) } };

/**
@param {ListNode} node
@return {void} */

LRUCache.prototype.add = function (node) { const nodeBeforeTail = this.tail.prev; nodeBeforeTail.next = node; node.prev = nodeBeforeTail; node.next = this.tail; this.tail.prev = node; }

/**

@param {ListNode} node
@return {void} */ LRUCache.prototype.remove = function(node) { node.prev.next = node.next; node.next.prev = node.prev; }

class ListNode { constructor (key,val) { this.key = key; this.val = val; this.next = null; this.prev = null; } }

class Node{
public:
    int key, value;
    Node *pre, *next;
    Node(int k=0, int v=0):key(k), value(v){}
};

class LRUCache {
private:
    int capacity;
    Node *dummy;
    unordered_map<int, Node*> key_to_node;
    // 删除一个节点（抽出一本书）
    void remove(Node *x) {
        x->pre->next = x->next;
        x->next->pre = x->pre;
    }

    // 在链表头添加一个节点（把一本书放在最上面）
    void push_front(Node *x) {
        x->pre = dummy;
        x->next = dummy->next;
        x->pre->next = x;
        x->next->pre = x;
    }

    Node *get_node(int key) {
        auto it = key_to_node.find(key);
        if (it == key_to_node.end()) // 没有这本书
            return nullptr;
        auto node = it->second; // 有这本书
        remove(node); // 把这本书抽出来
        push_front(node); // 放在最上面
        return node;
    }

public:

    LRUCache(int capacity): capacity(capacity), dummy(new Node()) {
        dummy->pre = dummy;
        dummy->next = dummy;
    }

    int get(int key) {
        auto node = get_node(key);
        return node ? node->value : -1;
    }

    void put(int key, int value) {
        auto node = get_node(key);
        if (node) { // 有这本书
            node->value = value; // 更新 value
            return;
        }
        key_to_node[key] = node = new Node(key, value); // 新书
        push_front(node); // 放在最上面
        if (key_to_node.size() > capacity) { // 书太多了
            auto back_node = dummy->prev;
            key_to_node.erase(back_node->key);
            remove(back_node); // 去掉最后一本书
            delete back_node; // 释放内存
        }
    }

};

class LRUCache { private: struct ListNode { int key; int val; ListNode next; ListNode last; ListNode() : key(0), val(0), next(nullptr), last(nullptr) {} ListNode(int _key, int _value) : key(_key), val(_value), next(nullptr), last(nullptr) {} };

ListNode* dummy_head;
ListNode* dummy_tail;

unordered_map<int, ListNode*> datamap;
int max_size;
int cur_size;

public:

LRUCache(int capacity) {
    max_size = capacity;

    dummy_head = new ListNode();
    dummy_tail = new ListNode();

    dummy_head->next = dummy_tail;
    dummy_tail->last = dummy_head;
}

int get(int key) {
    auto it = datamap.find(key);
    if (it != datamap.end()) {
        // 如果关键字 key 存在于缓存中
        // 移动至头部
        ListNode* cur_node = datamap[key];
        moveToHead(cur_node);
        // 则返回关键字的值
        return cur_node->val;
    }
    else {
        return -1;
    }
}

void put(int key, int value) {
    auto it = datamap.find(key);
    if (it != datamap.end()) {
        // 如果关键字 key 已经存在，则变更其数据值 value
        datamap[key]->val = value;
        // 移动至头部
        moveToHead(datamap[key]);
    }
    else // 如果不存在，则向缓存中插入该组 key-value
    {
        // 创建新节点
        ListNode* node = new ListNode(key, value);

        // 头部插入
        insertToHead(node);
        // 保存哈希
        datamap[key] = node;

        cur_size++;
        if (cur_size > max_size) {
            // 如果插入操作导致关键字数量超过 capacity ，则应该 逐出
            // 最久未使用的关键字。 删除末尾节点
            ListNode* tail_node = removeTail();
            // 删除哈希
            datamap.erase(tail_node->key);
            cur_size--;
        }
    }
}

void moveToHead(ListNode* node) {
    ListNode* temp = dummy_head->next;
    ListNode* cur_last = node->last;
    ListNode* cur_next = node->next;

    node->next = temp;
    cur_next->last = cur_last;
    cur_last->next = cur_next;
    node->last = dummy_head;
    temp->last = node;
    dummy_head->next = node;
}

void insertToHead(ListNode* node) {
    ListNode* temp = dummy_head->next;
    node->next = temp;
    temp->last = node;
    dummy_head->next = node;
    node->last = dummy_head;
}

ListNode* removeTail() {
    ListNode* tail_node = dummy_tail->last;
    tail_node->last->next = dummy_tail;
    dummy_tail->last = tail_node->last;
    return tail_node;
}

};

from collections import OrderedDict
class LRUCache(OrderedDict):

    def __init__(self, capacity: int):
        self.s = capacity

    def get(self, key: int) -> int:
        if key in self:
            self.move_to_end(key)
            return self[key]
        else:
            return -1

    def put(self, key: int, value: int) -> None:
        if key in self:
            self.move_to_end(key)
        self[key] = value
        if len(self) > self.s:
            self.popitem(last=False)

leetcode-pp / 91alg-13-daily-check

【Day 12 】2024-04-19 - 146. LRU 缓存机制 #12