LeetCode 146. LRU Cache 原创Java参考解答

LeetCode 146. LRU Cache 原创Java参考解答

问题描述

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

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

get(key) – Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(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.

解题思路

经典的算法问题:LRU Cache,设计最近最少使用缓存。

最近最少使用缓存(LRU)需要两个操作:获取数据(get)和写入数据(set)。

  • 获取数据get(key):如果缓存中存在key,则获取其数据值,否则返回-1。
  • 写入数据set(key, value):如果key还没有在缓存中,则写入其数据值。当缓存达到容量上限,它应该在写入新数据之前,删除最近最少使用的过往数据来腾出空闲位置。
常见的LRU Cache实现方法:双向链表(Doubly Linked List) + HashMap
LRU的实质是按照节点访问时间顺序排列的双向链表。每个双向链表节点有prev和next指向其一前一后的节点。最近被访问的节点放置在链表头部。一旦链表达到容量,需要剔除元素的时候,踢出链表尾部的最老时间被访问过的元素。
HashMap则是用来根据key来找对应的链表节点。

参考代码

相关题目

LeetCode All in One 原创题目讲解汇总

发表评论

电子邮件地址不会被公开。 必填项已用*标注