LFU Cache

大家好，欢迎来到IT知识分享网。

24. LFU Cache
中文English
LFU (Least Frequently Used) is a famous cache eviction algorithm.

For a cache with capacity k, if the cache is full and need to evict a key in it, the key with the lease frequently used will be kicked out.

Implement set and get method for LFU cache.

Example
Given capacity=3

set(2,2)
set(1,1)
get(2)
>> 2
get(1)
>> 1
get(2)
>> 2
set(3,3)
set(4,4)
get(3)
>> -1
get(2)
>> 2
get(1)
>> 1
get(4)
>> 4

维护一个 map 实现取数据时的O(1)复杂度
维护一个双链表实现更新数据时的O(1)~O(n)复杂度

        
class LFUCache:
    """ @param: capacity: An integer """
    class ListNode:
        def __init__(self, key, value, next=None, prev=None, visit_count=0):
            self.key = key
            self.value = value
            self.next = next
            self.prev = prev
            self.visit_count = visit_count
        
    def __init__(self, capacity):
        # do intialization if necessary
        self.l = 0
        self.capacity = capacity
        self.maps = { 
   }
        self.start = self.ListNode(key=None, value=None)
        self.tail = self.ListNode(key=None, value=None)
        self.start.next = self.tail
        self.tail.prev = self.start
    """ @param: key: An integer @param: value: An integer @return: nothing """
    def set(self, key, value):
        # write your code here
        node = self.maps.get(key)
        if node != None:
        	# 已存在key 更新visitcount 移动位置
            node.value = value
            node.visit_count += 1
            tmp = node.prev
            while node.visit_count >= tmp.visit_count and tmp != self.start:
                tmp = tmp.prev
            node.next.prev = node.prev
            node.prev.next = node.next
            node.next = tmp.next
            tmp.next.prev = node
            tmp.next = node
            node.prev = tmp
            return
            
        else:
        # key不存在 新建一个key 
        # 进一步分为两种情况 缓存已满和缓存未满
            node = self.ListNode(key, value, self.tail, self.tail.prev)
            self.tail.prev.next = node
            self.tail.prev = node
            if self.l < self.capacity:
                self.l += 1
            else:
                invalid_node = node.prev
                invalid_key = invalid_node.key
                del self.maps[invalid_key]
                invalid_node.prev.next = node
                node.prev = invalid_node.prev
            tmp = node.prev
            while node.visit_count >= tmp.visit_count and tmp != self.start:
                tmp = tmp.prev
            node.next.prev = node.prev
            node.prev.next = node.next
            node.next = tmp.next
            tmp.next.prev = node
            tmp.next = node
            node.prev = tmp
            
            self.maps[key] = node
            
    """ @param: key: An integer @return: An integer """
    def get(self, key):
        # write your code here
        node = self.maps.get(key)
        if node:
            node.visit_count += 1
            tmp = node.prev
            while node.visit_count >= tmp.visit_count and tmp != self.start:
                tmp = tmp.prev
            node.next.prev = node.prev
            node.prev.next = node.next
            node.next = tmp.next
            tmp.next.prev = node
            tmp.next = node
            node.prev = tmp
            return node.value
        else:
            return -1