C# solution beats %100.00 with pooling


  • 0
    D
    public class Pair {
        public int Key;
        public int Value;
        public Pair(int key, int value) {
            Key = key;
            Value = value;
        }
        public void SetKeyValue(int key, int value) {
            Key = key;
            Value = value;
        }
    }
    
    public class LRUCache {
        private int cap;
        private Dictionary<int, LinkedListNode<Pair>> cache;
        private LinkedList<Pair> list;
        private Stack<LinkedListNode<Pair>> poolStack;
    
        public LRUCache(int capacity) {
            cap = capacity;
            cache = new Dictionary<int, LinkedListNode<Pair>>(cap);
            list = new LinkedList<Pair>();
            poolStack = new Stack<LinkedListNode<Pair>>(cap);
            for (int i = 0; i < cap; i++) {
                poolStack.Push(new LinkedListNode<Pair>(new Pair(0, 0)));
            }
        }
    
        public int Get(int key) {
            if (!cache.ContainsKey(key))
                return -1;
            var n = cache[key];
            list.Remove(n);
            list.AddFirst(n);
            return n.Value.Value;
        }
    
        public void Set(int key, int value) {
            if (!cache.ContainsKey(key)) {
                if (cache.Count >= cap) {
                    var n = list.Last;
                    list.RemoveLast();
                    cache.Remove(n.Value.Key);
                    poolStack.Push(n);
                }
                var node = poolStack.Pop();
                node.Value.SetKeyValue(key, value);
                cache.Add(key, node);
                list.AddFirst(cache[key]);
            }
            else {
                cache[key].Value.Value = value;
                Get(key);
            }
        }
    }
    

Log in to reply
 

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