146、LRU缓存-cangjie

题目

146、LRU缓存

思路

数据结构：
- 使用 HashMap (map) 存储缓存的键值对。键是缓存的键，值是链表节点，可以通过键快速访问。
- 使用 LinkedList (lists) 来维护缓存的顺序。链表从头到尾表示使用时间，头部是最老的元素，尾部是最近使用的元素。
- maxSize 是缓存的最大容量。
初始化：
- 初始化链表和哈希表。在构造函数中，设置最大容量并创建相应的数据结构。
获取（get）操作：
- 如果键存在于哈希表中：
  - 从 map 中获取对应的链表节点（即存储的键值对）。
  - 读取值，并将对应节点移到链表的尾部（表示最近使用）。
  - 更新哈希表中该键的新位置。
- 如果键不存在，返回 -1。
插入（put）操作：
- 如果键已经存在：
  - 移除旧节点并在链表中插入新节点（更新为最新的值）。
- 如果键不存在：
  - 插入新节点到链表尾部。
  - 如果超过最大容量，移除链表头部（最老的元素）和哈希表中对应的键，确保缓存不超过最大容量。

代码

import std.collection.*class LRUCache {var map : HashMap<Int64, LinkedListNode<Array<Int64>>>var lists : LinkedList<Array<Int64>>var maxSize : Int64init(capacity: Int64) {this.lists = LinkedList<Array<Int64>>() // 链表头最老，尾最新// println("init! list size = ${lists.size}")maxSize = capacitythis.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)*/

复杂度

时间复杂度

get操作：
- 在哈希表中查找键是 O(1) 的时间复杂度。
- 移动节点在链表中（移除和插入）也是在 O(1) 的时间复杂度。
- 因此，get 的总时间复杂度是 O(1)。
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，报错如下