题意整理
- 设计一个缓存结构，实现set、get功能。
- set(key, value)：将记录(key, value)插入该结构。get(key)：返回key对应的value值。
- 缓存结构中最多存放k条记录，如果超过k条记录，则根据策略删掉一条记录。
- 删除策略为：删掉调用次数最少的记录，如果调用次数最少的记录有多条，则删掉上次调用发生最早的key。
方法一（双哈希表）
1.解题思路
- 首先定义两个Map，分别记为cache和freqMap。cache用于存储缓存，键为缓存的键，值为key、value组成的Node，freqMap用于存储频次，键为某个Node调用次数，值为对应频次的双向链表。然后定义一个变量min记录最小调用次数。
- 对于get方法，如果cache不包含对应的key，直接返回-1。如果包含，则找到对应的node，更新其调用的频次。并返回node对应的value。
- 对于set方法，如果cache不包含对应的key，并且容量达到上限容量，这时候要考虑删除一条记录。首先根据最小调用次数找到对应的双向链表，然后删掉双向链表的第一个node，同时从cache中移除掉对应的key。如果cache包含对应的key，则新建一个node，将其放入cache缓存，并在频次为1的双向链表添加该node。
图解展示：
2.代码实现
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LFU (int[][] operators, int k) {
//记录get调用的次数
int cnt=0;
for(int[] opera:operators){
if(opera[0]==2){
cnt++;
}
}
//根据cnt新建结果数组
int[] res=new int[cnt];
int id=0;
//新建缓存结构
LFUCache lfu=new LFUCache(k);
for(int[] opera:operators){
//执行set操作
if(opera[0]==1){
lfu.set(opera[1],opera[2]);
}
//执行get操作
else{
int value=lfu.get(opera[1]);
res[id++]=value;
}
}
return res;
}
}
class LFUCache{
//定义Node结构，包含一个key和一个value，并初始化调用次数freq为1
class Node{
int key;
int value;
int freq=1;
Node(int key,int value){
this.key=key;
this.value=value;
}
}
//用于存储缓存，键为缓存的键，值为key、value组成的Node
Map<Integer,Node> cache;
//用于存储频次，键为某个Node调用次数，值为对应频次的双向链表
Map<Integer,LinkedHashSet<Node>> freqMap;
//缓存的容量
int capacity;
//记录最小调用次数
int min;
//初始化
public LFUCache(int capacity){
this.capacity=capacity;
cache=new HashMap<>(capacity);
freqMap=new HashMap<>();
}
//返回key对应的value值
public int get(int key){
//如果缓存中不存在key，直接返回-1
if(!cache.containsKey(key)){
return -1;
}
//找到对应的node
Node node=cache.get(key);
//更新调用频次
freqInc(node);
return node.value;
}
//将记录(key,value)插入缓存结构
public void set(int key,int value){
//如果缓存中已经存在这个key
if(cache.containsKey(key)){
//找到对应的node，设置值为value，更新频次
Node node=cache.get(key);
node.value=value;
freqInc(node);
}
//如果缓存中不存在这个key
else{
//如果缓存的大小达到了容量capacity
if(cache.size()==capacity){
//根据策略从双向链表删掉对应的节点
Node deadNode=removeNode();
//从缓存中移除对应的key
cache.remove(deadNode.key);
}
//新建一个Node，将其放入缓存，并在双向链表添加该Node
Node newNode=new Node(key,value);
cache.put(key,newNode);
addNode(newNode);
}
}
//更新频次
public void freqInc(Node node){
//找到对应的双向链表，移除掉node
int freq=node.freq;
LinkedHashSet<Node> set=freqMap.get(freq);
set.remove(node);
//如果删掉的刚好是最小频次，并且只存在一个这样的node，需要更新min
if(freq==min&&set.size()==0){
min=freq+1;
}
//node对应的频次加1
node.freq++;
//找到node新的频次对应的双向链表
LinkedHashSet<Node> newSet=freqMap.get(node.freq);
if(newSet==null){
//如果为空，新建一个，并放到缓存
newSet=new LinkedHashSet<>();
freqMap.put(node.freq,newSet);
}
//在新的频次对应的双向链表中添加node
newSet.add(node);
}
//根据策略从双向链表删掉对应的节点
public Node removeNode(){
//找到最小频次对应的双向链表
LinkedHashSet<Node> set=freqMap.get(min);
//找到该链表中最早进来的node
Node deadNode=set.iterator().next();
//移除掉这个node
set.remove(deadNode);
return deadNode;
}
//在频次为1的链表中添加新的node
public void addNode(Node node){
//找到频次为1的链表
LinkedHashSet<Node> set=freqMap.get(1);
if(set==null){
//如果为空，新建一个并放入频次map
set=new LinkedHashSet<>();
freqMap.put(1,set);
}
//添加node，并设置min为1
set.add(node);
min=1;
}
}
3.复杂度分析
- 时间复杂度：get方法和set方法中均是复杂度级别的操作，所以时间复杂度是。
- 空间复杂度：假设缓存结构的容量为n，需要额外大小为n的cache哈希表以及最多大小为n的freqMap哈希表，所以空间复杂度为。
方法二（自定义双向链表）
1.解题思路
思路和方法一大致相同，不过使用了自定义的双向链表。需要注意的地方有：1.如何从双向链表中添加节点？2.如何从双向链表中移除指定节点？3.如何确定双向链表中最早调用的key？4.如何判断双向链表是否为空？
对于如何从双向链表中添加节点，可以通过将新node添加到head节点之后，head.next节点之前。对于如何从双向链表中移除指定节点，只需改变它的前驱的next指针和后继的pre指针即可。对于如何确定双向链表中最早调用的key，因为是从头节点后面加入的，所以最早调用的node一定是tail指针的前一个。对于如何判断双向链表是否为空，只需看head节点的next指针是否指向tail节点。
2.代码实现
import java.util.*;
public class Solution {
/**
* lfu design
* @param operators int整型二维数组 ops
* @param k int整型 the k
* @return int整型一维数组
*/
public int[] LFU (int[][] operators, int k) {
//记录get调用的次数
int cnt=0;
for(int[] opera:operators){
if(opera[0]==2){
cnt++;
}
}
//根据cnt新建结果数组
int[] res=new int[cnt];
int id=0;
//新建缓存结构
LFUCache lfu=new LFUCache(k);
for(int[] opera:operators){
//执行set操作
if(opera[0]==1){
lfu.set(opera[1],opera[2]);
}
//执行get操作
else{
int value=lfu.get(opera[1]);
res[id++]=value;
}
}
return res;
}
}
class LFUCache {
//定义Node结构，包括一个key、value对，以及freq和两个指针
class Node{
int key;
int value;
int freq=1;
Node pre;
Node next;
Node(){}
Node(int key,int value){
this.key=key;
this.value=value;
}
}
//定义双向链表结构
class DoubleLinkedList{
//头节点和尾节点
Node head;
Node tail;
//构造函数
DoubleLinkedList(){
head=new Node();
tail=new Node();
head.next=tail;
tail.pre=head;
}
//从头节点后面添加节点
public void addNode(Node node){
node.next=head.next;
head.next.pre=node;
node.pre=head;
head.next=node;
}
//移除掉指定节点
public void removeNode(Node node){
node.pre.next=node.next;
node.next.pre=node.pre;
}
}
//缓存Map
Map<Integer,Node> cache;
//频次Map
Map<Integer,DoubleLinkedList> freqMap;
//最小频次
int min;
//缓存上限容量
int capacity;
//初始化
public LFUCache(int capacity) {
cache=new HashMap<>(capacity);
freqMap=new HashMap<>();
this.capacity=capacity;
}
//返回key对应的value值
public int get(int key) {
//如果不存在key，直接返回-1
if(!cache.containsKey(key)){
return -1;
}
//找到对应node
Node node=cache.get(key);
//更新频次
freqInc(node);
return node.value;
}
//插入(key,value)记录
public void set(int key, int value) {
if(!cache.containsKey(key)){
//如果达到容量上限
if(cache.size()==capacity){
//找到min频次对应的链表
DoubleLinkedList doubleList=freqMap.get(min);
//缓存中移除频次最小的最早进来的node
cache.remove(doubleList.tail.pre.key);
//链表中移除最早进来的node
doubleList.removeNode(doubleList.tail.pre);
}
//新建一个node
Node newNode=new Node(key,value);
//放入缓存
cache.put(key,newNode);
//找到频次为1的链表
DoubleLinkedList newDoubleList=freqMap.get(1);
if(newDoubleList==null){
//如果为空，则新建一个，并放入频次Map
newDoubleList=new DoubleLinkedList();
freqMap.put(1,newDoubleList);
}
//链表中添加新node
newDoubleList.addNode(newNode);
//更新最小频次
min=1;
}
else{
//如果存在node，直接找到node，更新value和频次freq
Node node=cache.get(key);
node.value=value;
freqInc(node);
}
}
//更新频次
private void freqInc(Node node){
int freq=node.freq;
//找到node.freq对应的双向链表
DoubleLinkedList doubleList=freqMap.get(freq);
//从链表中移除node
doubleList.removeNode(node);
//如果node被移除后，链表为空，并且移除node的频次刚好等于min
if(freq==min&&doubleList.head.next==doubleList.tail){
//更新min
min=freq+1;
}
//node频次加1
node.freq++;
//找到新频次对应的双向链表
DoubleLinkedList newDoubleList=freqMap.get(node.freq);
if(newDoubleList==null){
//如果为空，则新建一个，并放入频次Map
newDoubleList=new DoubleLinkedList();
freqMap.put(node.freq,newDoubleList);
}
//在新的链表中添加这个node
newDoubleList.addNode(node);
}
}
3.复杂度分析
- 时间复杂度：get方法和set方法中均是复杂度级别的操作，所以时间复杂度是。
- 空间复杂度：假设缓存结构的容量为n，需要额外大小为n的cache哈希表以及最多大小为n的freqMap哈希表，所以空间复杂度为。
京公网安备 11010502036488号