马小混

leetcode(146) - LRU缓存机制

2019/04/29

LRU缓存机制

一、题目描述

1、English版本

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.

Follow up:
Could you do both operations in O(1) time complexity?

Example: 

LRUCache cache = new LRUCache( 2 /* capacity */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

2、 中文版

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:

你是否可以在 O(1) 时间复杂度内完成这两种操作？

示例:

LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得密钥 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得密钥 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4

二、ruby方案

采用双向链表作为LRU索引表，采用哈希表作为数据表。

当容量满时，从索引表移除第一项，再从哈希表删除元素。每次插入元素或获取元素时，都要从索引表中删除索引，再重新插入索引。

由于是双向链表，并且已经保存了索引的节点，因此对索引的操作是o(1)，而存储数据的hash表也是o(1)，所以理论上整体操作是o(1)。

LRU

如图，LRU是最近最少使用，所以使用双向链表，将最近最少使用的数据放在表头移除元素时可以实现O(1)；

而读取则使用hash作为数据表，读取之后移除该元素；

代码如下：

# 采用双向链表作为LRU索引表，采用哈希表作为数据表
# 当容量满时，从索引表移除第一项，再从哈希表删除元素。
# 每次插入元素或获取元素时，都要从索引表中删除索引，再重新插入索引。
# 由于是双向链表，并且已经保存了索引的节点，因此对索引的操作是o(1)，而存储数据的hash表也是o(1)，所以理论上整体操作是o(1)。

class Node
   def initialize(key, val)
     @val = val
     @key = key
     @pre = nil
     @next = nil
   end
end

class LRUCache

=begin
    :type capacity: Integer
=end
    def initialize(capacity)
      @capacity = capacity
      @node_map = {}
      @head = nil
      @tail = nil
    end


=begin
    :type key: Integer
    :rtype: Integer
=end
    def get(key)
      if @node_map.keys.include? key
        return -1
      end
      
      node = @node_map[key]
      if !node.next.nil?
        if node.pre.nil?
          @head = @head.next
          @head.pre = nil
        else
          node.pre.next = node.next
          node.next.pre = node.pre
        end
        @tail.next = node
        node.pre = @tail
        node.next = nil
        @tail = node
      end
      
      node.val
    end


=begin
    :type key: Integer
    :type value: Integer
    :rtype: Void
=end
    def put(key, value)
      if @node_map.keys.include? key
        @node_map[key].val = value
        get(key)
        return
      end
      
      if @node_map.keys.size == @capacity
        node = @node_map[head.key]
        @node_map.delete(head.key)
        @node_map[key] = value
        node.val = value
        node.key = key
        get(key)
      else
        node = Node.new(key, value)
        @node_map[key] = node
        if @head.nil?
          @head = node
          @tail = node
        else
          @tail.next = node
          node.pre = @tail
          @tail = node
        end
      end
    end
end

# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache.new(capacity)
# param_1 = obj.get(key)
# obj.put(key, value)


Show Disqus Comments

Post Directory