C# O(1) Accepted Solution.


  • 1
    R

    public class LFUCache {
    private class CacheItem
    {
    public int key;
    public int value;
    public long frequency;
    }

        Dictionary<int, LinkedListNode<CacheItem>> dic1; // key, Node
        Dictionary<long, LinkedList<CacheItem>> dic2;// Frequncy , List
        
        Dictionary<long, LinkedListNode<long>> dic3;// 根据frequency 找到node
        LinkedList<long> list;// frequency enum
    
        private int capacity;
    
        public LFUCache(int capacity)
        {
            this.capacity = capacity;
            dic1 = new Dictionary<int, LinkedListNode<CacheItem>>();
            dic2 = new Dictionary<long, LinkedList<CacheItem>>();
            
            list = new LinkedList<long>();
            dic3 = new Dictionary<long, LinkedListNode<long>>();
        }
    
        public int Get(int key)
        {
            if (this.capacity <= 0)
                return -1;
    
            if (dic1.ContainsKey(key))
            {
                var node = dic1[key];
                
                node.Value.frequency++;
                if (dic2.ContainsKey(node.Value.frequency))
                {
                    dic2[node.Value.frequency].AddLast(node.Value);
                }
                else
                {
                    AddNewNodeInDic2(key, node.Value.value, node.Value.frequency);
                }
                dic1[key] = dic2[node.Value.frequency].Last;
    
                var listInner = dic2[node.Value.frequency - 1];
                listInner.Remove(node.Value);
                if (dic2[node.Value.frequency - 1].Count == 0)
                {
                    dic2.Remove(node.Value.frequency - 1);
                    var removeNode = dic3[node.Value.frequency - 1];
                    list.Remove(removeNode.Value);
                    dic3.Remove(node.Value.frequency - 1);
                }
                
                return node.Value.value;
            }
            else
                return -1;
        }
    
        public void Put(int key, int value)
        {
            if (this.capacity <= 0)
                return;
    
            if(dic1.ContainsKey(key))//已有 重置该key的值,并将frequency加一
            {
                var node = dic1[key];
    
                node.Value.frequency++;
                node.Value.value = value;
                if (dic2.ContainsKey(node.Value.frequency))
                {
                    dic2[node.Value.frequency].AddLast(node.Value);
                }
                else
                {
                    AddNewNodeInDic2(key, node.Value.value, node.Value.frequency);
                }
                dic1[key] = dic2[node.Value.frequency].Last;
    
                var listInner = dic2[node.Value.frequency - 1];
                listInner.Remove(node.Value);
                if (dic2[node.Value.frequency - 1].Count == 0)
                {
                    dic2.Remove(node.Value.frequency - 1);
                    var removeNode = dic3[node.Value.frequency - 1];
                    list.Remove(removeNode.Value);
                    dic3.Remove(node.Value.frequency - 1);
                }
            }
            else// 没有,找到dic2[list.first()].first()元素  将其在dic1中删除 ,然后在dic1和dic2中插入新元素
            {
                if(dic1.Count >= this.capacity)// full
                {
                    var dic2Key = list.First.Value;
                    var node = dic2[dic2Key];
                    dic1.Remove(node.First().key);
    
                    node.Remove(node.First);
                    if (!dic2[dic2Key].Any())//删除后,没有元素了
                    {
                        dic2.Remove(dic2Key);
                        var removeNode = dic3[dic2Key];
                        list.Remove(removeNode.Value);
                        dic3.Remove(dic2Key);
                    }
    
                    AddNewNodeInDic2(key, value);
                    dic1.Add(key, dic2[1].Last);
                }
                else// not full
                {
                    AddNewNodeInDic2(key, value);
                    dic1.Add(key, dic2[1].Last);
                }
            }
        }
    
        private void AddNewNodeInDic2(int key, int value, long frequency = 1)
        {
            LinkedListNode<CacheItem> newNode = new LinkedListNode<CacheItem>(new CacheItem()
            {
                frequency = frequency,
                key = key,
                value = value
            });
            if (dic2.ContainsKey(frequency))
            {
                dic2[frequency].AddLast(newNode);
            }
            else
            {
                var newList = new LinkedList<CacheItem>();
                newList.AddLast(newNode.Value);
                dic2.Add(frequency, newList);
    
                if(frequency == 1)
                {
                    if (list.First == null || list.First.Value != 1)
                    {
                        list.AddFirst(1);
                        dic3.Add(1, list.First);
                    }
                }
                else
                {
                    if (dic3[frequency - 1].Next == null || dic3[frequency - 1].Next.Value != frequency)
                    {
                        var newNode3 = new LinkedListNode<long>(frequency);
                        list.AddAfter(dic3[frequency - 1], newNode3);
                        dic3.Add(frequency, newNode3);
                    }
                }
            }
    
        }
    

    }


Log in to reply
 

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