LeetCode -- LRU Cache

LeetCode -- LRU Cache

題目描述：
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get


and set.


get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should


invalidate the least recently used item before inserting a new item.


實現一個LRU的緩存，關於LRU緩存，可以概括為一個指定容量的的緩存，當超出容量時，拿掉最長時間沒有使用的那個元素。

 

 

 

思路：
1. 使用哈希來存[key,value]
2. 維護一個集合，根據key的使用情況（最早使用的放最後）更新位置


實現代碼：

public class LRUCache {


    private Dictionary _cache; 
	private List _usedKeys;
	
	private int _capacity;
	
    public LRUCache(int capacity)
	{
		_cache = new Dictionary();
		_usedKeys = new List();
		
        _capacity = capacity;
    }


    public int Get(int key)
	{
        if(!_cache.ContainsKey(key)){
			return -1;
		}
		else{
			_usedKeys.Remove(key);
			_usedKeys.Insert(0, key);
			
			return _cache[key];
		}
    }


    public void Set(int key, int value) 
	{
		if(_cache.ContainsKey(key)){
			_cache[key] = value;
			
			_usedKeys.Remove(key);
			_usedKeys.Insert(0, key);
		}
		else{
			if(_cache.Keys.Count < _capacity){
				_cache.Add(key, value);
				
				_usedKeys.Insert(0, key);
			}
			else
			{
				var removing = _usedKeys.Last();
				_usedKeys.RemoveAt(_usedKeys.Count - 1);
				
				_cache.Remove(removing);
				_cache.Add(key, value);
				
				_usedKeys.Insert(0, key);
			}
		}
    }
    
}