146. LRU 缓存

1. LRU 缓存

https://leetcode.cn/problems/lru-cache/description/

2. 代码实现

class LRUCache {
    int capacity;
    HashMap<Integer,Node> table;
    LinkedList<Integer> queue;
    Node head,tail;
    int size=0;
    public LRUCache(int capacity) {
        this.capacity=capacity;
        this.table=new HashMap<>();
        this.queue=new LinkedList<>();
        this.head=new Node();
        this.tail=new Node();
        this.head.next=this.tail;
        this.tail.pre=this.head;
    }
    
    public int get(int key) {
        if(!table.containsKey(key)){
            return -1;
        }
        // 返回该节点对应值
        Node node=table.get(key);
        int val=node.val;
        // 删除该节点
        removeNode(node);
        // 将该节点插入到队列末尾
        addToTail(node);
        return val;
    }
    
    // 从队列中移除节点
    public void removeNode(Node node){
        size--;
        Node left=node.pre,right=node.next;
        left.next=right;
        right.pre=left;
    }

    // 将节点添加到队列末尾
    public void addToTail(Node node){
        size++;
        Node last=tail.pre;
        last.next=node;
        node.pre=last;
        node.next=tail;
        tail.pre=node;
    }

    public void put(int key, int value) {
        // 查看该值是否存在
        if(get(key)!=-1){
            // 更新
            table.get(key).val=value;
            return;
        }
        // 判断容量是否超过阈值
        Node node=new Node(key,value);
        table.put(key,node);
        // System.out.println(size+" "+capacity);
        if(size==capacity){
            // 如果超过则删除最近最少 使用的节点
            int k=head.next.key;
            removeNode(head.next);
            table.remove(k);
        }
        // 将新的节点插入到队列末尾
        addToTail(node);
        // printList(head);
    }

    void printList(Node node){
        Node temp=head.next;
        while(temp!=tail){
            System.out.print(temp.val+" ");
            temp=temp.next;
        }
        System.out.println();
    }

    class Node{
        int key;
        int val;
        Node pre;
        Node next;
        public Node(){
        }

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

/**
 * Your LRUCache object will be instantiated and called as such:
 * LRUCache obj = new LRUCache(capacity);
 * int param_1 = obj.get(key);
 * obj.put(key,value);
 */
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