Open YBFACC opened 3 years ago
为了实现O(1)时间复杂度,此题需要使用双向链表。
需要使用map来快速获取双向链表的值
需要使用frequentMap来获取同频率的所有节点。
需要维护一个变量minFreq来指向frequentMap中频率最低
更新minFreq的时机:节点已经从原链表中删除,节点插入到新链表之后
此图作者:liweiwei1419 链接:https://leetcode-cn.com/problems/lfu-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiwei/
此图作者:liweiwei1419
链接:https://leetcode-cn.com/problems/lfu-cache/solution/ha-xi-biao-shuang-xiang-lian-biao-java-by-liweiwei/
class linkedTwo { pre: linkedTwo | undefined next: linkedTwo | undefined key: number val: number times: number constructor(key: number, val: number) { this.key = key this.val = val this.pre this.next this.times = 1 } delete(): void { const pre = this.pre as linkedTwo const next = this.next as linkedTwo pre.next = next next.pre = pre } } class LFUCache { getLinked: Map<number, linkedTwo> frequentMap: Map<number, LFUitem> max: number cache_num: number minFreq: number constructor(capacity: number) { this.max = capacity this.frequentMap = new Map() this.getLinked = new Map() this.cache_num = 0 this.minFreq = 1 } get(key: number): number { if (this.getLinked.has(key)) { const linked = this.getLinked.get(key) as linkedTwo this.move(linked) return linked.val } return -1 } put(key: number, value: number): void { const frequentMap = this.frequentMap if (this.getLinked.has(key)) { const linked = this.getLinked.get(key) as linkedTwo linked.val = value this.move(linked) } else { if (this.cache_num >= this.max && this.max >= 1) { let item = frequentMap.get(this.minFreq) as LFUitem const temp = item.delete_Tail() this.getLinked.set(key, this.insert_linked(key, value)) this.getLinked.delete(temp) } else if (this.cache_num < this.max) { this.getLinked.set(key, this.insert_linked(key, value)) this.cache_num++ } } } move(linked: linkedTwo): void { const frequentMap = this.frequentMap linked.delete() linked.times++ this.add_frequentMap(linked) this.updata_minFreq(frequentMap.get(linked.times - 1) as LFUitem, linked.times - 1) } insert_linked(key: number, value: number): linkedTwo { const target = new linkedTwo(key, value) this.minFreq = 1 this.add_frequentMap(target) return target } add_frequentMap(linked: linkedTwo): void { const frequentMap = this.frequentMap const index = linked.times if (!frequentMap.has(index)) { frequentMap.set(index, new LFUitem()) } const item = frequentMap.get(index) as LFUitem item.insert_tump(linked) } updata_minFreq(item: LFUitem | undefined, index: number): void { if (!item) return const frequentMap = this.frequentMap if (item.nothing()) { frequentMap.delete(index) if (frequentMap.size === 0) { this.minFreq = 1 return } while (!frequentMap.has(this.minFreq)) { this.minFreq++ } } } } class LFUitem { tump: linkedTwo tail: linkedTwo constructor() { this.tump = new linkedTwo(NaN, NaN) this.tail = new linkedTwo(NaN, NaN) this.tump.next = this.tail this.tail.pre = this.tump } insert_tump(linked: linkedTwo): void { const temp = this.tump.next as linkedTwo linked.pre = this.tump this.tump.next = linked linked.next = temp temp.pre = linked } delete_Tail(): number { const target = this.tail.pre as linkedTwo const pre = target.pre as linkedTwo pre.next = this.tail this.tail.pre = pre return target.key } nothing(): boolean { const tump = this.tump const tail = this.tail if (tump.next === tail) { return true } return false } }
使用双向链表代替frequentMap,可以省去minFreq变量。
原本更新minFreq的时间复杂度在最坏的情况下,不是O(1)
class linked_list { tump: linked_item tail: linked_item constructor(frequent: frequentItem) { this.tump = new linked_item(NaN, NaN, frequent) this.tail = new linked_item(NaN, NaN, frequent) this.tump.next = this.tail this.tail.pre = this.tump } insert_tump(linked: linked_item): void { const temp = this.tump.next as linked_item linked.pre = this.tump this.tump.next = linked linked.next = temp temp.pre = linked } delete_Tail(): number { const target = this.tail.pre as linked_item const pre = target.pre as linked_item pre.next = this.tail this.tail.pre = pre return target.key } nothing(): boolean { const tump = this.tump const tail = this.tail if (tump.next === tail) { return true } return false } } class linked_item { pre: linked_item | undefined next: linked_item | undefined key: number val: number frequent: frequentItem | undefined constructor(key: number, val: number, frequent?: frequentItem) { this.key = key this.val = val this.pre this.next this.frequent = frequent } delete(): void { const pre = this.pre as linked_item const next = this.next as linked_item pre.next = next next.pre = pre } } class frequent_list { start: frequentItem end: frequentItem constructor() { this.start = new frequentItem(NaN) this.end = new frequentItem(NaN) this.start.next = this.end this.end.pre = this.start } insert(linked: linked_item) { if (this.start?.next?.key !== 1) { this.start.add_frequentItem(1) } const one = this.start.next as frequentItem linked.frequent = one one.item.insert_tump(linked) } delete(): number { const target = this.start.next as frequentItem if (target.key === NaN) return -1 const key = target.item.delete_Tail() target.delete_frequentItem() return key } } class frequentItem { pre: frequentItem | undefined next: frequentItem | undefined item: linked_list key: number constructor(key: number) { this.pre this.next this.item = new linked_list(this) this.key = key } next_item(linked: linked_item) { if (this.next?.key !== this.key + 1) { this.add_frequentItem(this.key + 1) } const next_linked_list = this.next?.item! linked.frequent = this.next! next_linked_list.insert_tump(linked) this.delete_frequentItem() } add_frequentItem(key: number) { const next = this.next as frequentItem const new_item = new frequentItem(key) this.next = new_item new_item.pre = this new_item.next = next next.pre = new_item } delete_frequentItem() { const linked_list = this.item as linked_list if (linked_list.nothing()) { const pre = this.pre as frequentItem const next = this.next as frequentItem pre.next = next next.pre = pre } } } class LFUCache { linked_item: Map<number, linked_item> frequent_list: frequent_list capacity: number cache_num: number constructor(capacity: number) { this.cache_num = 0 this.capacity = capacity this.linked_item = new Map() this.frequent_list = new frequent_list() } get(key: number): number { const map = this.linked_item if (map.has(key)) { const target = map.get(key) as linked_item this.move(target) return target.val } return -1 } put(key: number, value: number): void { const map = this.linked_item if (this.capacity === 0) return if (map.has(key)) { const target = map.get(key) as linked_item target.val = value this.move(target) } else { const frequent_list = this.frequent_list if (this.cache_num === this.capacity) { const key = frequent_list.delete() map.delete(key) } else { this.cache_num++ } const target = new linked_item(key, value) map.set(key, target) frequent_list.insert(target) } } move(linked: linked_item) { const frequent = linked.frequent as frequentItem linked.delete() frequent.next_item(linked) } }
LFU缓存
为了实现O(1)时间复杂度,此题需要使用双向链表。
需要使用map来快速获取双向链表的值
需要使用frequentMap来获取同频率的所有节点。
需要维护一个变量minFreq来指向frequentMap中频率最低
更新minFreq的时机:节点已经从原链表中删除,节点插入到新链表之后
使用双向链表代替frequentMap
使用双向链表代替frequentMap,可以省去minFreq变量。
原本更新minFreq的时间复杂度在最坏的情况下,不是O(1)