460. LFU Cache

Loading...LeetCode

跟LRU那题相比，排序的 primary key 变成了使用次数 frequency，有并列再去比较 recent use，本来想在LRU解法的基础上增加一个freq map，但是这样的话，如果拿 frequency 做 key 则get函数做不到O(1)，拿 node 做 key 则put函数做不到O(1)。

146. LRU Cache

然后就看到了这个大神讲解：Python concise solution detailed explanation: Two dict + Doubly linked list

基本思路是，freq map 存储一个双指针链表（python可以用OrderedDict代替），这个链表内部来完成LRU的功能，这样在put的时候就可以先找LFU，里面有多个元素的话可以直接根据顺序找到LRU（其实就是嵌套一个LRU的解）。

OrderedDict

class ListNode:
    def __init__(self, key, value):
        self.key = key
        self.val = value
        self.freq = 1
        
class LFUCache:

    def __init__(self, capacity: int):
        self.capacity = capacity
        self.cache = dict() 
        ## usage[f][k]=v : frequency = f, key = k, v = value 
        self.usage = collections.defaultdict(collections.OrderedDict)
        ## current least frequenct usage
        self.LF = 0

    def get(self, key: int) -> int:
        if key not in self.cache: return -1
        node = self.cache[key]
        ## update the frequency
        self.update(node, node.val)
        return node.val
        
    def put(self, key: int, value: int) -> None:
        if self.capacity == 0: return
        if key not in self.cache: 
            if len(self.cache) >= self.capacity:
                ## pop the node with current least freuenct usage (FIFO)
                k, v = self.usage[self.LF].popitem(last=False)
                self.cache.pop(k)
            node = ListNode(key, value)
            ## save the new node into cache and usage map
            self.cache[key] = node
            self.usage[1][key] = value
            ## reset current LF to 1
            self.LF = 1
        else: 
            ## update the vaLue of existing key 
            node = self.cache[key]
            node.val = value
            ## update the frequency
            self.update(node, value)
            
            
    def update(self, node, newVal):
        k, f = node.key, node.freq
        ## delete from the former frequency (f)
        self.usage[f].pop(k)
        ## if the former frequency is the LFU and it become empty
        ## the new frequency (f+1) become new LFU
        if not self.usage[f] and self.LF == f:
            self.LF += 1
        ## push to the new frequency (f+1)
        self.usage[f+1][k] = newVal
        node.freq += 1
        

double linked node