Description
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
描述
运用你所掌握的数据结构，设计和实现一个 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
思路
- LRU 最近最久未使用页面置换算法
- 最近最久未使用算法要求在替换页面时，替换当前已经在内存的所有页面中，使用时间离现在时间最远的页面.
- 我们使用两种主要的数据结构，字典（哈希表）和双向链表.
- 双向链表的每一个节点有四个值：key：页面号，value:当前页的内容，prev:当前节点的上一个节点，next当前节点的下一个节点
- 字典以链表中的key为键，以每个节点的引用为值.
- 涉及的主要操作有get，和put,为此我们实现两个辅助的内部函数_remove(self,node)和_add(self,node).
- _remove函数输入参数是需要移除的node节点，此函数实现将node节点从双链表中移除，但并不删除node节点本身.
- _add函数输入的参数是node，主要的功能是将node添加到双向链表中.
- get函数:如果当前请求的页面在内存中，则返回页面的值，并且当前页面放到双向链表的尾部（tail节点前面）；如果不在则直接返回-1.
- put函数:如果当前的页面在请求的内存中，将当前节点放到双向链表末尾；如果不在，创建一个新的节点并且放到双向链表末尾（tail节点前面）.
- put函数接下来检查已分配的页面数，如果超过了最大允许的页面数，删除头节点后面的节点（删除链表中的引用并删除节点本身）.
# -*- coding: utf-8 -*- # @Author: 何睿 # @Create Date: 2019-01-13 11:25:33 # @Last Modified by: 何睿 # @Last Modified time: 2019-01-13 13:16:53 # 使用双向链表，存储页面信息，每一个节点都需要连个指针，一个指向前驱结点，一个指向后继节点 # 根据题意key相当于页面号，value相当于页面中的内容 # 链表中的head，tail节点用作辅助节点 class Node: def __init__(self, key, value): # key相当于请求的页面 self.key = key # value相等于页面中存储的信息 self.value = value # 指向后继节点 self.next = None # 指向前驱结点 self.prev = None class LRUCache: def __init__(self, capacity): """ :type capacity: int """ # 页面最大容量 self.capacity = capacity # 字典用于存储链表节点的索引，根据key查找页面 self._dict = dict() # 链表头节点 # 头节点后面的节点是最早使用的 self.head = Node(0, 0) # 链表尾节点 # 尾节点前面的节点是刚刚才使用过的 self.tail = Node(0, 0) # 让链表头尾相连 self.head.next = self.tail self.tail.prev = self.head def get(self, key): """ :type key: int :rtype: int """ # 如果要查找的页面已经被分配 if key in self._dict: # 获取当前节点 node = self._dict[key] # 我们将此节点移动到尾节点前面，表示此节点最近被使用过 # 此操作分两步 1. 在节点在双向链表中删除（只是删除节点引用，不删除节点本身） self._remove(node) # 将节点添加到双向链表的末尾（tail节点前面） self._add(node) return node.value return -1 def put(self, key, value): """ :type key: int :type value: int :rtype: void """ # 如果要添加的页面已经被分配到页面中，将当前节点删除 # (删除在链表中的指向，并且删除节点本身) if key in self._dict: self._remove(self._dict[key]) del self._dict[key] # 新建一个节点 node = Node(key, value) # 添加当前节点 self._add(node) # 建立字典，以key为键，节点的引用为值 self._dict[key] = node # 如果当前的最大容量已经超过了给定的容量，则删除head后面的第一个节点（最近最久未被使用） if len(self._dict) > self.capacity: node = self.head.next # 在双线链表中删除节点 self._remove(node) # 删除字典中的引用 del self._dict[node.key] # 删除当前节点本身 del node def _remove(self, node): prev = node.prev _next = node.next prev.next = _next _next.prev = prev node.prev = None node.next = None def _add(self, node): prev = self.tail.prev prev.next = node self.tail.prev = node node.prev = prev node.next = self.tail
源代码文件在这里.
