学习笔记 | LeetCode 460. LFU缓存

LeetCode 460. LFU缓存

请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。它应该支持以下操作：get 和 put。

• get(key)

  - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。

• put(key, value)

  - 如果键已存在，则变更其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新项之前，使最不经常使用的项无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除最久未使用的键。
• 「项的使用次数」就是自插入该项以来对其调用

  get

  和

  put

  函数的次数之和。使用次数会在对应项被移除后置为 0 。

进阶：

• 你是否可以在 O(1) 时间复杂度内执行两项操作？

示例：

LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回 1
cache.put(3, 3);    // 去除 key 2
cache.get(2);       // 返回 -1 (未找到key 2)
cache.get(3);       // 返回 3
cache.put(4, 4);    // 去除 key 1
cache.get(1);       // 返回 -1 (未找到 key 1)
cache.get(3);       // 返回 3
cache.get(4);       // 返回 4
           

代码

class Node:
    def __init__(self, key, val, freq=1, prev=None, next=None):
        self.key = key
        self.val = val
        self.freq = freq
        self.prev = prev
        self.next = next

class LinkedNodeList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.size = 0

    def __len__(self):
        return self.size

    def append(self, node):
        if self.head is None and self.tail is None:
            self.head = self.tail = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node
        self.size += 1

    def remove(self, node):
        assert len(self) >= 1
        if node is self.head and node is self.tail:
            self.head = None
            self.tail = None
        else:
            if node is self.head:
                self.head = node.next
                node.next = None
            elif node is self.tail:
                self.tail = node.prev
                node.prev = None
            else:
                prev = node.prev
                next = node.next
                
                prev.next = next
                next.prev = prev
                
                node.prev = None
                node.next = None
        self.size -= 1
        
class LFUCache(object):
    def __init__(self, capacity):
        """
        :type capacity: int
        """
        self.heap = []
        self.capacity = capacity
        
        self.cnt = 0
        
        self.freq_mapping = {}
        self.key_mapping = {}        

    @property
    def min_freq(self):
        return min(self.freq_mapping.keys())

    def _get_existing_node(self, key):
        node = self.key_mapping[key]
        old_freq = node.freq
        new_freq = old_freq + 1
        linked_list = self.freq_mapping[old_freq]
        linked_list.remove(node)
        if len(linked_list) == 0:
            self.freq_mapping.pop(old_freq, None)
        linked_list = self.freq_mapping.get(new_freq, None) or LinkedNodeList()
        node.freq = new_freq
        linked_list.append(node)
        self.freq_mapping[new_freq] = linked_list
        return node

    def _put_new_node(self, key, value):
        linked_list = self.freq_mapping.get(1, None) or LinkedNodeList()
        node = Node(key, value)
        self.key_mapping[key] = node
        linked_list.append(node)
        self.freq_mapping[1] = linked_list
        self.cnt += 1        
    
    def get(self, key):
        """
        :type key: int
        :rtype: int
        """
        val = -1
        if key in self.key_mapping:
            node = self._get_existing_node(key)
            val = node.val
        return val        

    def put(self, key, value):
        """
        :type key: int
        :type value: int
        :rtype: None
        """
        if self.capacity == 0:
            return
        if key in self.key_mapping:
            node = self._get_existing_node(key)
            node.val = value
        else:
            if self.cnt < self.capacity:
                self._put_new_node(key, value)
            else:
                min_freq = self.min_freq
                linked_list = self.freq_mapping[min_freq]
                head = linked_list.head
                self.key_mapping.pop(head.key)
                linked_list.remove(head)
                del head
                if len(linked_list) == 0:
                    self.freq_mapping.pop(min_freq)
                self._put_new_node(key, value)        



# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
           

• LFU维护着N个使用频率的双向链表，命中的数据，会随着freq的增加，而被重新放置于更大的freq对应的双向链表中（具体的位置是尾部），而那些freq频率最小的双向链表，则是当缓存超出时，考虑删除的数据；由于对于每一个双向链表，新数据总是append到尾部，所以在删除数据的时候，删除的是最小频率的双向链表的表头；