146、LRU缓存-cangjie

题目

146、LRU缓存

思路

1. 数据结构：

   • 使用 HashMap (map) 存储缓存的键值对。键是缓存的键，值是链表节点，可以通过键快速访问。
   • 使用 LinkedList (lists) 来维护缓存的顺序。链表从头到尾表示使用时间，头部是最老的元素，尾部是最近使用的元素。
   • maxSize 是缓存的最大容量。

2. 初始化：

   • 初始化链表和哈希表。在构造函数中，设置最大容量并创建相应的数据结构。

3. 获取（get）操作：

   • 如果键存在于哈希表中：
     • 从 map 中获取对应的链表节点（即存储的键值对）。
     • 读取值，并将对应节点移到链表的尾部（表示最近使用）。
     • 更新哈希表中该键的新位置。
   • 如果键不存在，返回 -1。

4. 插入（put）操作：

   • 如果键已经存在：
     • 移除旧节点并在链表中插入新节点（更新为最新的值）。
   • 如果键不存在：
     • 插入新节点到链表尾部。
     • 如果超过最大容量，移除链表头部（最老的元素）和哈希表中对应的键，确保缓存不超过最大容量。

代码

import std.collection.*

class LRUCache {
    var map : HashMap<Int64, LinkedListNode<Array<Int64>>>
    var lists : LinkedList<Array<Int64>>
    var maxSize : Int64
    init(capacity: Int64) {
        this.lists = LinkedList<Array<Int64>>() // 链表头最老，尾最新
        // println("init! list size = ${lists.size}")
        maxSize = capacity
        this.map = HashMap<Int64, LinkedListNode<Array<Int64>>>()
    }
    
    func get(key: Int64): Int64 {
        // println("get in!")
        if(map.contains(key)){
            let oldNode = map[key]
            var val = oldNode.value[1]
            // println("get node val ${val}")
            let newNode = lists.append([key,val])
            lists.remove(oldNode)
            map.put(key, newNode)
            return val
        }
        return -1
    }
    
    func put(key: Int64, value: Int64): Unit {
        // println("put in!")
        if(map.contains(key)){
            lists.remove(map[key])
            let node = lists.append([key,value])
            map.put(key, node)
            // println("refresh! list size = ${lists.size}")
        }
        else{
            let node = lists.append([key,value])
            map.put(key, node)
            // println("put! list size = ${lists.size}")
            // println("newNode info : ${node.value[0]}, ${node.value[1]}")
            if(lists.size > maxSize){
                // println("cache oversize! remove head")
                map.remove((lists.firstNode()??throw Exception("er")).value[0])
                lists.remove((lists.firstNode()??throw Exception("er")))
                // println("remove over! list size = ${lists.size}")
            }
        }
    }
}

/**
 * Your LRUCache object will be instantiated and called as such:
 * let obj: LRUCache = LRUCache(capacity)
 * let param_1 = obj.get(key)
 * obj.put(key,value)
 */

复杂度

时间复杂度

1. get操作：

   • 在哈希表中查找键是 O(1) 的时间复杂度。
   • 移动节点在链表中（移除和插入）也是在 O(1) 的时间复杂度。
   • 因此，get 的总时间复杂度是 O(1)。

2. put操作：

   • 查找键操作为 O(1)。
   • 移动节点的操作也是 O(1)。
   • 若需移除链表头部元素，时间复杂度为 O(1)。
   • 因此，put 的总时间复杂度也是 O(1)。

空间复杂度

• HashMap 和 LinkedList 都存储相同数量的元素，因此空间复杂度是 O(n)，其中 n 是当前缓存中存储的元素数量。
• 由于只存储活动的缓存项，所以最大空间复杂度为 O(n)，与最大容量相同。

遇到的坑

1、为了实现插入后删除最老，需要从ListNode反查key，所以LinkedListNode需要存储kvpair，不能只存一个value
2、双向链表节点获取问题

map.remove((lists.firstNode()??throw Exception("er")).value[0])
lists.remove((lists.firstNode()??throw Exception("er")))

老生常谈了，option类型的返回值函数需要??判断是否抛错误

public func firstNode(): Option<LinkedListNode<T>>

3、初始化问题
不知道为什么this.map = HashMap<Int64, LinkedListNode<Array<Int64>>>(capacity, lists.firstNode()??throw Exception("error"))会要(Int64) ->Tuple, (capacity, lists.firstNode()??throw Exception("error"))这个不已经是tuple类型了嘛

this.map = HashMap<Int64, LinkedListNode<Array<Int64>>>() // ok,size = 0
this.map = HashMap<Int64, LinkedListNode<Array<Int64>>>((capacity, lists.firstNode()??throw Exception("error"))) // ok,但是需要list初始化的时候起一个头节点 例如先lists.append([0,0])
this.map = HashMap<Int64, LinkedListNode<Array<Int64>>>(capacity, lists.firstNode()??throw Exception("error")) // 不ok，报错如下

结果

cangjie