LeetCode 460. LFU Cache

版权声明：本文为博主原创文章，转载请注明出处，谢谢!

版权声明：本文为博主原创文章，转载请注明出处：http://blog.jerkybible.com/2017/01/17/LeetCode-460-LFU-Cache/

访问原文「LeetCode 460. LFU Cache」

题目要求

Design and implement a data structure for Least Frequently Used (LFU) 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 reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted.

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

Example:
>

LFUCache cache = new LFUCache( 2 / capacity / );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // returns 1
cache.put(3, 3); // evicts key 2
cache.get(2); // returns -1 (not found)
cache.get(3); // returns 3.
cache.put(4, 4); // evicts key 1.
cache.get(1); // returns -1 (not found)
cache.get(3); // returns 3
cache.get(4); // returns 4

题意解析

做一个符合LFU的cache，cache有两个方法，一个是get，一个是set。get的作用是从cache中获取是否存在一个值；set的作用是往cache中放一个键值对，如果cache已满，则删除应当删除的键值对然后再把新的键值对放入。

解法分析

这道题最主要的就是熟悉什么是LFU。LFU是Least Frequently Used 近期最少使用算法。即最不经常使用页置换算法，要求在页置换时置换引用计数最小的页，因为经常使用的页应该有一个较大的引用次数。但是有些页在开始时使用次数很多，但以后就不再使用，这类页将会长时间留在内存中，因此可以将引用计数寄存器定时右移一位，形成指数衰减的平均使用次数。

然后这道题要求在cache满的时候进行删除能够保持很快的速度。这里用到了java的HashMap以及双向指针，因为双向指针本身删除就很快。

解题代码

private CacheElement head = null;
   private int capacity = 0;
   private HashMap<Integer, Integer> valueHash = null;
   private HashMap<Integer, CacheElement> cache = null;
   
   public LFUCache(int _capacity) {
       capacity = _capacity;
       valueHash = new HashMap<Integer, Integer>();
       cache = new HashMap<Integer, CacheElement>();
   }
   
   public int get(int key) {
       if (valueHash.containsKey(key)) {
           refreshUsage(key);
           return valueHash.get(key);
       }
       return -1;
   }
   
   public void put(int key, int value) {
       if ( capacity == 0 ) return;
       if (valueHash.containsKey(key)) {
           valueHash.put(key, value);
       } else {
           if (valueHash.size() < capacity) {
               valueHash.put(key, value);
           } else {
               removeOne();
               valueHash.put(key, value);
           }
           addToHead(key);
       }
       refreshUsage(key);
   }
   
   private void addToHead(int key) {
       if (head == null) {
           head = new CacheElement(0);
           head.keys.add(key);
       } else if (head.count > 0) {
           CacheElement element = new CacheElement(0);
           element.keys.add(key);
           element.next = head;
           head.prev = element;
           head = element;
       } else {
           head.keys.add(key);
       }
       cache.put(key, head);      
   }
   
   private void refreshUsage(int key) {
       CacheElement element = cache.get(key);
       element.keys.remove(key);
       
       if (element.next == null) {
           element.next = new CacheElement(element.count+1);
           element.next.prev = element;
           element.next.keys.add(key);
       } else if (element.next.count == element.count+1) {
           element.next.keys.add(key);
       } else {
           CacheElement tmp = new CacheElement(element.count+1);
           tmp.keys.add(key);
           tmp.prev = element;
           tmp.next = element.next;
           element.next.prev = tmp;
           element.next = tmp;
       }

       cache.put(key, element.next);
       if (element.keys.size() == 0) remove(element);
   }
   
   private void removeOne() {
       if (head == null) return;
       int old = 0;
       for (int n: head.keys) {
           old = n;
           break;
       }
       head.keys.remove(old);
       if (head.keys.size() == 0) remove(head);
       cache.remove(old);
       valueHash.remove(old);
   }
   
   private void remove(CacheElement element) {
       if (element.prev == null) {
           head = element.next;
       } else {
           element.prev.next = element.next;
       } 
       if (element.next != null) {
           element.next.prev = element.prev;
       }
   }
   
   class CacheElement {
       public int count = 0;
       public LinkedHashSet<Integer> keys = null;
       public CacheElement prev = null, next = null;
       
       public CacheElement(int count) {
           this.count = count;
           keys = new LinkedHashSet<Integer>();
           prev = next = null;
       }
   }