题解 | #设计LFU缓存结构#

using System;
using System.Collections.Generic;


class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * lfu design
     * @param operators int整型二维数组 ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public List<int> LFU (List<List<int>> operators, int k) {
        LFUcache cache = new LFUcache(k);
        List<int> res = new List<int>();
        foreach(List<int> op in operators){
            if(op[0] == 1){
                cache.Set(op[1], op[2]);
            }
            else if(op[0] == 2){
                res.Add(cache.Get(op[1]));
            }
        }
        return res;
    }

    class LFUcache{
        Dictionary<int, Node> keyDic = new Dictionary<int, Node>();
        Dictionary<int, DLlist> freqDic = new Dictionary<int, DLlist>();
        readonly int capacity;
        int count => keyDic.Count;
        int minFrequency;
        
        public LFUcache(int capacity){
            this.capacity = capacity;
        }
        public int Get(int key){
            //Console.WriteLine("get:"+ key);
            if(keyDic.TryGetValue(key, out Node node)){
                MoveNodeInList(node);
                return node.Value;
            }
            return -1;
        }

        public void Set(int key, int value){
            Console.WriteLine("set:"+ key +"to" + value);
            if(keyDic.TryGetValue(key, out Node node)){
                node.Value = value;
                return;
            }
            if(count == capacity){
                Node spareNode = freqDic[minFrequency].GetTail();
                freqDic[minFrequency].Remove(spareNode);
                if(freqDic[minFrequency].Count == 0){
                    freqDic.Remove(minFrequency);
                }
                //Console.WriteLine("remove" + spareNode.Key);
                keyDic.Remove(spareNode.Key); 
            }
            Node newNode = new Node(key, value);
            keyDic.Add(key, newNode);
            minFrequency = 1;
            if(!freqDic.ContainsKey(1)){
                //Console.WriteLine("good"+ newNode.Value);
                freqDic.Add(1, new DLlist());
            }
            freqDic[1].AddFirst(newNode);
        }

        void MoveNodeInList(Node node){
            freqDic[node.Frequency].Remove(node);
            if(freqDic[node.Frequency].Count == 0){
                freqDic.Remove(node.Frequency);
                if(minFrequency == node.Frequency){
                    minFrequency++;
                }   
            }
            node.Frequency++;
            if(!freqDic.ContainsKey(node.Frequency)){
                freqDic[node.Frequency] = new DLlist();
            }
            freqDic[node.Frequency].AddFirst(node);
        }


        class Node{
            internal int Frequency{get; set;}
            internal int Key{get; set;}
            internal int Value{get; set;}
            internal Node pre;
            internal Node next;

            internal Node():this(-1,-1){}
            internal Node(int key, int value){
                Key = key;
                Value = value;
                Frequency = 1;
            }
        }

        class DLlist{
            internal Node head = new Node();
            internal Node tail = new Node();
            internal int Frequency{get; set;}
            internal int Count{get;set;}

            internal DLlist(){
                head.next = tail;
                tail.pre = head;
                Count = 0;
            }

            internal void AddFirst(Node node){
                head.next.pre = node;
                node.next = head.next;
                node.pre = head;
                head.next = node;
                Count++;
            }
            internal void Remove(Node node){
                node.pre.next = node.next;
                node.next.pre = node.pre;
                Count--;
            }
            internal Node GetHead(){
                return head.next;
            }
            internal Node GetTail(){
                if(tail.pre == head) Console.WriteLine("cant get tail!!!");
                return tail.pre;
            }
        }

    }
}