30daychallenge (24) | LRU Cache

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.

get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(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.

The cache is initialized with a positive capacity.

Follow up:
Could you do both operations in O(1) time complexity?

Đây là một bài toán cực kỳ hay và tôi đã chinh phục được nó trong một buổi tối, toàn sai mấy cái không đáng có. LRU - Least Recently Used Cache, ta sẽ loại bỏ khỏi Cache phần từ lâu chưa được dùng tới nhất. Thao tác get(key) và put(key,value), chúng ta sẽ dùng hai cấu trúc dữ liệu Doubly Linked List và HashTable theo tôi tìm hiểu là tối ưu nhất thời điểm này. Phần tử đầu list chính là phần tử lâu chưa được dùng tới nhất. Nếu có một thay đổi trên nốt, ta sẽ đẩy nó về tail đánh dấu nó vừa được cập nhật.

Dựa theo hình ảnh trên Wiki này sẽ giúp ta dễ hình dung công dụng của LRU hơn.

Mấu chốt để bài này đạt O(1) nằm ở việc sử dụng HashMap, còn nếu bạn đã cài đặt thành thạo Doubly Linked List thì bài này không thực sự khó đối với bạn.

	//duynotes.blogspot.com
	class Node{
	private Node prev;
	private Node next;
	private int key;
	private int value;
	Node(int key, int val){
	this.key = key;
	this.value = val;
	}
	public Node getPrev(){return prev;}
	public void setPrev(Node prev){ this.prev = prev;}
	public Node getNext(){return next;}
	public void setNext(Node next){ this.next = next;}
	public int getKey(){return key;};
	public void setKey(int key){this.key = key;}
	public int getValue(){return value;}
	public void setValue(int value){this.value = value;}
	}
	class LRUCache {
	private Node head;
	private Node tail;
	private HashMap<Integer,Node> map;
	int cap = 0;
	public LRUCache(int capacity) {
	this.cap = capacity;
	map = new HashMap<>();
	}
	public int get(int key) {
	if (map.get(key) == null){
	return -1;
	}
	Node node = map.get(key);
	remove(node);
	addTail(node);
	return node.getValue();
	}
	public void remove (Node node){
	if (node.getPrev() != null){
	node.getPrev().setNext(node.getNext());
	}
	else{
	head = node.getNext();
	}
	if (node.getNext()!=null){
	node.getNext().setPrev(node.getPrev());
	}
	else{
	tail = node.getPrev();
	}
	}
	public void addTail(Node node){
	if (tail!=null){
	tail.setNext(node);
	}
	node.setPrev(tail);
	node.setNext(null);
	tail = node;
	if (head == null){
	head = tail;
	}
	}
	public void put(int key, int value) {
	if (map.get(key) != null){
	Node node = map.get(key);
	node.setValue(value);
	remove(node);
	addTail(node);
	}else{
	if (map.size()==cap){
	map.remove(head.getKey());
	remove(head);
	}
	Node node = new Node(key,value);
	addTail(node);
	map.put(key,node);
	}
	}
	}
	/**
	* 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 delivered with ❤ by emgithub

Xin chào, cảm ơn bạn !