[LeetCode] 146. LRU Cache

轉自LeetCode

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.

<Solution>

這題是要去設計一個給 LRU cache 用的 data structure

所謂 LRU 就是當 cache 容量滿了，又有新資料進來，就把最久沒用到的資料從 cache 給拿掉

這邊要注意到的是，每次 get, set 的那筆資料，都要變成最近一個使用的資料

這邊設計的想法是

• 用 list 來存放資料，front 是剛使用到的資料，back 是最久沒用到的資料。用 list 來存放資料，也是因為移動資料位置比較方便。list 存放的資料是 pair，key 就是 key，value 就是 value

• 那每次去 list 找資料，這樣時間會耗太久，所以在用一個 unordered_map 來當作 hash map。key 就是 key，value 是該 key 存放在 list 裡面資料的 iterator，這樣之後可以透過 iterator 直接拿到資料，而且 hash map 的 access 是 O(1)，這樣就很快

• 每次 set 之後，都要檢查是否超過 capacity，超過就刪除 list 最後一個資料，記得要也從 hash map 裡面刪除相關資料

code 如下

C++

	class LRUCache{
	public:
	LRUCache(int capacity) {
	cacheCapacity = capacity;
	}
	int get(int key) {
	auto hashMapIt = hashMap.find(key);
	//> key is not exist
	if(hashMapIt == hashMap.end()) {
	return -1;
	}
	//> move item to front and return value
	cacheList.splice(cacheList.begin(), cacheList, hashMapIt->second);
	return hashMapIt->second->second;
	}
	void set(int key, int value) {
	auto hashMapIt = hashMap.find(key);
	if(hashMapIt != hashMap.end()) {
	//> item exist, update and move to front
	hashMapIt->second->second = value;
	cacheList.splice(cacheList.begin(), cacheList, hashMapIt->second);
	}
	else {
	//> net item, create at front
	cacheList.push_front(make_pair(key, value));
	hashMap[key] = cacheList.begin();
	}
	//> out of capacity, remove LRU
	if(cacheList.size() > cacheCapacity) {
	hashMap.erase(cacheList.rbegin()->first);
	cacheList.pop_back();
	}
	}
	private:
	int cacheCapacity;
	list<pair<int, int>> cacheList;
	unordered_map<int, list<pair<int, int>>::iterator> hashMap;
	};

view raw lruCache.cpp hosted with ❤ by GitHub

Java

	class LRUCache {
	private int capacity = 0;
	Map<Integer, Node> map = null;
	Node head = null;
	Node tail = null;
	public LRUCache(int capacity) {
	this.capacity = capacity;
	map = new HashMap();
	head = new Node(0,0);
	tail = new Node(0,0);
	head.next = tail;
	tail.prev = head;
	}
	public int get(int key) {
	if(!map.containsKey(key))
	return -1;
	moveToFront(map.get(key));
	return map.get(key).val;
	}
	public void put(int key, int value) {
	if(capacity ==0)
	return;
	if(map.containsKey(key)){
	map.get(key).val = value;
	moveToFront(map.get(key));
	} else{
	freeSpace();
	Node n = new Node(key,value);
	map.put(key,n);
	addToFront(n);
	}
	}
	private void freeSpace(){
	if(map.size() == capacity){
	Node toRemove = head.next;
	map.remove(toRemove.key);
	Node next = toRemove.next;
	head.next = next;
	next.prev = head;
	}
	}
	private void moveToFront(Node newNode){
	Node prev = newNode.prev;
	Node next = newNode.next;
	prev.next = next;
	next.prev = prev;
	addToFront(newNode);
	}
	private void addToFront(Node newNode){
	Node prev = tail.prev;
	prev.next = newNode;
	newNode.prev = prev;
	tail.prev = newNode;
	newNode.next = tail;
	}
	}
	class Node{
	int key;
	int val;
	Node prev;
	Node next;
	public Node(int key, int val){
	this.key = key;
	this.val = val;
	}
	}
	/**
	* Your LRUCache object will be instantiated and called as such:
	* LRUCache obj = new LRUCache(capacity);
	* int param_1 = obj.get(key);
	* obj.put(key,value);
	*/

view raw LRUCache.java hosted with ❤ by GitHub