LeetCode 146. LRU Cache
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
