My C# solution


  • 0
    S
    public class LRUCache 
    {
        Dictionary<int, LinkedListNode<int>> dic;
        int capacity;
        LinkedListNode<int> head;
        LinkedListNode<int> tail;
        LinkedList<int> cache;
        
        public LRUCache(int capacity) 
        {
            cache = new LinkedList<int>();
            dic = new Dictionary<int, LinkedListNode<int>>();
            this.capacity = capacity;
            head = new LinkedListNode<int>(0);
            tail = new LinkedListNode<int>(0);
            cache.AddFirst(head);
            cache.AddLast(tail);
        }
        
        public int Get(int key) 
        {
            LinkedListNode<int> node;
            if(dic.TryGetValue(key, out node))
            {
                cache.Remove(node);
                cache.AddBefore(tail, node);
                return node.Value;
            }
            return -1;
        }
        
        public void Put(int key, int value) 
        {
            if(capacity == 0)
                return;
            LinkedListNode<int> node;
            if(dic.TryGetValue(key, out node))
            {
                cache.Remove(node);
                cache.AddBefore(tail, node);
                node.Value = value;
            }
            else
            {
                if(cache.Count() >= capacity+2)
                {
                    node = head.Next;
                    var k = dic.First(n =>n.Value == node).Key;
                    dic.Remove(k);
                    cache.Remove(node);
                }
                var newNode = new LinkedListNode<int>(value);
                dic[key] = newNode;
                cache.AddBefore(tail, newNode);
            }
        }
    }
    

Log in to reply
 

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