力扣146题、460题（LRU缓存机制、LFU算法） 146.LRU缓存机制 460、LFU算法
基本思想：
需要做到两点：
1.
快读找到某个key是否有对应的val。(用字典)
2.
要支持在任意的位置快速插入和删除元素。（用链表）
结合起来就是哈希链表
使用双向链表和哈希表结合
为什么使用双向链表？
具体实现：
对哈希双向链表的操作
1.在第一个节点处添加节点 addToHead（）
2.删除其中一个节点removeNode（）
3.将一个节点移至第一个节点处moveToHead（）
4.删除最后一个节点removeTail（）
规定越靠近头部是最新的元素，越靠近尾部是越旧的元素
代码：
class DLinkedNode: def __init__(self, key=0, value=0): self.key = key self.value = value self.prev = None self.next = None class LRUCache: def __init__(self, capacity: int): self.cache = dict() # 创建一个空字典 # 使用伪头部和伪尾部节点 self.head = DLinkedNode() #创建一个头结点 self.tail = DLinkedNode() #创建一个尾节点 self.head.next = self.tail self.tail.prev = self.head self.capacity = capacity self.size = 0 def get(self, key: int) -> int: if key not in self.cache: return -1 # 如果 key 存在，先通过哈希表定位，再移到头部 node = self.cache[key] #node是通过put创建出的节点，有key有value self.moveToHead(node) return node.value def put(self, key: int, value: int) -> None: if key not in self.cache: # 如果 key 不存在，创建一个新的节点 node = DLinkedNode(key, value) # 添加进哈希表 self.cache[key] = node # node的key给字典的key，node的value给字典的value？？？ # 添加至双向链表的头部 self.addToHead(node) self.size += 1 if self.size > self.capacity: # 如果超出容量，删除双向链表的尾部节点 removed = self.removeTail() # 删除哈希表中对应的项 self.cache.pop(removed.key) self.size -= 1 else: # 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部 node = self.cache[key] node.value = value self.moveToHead(node) def addToHead(self, node): node.prev = self.head node.next = self.head.next self.head.next.prev = node self.head.next = node def removeNode(self, node): node.prev.next = node.next node.next.prev = node.prev def moveToHead(self, node): self.removeNode(node) self.addToHead(node) def removeTail(self): node = self.tail.prev self.removeNode(node) return node
460、LFU算法
基本思想：
具体实现：
定义两个字典：
1.第一个：key-to-node，
key对应的value
2.第二个：双向链表
freq对应key与value
目的：利用两个哈希表来使得两个操作的时间复杂度均为O(1)
get(key)操作：
判断key是否存在
存在的话，在原有的频率对应的列表[key：value;key：value;key：value]中，删除这个key：value
判断是否改变了最小频率
将这个key对应的freq+1
再将这key：value放入新的freq对应的列表中
put(key,value)操作：
插入的key如果原来就存在，做法如同get
插入的key不存在的话
判断容量是否满了，满了就删除最小频率对应的key
不满的话就是一个新的key，出现频率为1
代码：
# 定义节点 class Node: def __init__(self, key, val): self.key = key self.val = val self.freq = 1 self.prev = self.next = None # 定义双向链表 class DLinkedList: def __init__(self): self.dummy = Node(None, None) # 成环，初始双向列表中只有一个节点 self.dummy.next = self.dummy self.dummy.prev = self.dummy self.size = 0 def append(self, node: Node): # 尾插入, 加到双向链表尾部 自己画图画图画图 node.prev = self.dummy.prev node.next = self.dummy node.prev.next = node self.dummy.prev = node self.size += 1 def pop(self, node: Node = None): if self.size == 0: return # 删除头部 自己画图画图画图 if node is None: node = self.dummy.next node.prev.next = node.next node.next.prev = node.prev self.size -= 1 return node class LFUCache: def __init__(self, capacity: int): from collections import defaultdict self.key_to_node = {} self.freq = defaultdict(DLinkedList)
# freq:[key:value;key:value] self.min_freq = 0 self.capacity = capacity def get(self, key: int) -> int: if key not in self.key_to_node: return -1 node = self.key_to_node[key] node_freq = node.freq self.freq[node_freq].pop(node)
#self.freq[node_freq] 是[key:value;key:value;....] if self.min_freq == node_freq and self.freq[node_freq].size == 0: self.min_freq += 1 node.freq += 1 self.freq[node.freq].append(node) return node.val def put(self, key: int, value: int) -> None: if self.capacity == 0: return if key in self.key_to_node: node = self.key_to_node[key] node_freq = node.freq self.freq[node_freq].pop(node) if self.min_freq == node_freq and self.freq[node_freq].size == 0: self.min_freq += 1 node.freq += 1 node.val = value self.freq[node.freq].append(node) else: if len(self.key_to_node) == self.capacity: node = self.freq[self.min_freq].pop() self.key_to_node.pop(node.key) node = Node(key, value) self.key_to_node[key] = node self.freq[1].append(node) self.min_freq = 1
不是O(1)时间但比O(1)时间的容易想到和简单直观，应对面试更实际一点吧
二分法，主要通过维护一个按（频率，时间）有序的key列表和一个{key:值，频率，时间}的哈希实现
每次从key里取出值和频率时间后再根据频率时间在key列表里找到该记录并移除后再更新并二分插入即可
from bisect import bisect_left, insort class LFUCache: def __init__(self, capacity: int): self.cap, self.tick = capacity, 0 # 容量和计时 self.his = [] # 元素形式为：(freq, tick, key) self.dic = {} # 键值对形式为：key:[val, freq, tick] def get(self, key: int) -> int: if key not in self.dic: # key不存在 return -1 self.tick += 1 # 计时 val, freq, tick = self.dic[key] # 取出值、频率和时间 self.dic[key][1] += 1 # 将频率+1 self.his.pop(bisect_left(self.his, (freq, tick, key))) # 找到history里的记录并移除 insort(self.his, (freq+1, self.tick, key)) # 将更新后的记录二分插入 return val def put(self, key: int, value: int) -> None: if not self.cap: return self.tick += 1 if key in self.dic: _, freq, tick = self.dic[key] # 取出频率和时间 self.dic[key][:] = value, freq+1, self.tick # 更新值、频率和计时 self.his.pop(bisect_left(self.his, (freq, tick, key))) # 找到history里的记录并移除 insort(self.his, (freq+1, self.tick, key)) # 将更新后的记录二分插入 else: # 无该记录 self.dic[key] = [value, 1, self.tick] if len(self.his) == self.cap: # history容量已满 del self.dic[self.his.pop(0)[2]] # 移除history首个元素即对应的键值对 insort(self.his, (1, self.tick, key)) # 将新记录插入history