LFU缓存[leetcode算法题]_newlfucache 参数

LFU缓存

//设计并实现最不经常使用（LFU）缓存的数据结构。它应该支持以下操作：get 和 put。
//
// get(key) - 如果键存在于缓存中，则获取键的值（总是正数），否则返回 -1。
//put(key, value) - 如果键不存在，请设置或插入值。当缓存达到其容量时，它应该在插入新项目之前，使最不经常使用的项目无效。在此问题中，当存在平
//局（即两个或更多个键具有相同使用频率）时，最近最少使用的键将被去除。
//
// 进阶：
//你是否可以在 O(1) 时间复杂度内执行两项操作？
//
// 示例：
//
//
//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
// Related Topics 设计

思路

设计一种数据结构：双向链表，具有头链表和尾链表不存放结点，中间的链表中存放结点，每一条链表代表特定使用频率的结点的集合。每一条链表有头部和尾部，当头部指向尾部时代表链表为空。使用频率越高则链表在越接近头链表。在链表中增加结点时增加在链表的头部之后。故删除结点时删除lastDoublyLinkedList.pre.tail.pre,这个结点是使用频率最低最久之前访问的，实现了增加删除操作的o（1）时间复杂度。

实现

package leetcode;
import java.util.HashMap;
import java.util.Map;

public class Demo15 {
    public static void main(String[] args) {
        LFUCache lfuCache = new LFUCache(1);
        lfuCache.put(2,1);
        System.out.println(lfuCache.get(2));
    }
}



class LFUCache {
    int size;
    int cap;
    Map<Integer, Node> hm;
    DoblyLinkedList firstDoblyLinkedList;
    DoblyLinkedList lastDoblyLinkedList;//lastLinkedList.pre 是频次最小的双向链表，满了之后删除 lastLinkedList.pre.tail.pre 这个Node即为频次最小且访问最早的Node
    public LFUCache(int capacity) {
        hm = new HashMap<>(capacity);
        firstDoblyLinkedList = new DoblyLinkedList(999);
        lastDoblyLinkedList = new DoblyLinkedList(999);
        firstDoblyLinkedList.post = lastDoblyLinkedList;
        lastDoblyLinkedList.pre = firstDoblyLinkedList;
        this.cap = capacity;
    }

    public int get(int key) {
        Node node = hm.getOrDefault(key,null);
        if (node==null){return -1;}
        freqInc(node);//访问次数加一
        return node.value;
    }

    public void put(int key, int value) {
        if (cap==0){return;}
        Node node = hm.get(key);
        if (node!=null){//如果值不为空，则说明键在内存中,只需要修改value
            node.value=value;
            freqInc(node);
        }else {
            if (size==cap){//内存满了
                System.out.println("你删除了:"+lastDoblyLinkedList.pre.tail.pre.key+","+lastDoblyLinkedList.pre.tail.pre.value);
                hm.remove(lastDoblyLinkedList.pre.tail.pre.key);//在hm里面删除结点的主键
                lastDoblyLinkedList.removeNode(lastDoblyLinkedList.pre.tail.pre);//删除频率最低里面访问次数最少的结点
                size--;
                if (lastDoblyLinkedList.pre.head.post==lastDoblyLinkedList.pre.tail){//如果链表为空了则删除链表
                    removeDoublyLinkedList(lastDoblyLinkedList.pre);
                }
            }

            //增加新的node值到hm中
            Node node1 = new Node(key,value);
            hm.put(key,node1);
            //把结点添加到访问此数为1的链表，如果不存在则创建
            if (lastDoblyLinkedList.pre.freq!=1){
                DoblyLinkedList doblyLinkedList = new DoblyLinkedList(1);
                addDoublyLinkedList(doblyLinkedList,lastDoblyLinkedList.pre);
                doblyLinkedList.addNode(node1);
            }else {
                lastDoblyLinkedList.pre.addNode(node1);
            }
            size++;
        }

    }

    //节点的频率增加，变换所在双向链表
    void freqInc(Node node){
        DoblyLinkedList doblyLinkedList1 = node.doblyLinkedList;
        DoblyLinkedList pre = node.doblyLinkedList.pre;
        //在原来的链表中删除原来的节点
        doblyLinkedList1.removeNode(node);
        //如果链表为空了则删除原来所在的链表
        if (doblyLinkedList1.head.post==doblyLinkedList1.tail){
            removeDoublyLinkedList(doblyLinkedList1);
        }

        //把结点增加到频率加一的链表中
        ++node.freq;
//        DoblyLinkedList doblyLinkedList=node.doblyLinkedList;
        //如果对应频率的链表不存在，则增加链表
        if (pre.freq!=node.freq){
            DoblyLinkedList newDoblyLinkedList=new DoblyLinkedList(node.freq);
            addDoublyLinkedList(newDoblyLinkedList,pre);
            newDoblyLinkedList.addNode(node);
        }else{
            doblyLinkedList1.pre.addNode(node);
        }

    }


    void addDoublyLinkedList(DoblyLinkedList newDoublyLinedList, DoblyLinkedList preLinkedList) {

        newDoublyLinedList.post = preLinkedList.post;

        newDoublyLinedList.post.pre = newDoublyLinedList;

        newDoublyLinedList.pre = preLinkedList;

        preLinkedList.post = newDoublyLinedList;
        System.out.println("你把频率为"+newDoublyLinedList.freq+"的链表增加在了频率为"+preLinkedList.freq+"的链表之后");

    }
    //删除某一链表的方法
    void removeDoublyLinkedList(DoblyLinkedList doblyLinkedList){
        doblyLinkedList.pre.post=doblyLinkedList.post;
        doblyLinkedList.post.pre=doblyLinkedList.pre;
        System.out.println("你删除了频率为"+doblyLinkedList.freq+"的链表");
    }
    }


class DoblyLinkedList{
    int freq;
    DoblyLinkedList pre;
    DoblyLinkedList post;
    Node head;
    Node tail;

    //两个构造函数
    public DoblyLinkedList() {
        this.head=new Node();
        this.tail=new Node();
        head.post=tail;
        tail.pre=head;
    }
    public DoblyLinkedList(int freq) {
        this.head=new Node();
        this.tail=new Node();
        head.post=tail;
        tail.pre=head;
        this.freq = freq;
    }
    //在链表里面的头部增加一个节点
    public void addNode(Node node){
        node.post=head.post;
        node.pre=head;
        head.post.pre=node;
        head.post=node;
        node.doblyLinkedList=this;
        System.out.println("你把"+node.key+"放入了频率为"+this.freq+"的表中");

    }
    public void removeNode(Node node){
        node.pre.post=node.post;
        node.post.pre=node.pre;
        System.out.println("你把"+node.key+"从"+node.doblyLinkedList.freq+"频率的表中删除了");
    }

}

class Node{//每一个不同调用次数的链表由相同调用次数的node构成，一条链表前面的是最近被调用的
    int value;
    int key;
    int freq=1;//节点所在双向链表的调用次数
    DoblyLinkedList doblyLinkedList;//所在链表
    Node pre;
    Node post;

    public Node() {
    }

    public Node(int key, int value) {
        this.value = value;
        this.key = key;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171