Python O(1) solution with two dict and k double linked list


  • 0
    A

    class Node(object):

    def __init__(self,key, val,f):
        self.k=key
        self.v=val
        self.f=f
        self.next=None
        self.prev=None
    

    class LFUCache(object):

    def __init__(self, capacity):
        self.cap=capacity
        self.cnt=0
        self.map={}
        self.fmap={}
        self.tail=None
    
    def _add(self,node,head):
        n=head.next
        head.next=node
        node.prev=head
        n.prev=node
        node.next=n
    
    def _remove(self,node):
        p=node.prev
        n=node.next
        f=node.f
        p.next=n
        n.prev=p
        return n==self.tail and p.v==-1         #should update the tail
     
    def _createlink(self,f):
        if f not in self.fmap:
            head, tail= Node(0,-1,-1),Node(0,-1,-1)
            head.next=tail
            tail.prev=head
            self.fmap[f]=(head,tail)
    
    def get(self, key):
        if key in self.map:
            node=self.map[key]
            val=node.v
            f=node.f
            f+=1
            self._createlink(f)
            if self._remove(node):
                self.tail=self.fmap[f][1]
            node.f=f
            newhead=self.fmap[f][0]
            self._add(node,newhead)
            return val  
        else:
            return -1
    
    def put(self, key, value):
        flag=0
        if key in self.map:
            
            node=self.map[key]
            f=node.f
            f+=1
            self._createlink(f)
            if self._remove(node):
                self.tail=self.fmap[f][1]
        else:
            f=1
            self._createlink(f)
            if self.cnt==self.cap:
                if self.cap==0:     
                    return
                de=self.tail.prev
                self._remove(de)
                del self.map[de.k]
            else:
                self.cnt+=1
            self.tail=self.fmap[f][1]
    
        node=Node(key,value,f)
        newhead=self.fmap[f][0]
        self._add(node,newhead)
        self.map[key]=node

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.