抬头仰望星空,是否能发现自己的渺小。

伪斜杠青年

人们总是混淆了欲望和理想

56 | 面试题:设计和实现一个LRU Cache缓存机制

146. LRU缓存机制

关于 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条评论

发表评论