LRU和LFU都是内存管理的页面置换算法。
LFU：最不经常使用淘汰算法（Least Frequently Used）。LFU是淘汰一段时间内，使用次数最少的页面。
LRU：最近最少使用淘汰算法（Least Recently Used）。LRU是淘汰最长时间没有被使用的页面。
LRU如下：
public class LRUCache {class Node {private int key;private int val;private Node next;Node(int key, int val) {this.key = key;this.val = val;next = null;}}public Node first = new Node(-1, 0);//头节点;public Node last=first;public int capacity;public LRUCache(int capacity) {this.capacity = capacity;}public int get(int key) {Node pre = this.first.next;Node post = this.first;while (pre != null) {if (pre.key == key) {if(this.last!=pre){post.next = pre.next;pre.next = null;this.last.next = pre;this.last = pre;}return pre.val;}pre = pre.next;post = post.next;}return -1;}public void put(int key, int value) {Node tmp = this.first.next;int count = 0;if (get(key) == -1) {while (tmp != null) {tmp = tmp.next;count++;}//System.out.println("count:"+count);if (count == this.capacity) {tmp = new Node(key, value);this.last.next= tmp;this.last=tmp;Node d = this.first.next;this.first.next = d.next;d.next = null;} else {Node N=new Node(key,value);this.last.next=N;this.last=N;}}}public void printL(){Node tmp=this.first.next;while (tmp!=null){System.out.print("("+tmp.key+","+tmp.val+")->");tmp=tmp.next;}System.out.println();}public static void main(String[] args){LRUCache cache = new LRUCache( 3 /* capacity (缓存容量) */ );cache.put(2, 2);cache.printL();cache.put(1, 1);cache.printL();System.out.println("cache.get(2):"+cache.get(2));System.out.println("cache.get(1):"+cache.get(1));cache.printL();System.out.println("cache.get(2):"+cache.get(2));cache.put(3, 3);cache.printL();cache.put(4, 4);cache.printL();System.out.println("cache.get(3):"+cache.get(3));System.out.println("cache.get(2):"+cache.get(2));System.out.println("cache.get(1):"+cache.get(1));System.out.println("cache.get(4):"+cache.get(4));}
}
LFU：
例如 leetcode
460. LFU缓存
设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
示例：
LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );cache.put(1, 1);
cache.put(2, 2);
cache.get(1); // 返回 1
cache.put(3, 3); // 去除 key 2
cache.get(2); // 返回 -1 (未找到key 2)
cache.get(3); // 返回 3
cache.put(4, 4); // 去除 key 1
cache.get(1); // 返回 -1 (未找到 key 1)
cache.get(3); // 返回 3
cache.get(4); // 返回 4来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/lfu-cache
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。题解：
import java.awt.print.Pageable;public class LFUCache {class Node {private int key;private int val;private int times;private LFUCache.Node next;Node(int key, int val,int times) {this.key = key;this.val = val;this.times = times;next = null;}}public LFUCache.Node first = new LFUCache.Node(-1, 0,0);//头节点;public int capacity;public LFUCache(int capacity) {this.capacity = capacity;}public int get(int key) {LFUCache.Node pre = this.first.next;LFUCache.Node post = this.first;while (pre != null) {if (pre.key == key) {post.next=pre.next;pre.next=null;Node tmp =this.first;while (tmp.next!=null)tmp=tmp.next;tmp.next=pre;pre.times++;return pre.val;}pre = pre.next;post = post.next;}return -1;}public void put(int key, int value) {LFUCache.Node tmp = this.first.next;Node tmpPre=this.first;int flag=0;int count = 0;while(tmp!=null){if(tmp.key==key){tmp.val=value;tmp.times++;flag=1;}tmp=tmp.next;}tmp=this.first.next;if (flag==0) {while (tmp!= null) {tmp = tmp.next;tmpPre=tmpPre.next;count++;}if (count == this.capacity) {Node pre =this.first;Node min=this.first.next;//删除元素;tmpPre=this.first;tmp=this.first.next;while (tmp!=null){if(tmp.times<min.times){pre=tmpPre;min=tmp;}tmp=tmp.next;tmpPre=tmpPre.next;}pre.next=min.next;min.next=null;tmp=this.first;while (tmp.next!=null)tmp=tmp.next;LFUCache.Node N = new LFUCache.Node(key, value,1);tmp.next=N;} else {LFUCache.Node N = new LFUCache.Node(key, value,1);tmpPre.next=N;}}}public void printL() {LFUCache.Node tmp = this.first.next;while (tmp != null) {System.out.print("(" + tmp.key + "," + tmp.val +","+tmp.times+")->");tmp = tmp.next;}System.out.println();}public static void main(String[] args) {
// ["LFUCache","put","put","get","get","get","put","put","get","get","get","get"]
//[[3],[2,2],[1,1],[2],[1],[2],[3,3],[4,4],[3],[2],[1],[4]]
// ans:[null,null,null,2,1,2,null,null,-1,2,1,4]LFUCache cache = new LFUCache(2 /* capacity (缓存容量) */);cache.put(3, 1);cache.printL();cache.put(2, 1);cache.printL();cache.put(2, 2);cache.printL();cache.put(4, 4);cache.printL();System.out.println("cache.get(2):" + cache.get(2));// System.out.println("---------------------------------");
// LFUCache cache = new LFUCache( 2 /* capacity (缓存容量) */ );
//
// cache.put(1, 1);
// cache.put(2, 2);
// cache.printL();
// System.out.println(cache.get(1));; // 返回 1
// cache.put(3, 3);
// cache.printL();// 去除 key 2
// System.out.println(cache.get(2)); // 返回 -1 (未找到key 2)
// System.out.println(cache.get(3)); // 返回 3
// cache.put(4, 4); // 去除 key 1
// cache.printL();
// System.out.println(cache.get(1)); // 返回 -1 (未找到 key 1)
// System.out.println(cache.get(3)); // 返回 3
// System.out.println(cache.get(4)); // 返回 4}
}
get,put的时间复杂度都为O(n),空间复杂度也为O(n);