2020-4-5

460.LFU缓存

✒解题思路：

1. 使用堆（优先队列）存放节点的使用频次
2. 将频次作为map的key，每个频次对应一个节点链表，并且节点进入链表有先后顺序

//使用PriorityQueue
class LFUCache {

	Map<Integer, Node> cache;
	Queue<Node> queue;
	int capacity;
	int size;
	int time = 0;

	public LFUCache(int capacity) {
		cache = new HashMap<>(capacity);
		if (capacity > 0) {
			queue = new PriorityQueue<>(capacity);
		}
		this.capacity = capacity;
	}

	public int get(int key) {
		if (!cache.containsKey(key)) {
			return -1;
		}
		Node node = cache.get(key);
		node.freq++;
		node.time = time++;
		queue.remove(node);
		queue.offer(node);
		return node.val;
	}

	public void put(int key, int value) {
		if (capacity == 0) {
			return;
		}
		Node node = cache.get(key);
		if (node != null) {
			node.val = value;
			node.freq++;
			node.time = time++;
			queue.remove(node);
			queue.add(node);
		} else {
			if (size == capacity) {
				cache.remove(queue.peek().key);
				queue.poll();
				size--;
			}
			Node newNode = new Node(key, value, time++);
			cache.put(newNode.key, newNode);
			queue.offer(newNode);
			size++;
		}
    }
}
class Node implements Comparable<Node> {
    
	int key;
	int val;
	int freq;
	int time;

	Node(int key, int val, int time) {
		this.key = key;
		this.val = val;
		freq = 1;
		this.time = time;
	}

	@Override
	public int compareTo(Node node) {
		int diff = freq - node.freq;
		return diff != 0 ? diff : time - node.time;
	}
}
/**
 * Your LFUCache object will be instantiated and called as such:
 * LFUCache obj = new LFUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */

//使用LinkedHashSet
class LFUCache {

	Map<Integer, Node> cache;
	Map<Integer, LinkedHashSet<Node>> freSet;
	int capacity;
	int size;
	int min = 1;

	public LFUCache(int capacity) {
		cache = new HashMap<>(capacity);
		freSet = new LinkedHashMap<>(capacity);
		this.capacity = capacity;
	}

	public int get(int key) {
		if (!cache.containsKey(key)) {
			return -1;
		}
		Node node = cache.get(key);
		freqInc(node);
		return node.val;
	}

	public void put(int key, int value) {
		if (capacity == 0) {
			return;
		}
		Node node = cache.get(key);
		if (node != null) {
			node.val = value;
			freqInc(node);
		} else {
			if (size == capacity) {
				Node deadNode = getDeadNode();
				cache.remove(deadNode.key);
				size--;
	    	}
			Node newNode = new Node(key, value);
			cache.put(key, newNode);
			addNode(newNode);
			size++;
		}
	}

	private void addNode(Node newNode) {
		LinkedHashSet<Node> set = freSet.get(1);
		if (set == null) {
			set = new LinkedHashSet<>();
		}
		set.add(newNode);
		freSet.put(1, set);
		min = 1;
	}

	private Node getDeadNode() {
		LinkedHashSet<Node> set = freSet.get(min);
		Node deadNode = set.iterator().next();
		set.remove(deadNode);
		return deadNode;
	}

	private void freqInc(Node node) {
		int freq = node.freq;
		LinkedHashSet<Node> set = freSet.get(freq);
		set.remove(node);
		if (freq == min && set.isEmpty()) {
			min++;
		}
		node.freq++;
		LinkedHashSet<Node> newSet = freSet.get(freq + 1);
		if (newSet == null) {
			newSet = new LinkedHashSet<>();
			freSet.put(freq + 1, newSet);
		}
		newSet.add(node);
	}
}

class Node {
	int key;
	int val;
	int freq = 1;

	Node(int key, int val) {
		this.key = key;
		this.val = val;
	}
}