关于 LRU 缓存(优先淘汰最长时间未被使用的元素),在面试中应该是老生常谈了,但有意思的是,一般人还是用不到。
在看题解的时候发现了这个骚操作:
class LRUCache(private val capacity: Int) : LinkedHashMap<Int?, Int?>(capacity, 0.75f, true) {
operator fun get(key: Int): Int {
return super.getOrDefault(key, -1)?:-1
}
fun put(key: Int, value: Int) {
super.put(key, value)
}
override fun removeEldestEntry(eldest: Map.Entry<Int?, Int?>): Boolean {
return size > capacity
}
}
0.75的负载因子是默认的,只是为了调用三参构造函数中的第三个排序参数,才需要手动填,removeEldestEntry是为了实现超出大小就抛弃掉。
但肯定这样肯定不合适,需要去把 linkedlist 抄一抄,哈哈,开玩笑。我觉得官方题解的那份就挺不错,能写出来,说明理解链表,同时利用了 MAP,拥有最快 O(1)的时间复杂度,面试时能写出来也很不错了。
class LRUCache(var capacity: Int) {
class LinkedNode(val key: Int = -1, var value: Int = -1) {
var prev: LinkedNode? = null
var next: LinkedNode? = null
}
val cache = HashMap<Int, LinkedNode>()
var size = 0
var head: LinkedNode = LinkedNode()
var tail: LinkedNode = LinkedNode()
init {
head.next = tail
tail.prev = head
}
fun get(key: Int): Int {
val node = cache[key] ?: return -1
// 如果 key 存在,先通过哈希表定位,再移到头部
moveToHead(node)
return node.value
}
fun put(key: Int, value: Int) {
val node = cache[key]
if (node == null) {
// 如果 key 不存在,创建一个新的节点
val newNode = LinkedNode(key, value)
// 添加进哈希表
cache[key] = newNode
// 添加至双向链表的头部
addToHead(newNode)
++size
if (size>capacity){
// 如果超出容量,删除双向链表的尾部节点
val lastNode = removeTail()
// 删除哈希表中对应的项
cache.remove(lastNode.key)
--size
}
}else{
// 如果 key 存在,先通过哈希表定位,再修改 value,并移到头部
node.value=value
moveToHead(node)
}
}
private fun moveToHead(node: LinkedNode) {
removeNode(node)
addToHead(node)
}
private fun addToHead(node: LinkedNode) {
node.prev = head
node.next = head.next
head.next?.prev = node
head.next = node
}
private fun removeNode(node: LinkedNode) {
node.prev?.next = node.next
node.next?.prev = node.prev
}
private fun removeTail(): LinkedNode {
val res = tail.prev!!
removeNode(res)
return res
}
}
手抄了一遍,注释按官方的给复制过来了,逻辑简单,但细节还是得注意注意。
本站由以下主机服务商提供服务支持:
0条评论