前言：由于在公司工作比较繁忙，导致之前刷的算法题忘记了许多，因此最近要大量回顾之前刷过的算法题，旨在有利于自己更好的复习，想跟着学习或复习的小伙伴儿们也可以参考一下🤞🤞
如果有什么需要改进的地方还请大佬斧正😁
小威在此先感谢诸佬了👏👏

🏠个人主页：小威要向诸佬学习呀
🧑个人简介：大家好，我是小威，一个想要与大家共同进步的男人😉😉
目前状况🎉：目前大二，在一家满意的公司实习👏👏

🎁如果大佬在准备面试，找工作，刷算法，可以使用我找实习前用的刷题神器哦刷题神器点这里哟
💕欢迎大家：这里是CSDN，我总结知识的地方，欢迎来到我的博客，我亲爱的大佬😘

牛客部分使用反馈，个人感觉还不错，帮我找到了心仪的公司，希望各位伙伴儿们通过它也能提高不少🥂🥂🥂

以下正文开始

LRU缓存

题目：

请你设计并实现一个满足 LRU (最近最少使用) 缓存 约束的数据结构。
实现 LRUCache 类：
LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。
void put(int key, int value) 如果关键字 key 已经存在，则变更其数据值 value ；如果不存在，则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ，则应该 逐出 最久未使用的关键字。
函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例：

输入 [“LRUCache”, “put”, “put”, “get”, “put”, “get”, “put”, “get”,“get”, “get”]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出 [null, null, null, 1, null, -1, null, -1, 3, 4]

解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4

题解：此题用哈希链表，即哈希表和链表的形式比较高效一些，创建链表形式的哈希表，HashMap，map中的key和ListNode中的key相对应。

代码+详解：

class LRUCache {
    ListNode head;
    ListNode tail;
    int sum =0;
    int capacity=0;
    HashMap<Integer,ListNode> map = new HashMap<>();//双向链表的HashMap集合
    public LRUCache(int capacity) {
        head = new ListNode();
        tail = new ListNode();
        tail.pre = head;
        head.next = tail;
        this.capacity = capacity;
    }
    public int get(int key){
        ListNode node = map.get(key); //从map集合中取出数据;
        if(node==null){  //如果map集合中无数据则返回-1;
            return -1;
        }else{
             moveToHead(node); //有数据就代表使用过了该数据，将数据移动到前面并返回;
             return node.value;
        }

    }

    public void moveToHead(ListNode node){
        // 断开node结点，使得node前面和后面的结点相连
        node.pre.next=node.next;
        node.next.pre=node.pre;
        //由于是双向链表，先将node插入head 和head的下一个的中间，即node与head和head.next节点相连
        node.pre=head;
        node.next=head.next;
        //这一步是将head，head的下一个节点与node相连
        head.next.pre=node;
        head.next=node;
    }

    public void put (int key,int value){
        ListNode cc=map.get(key);
        if(cc==null){
            ListNode node =new ListNode(key,value);
            map.put(key,node);
            //老样子，先让node指向head和head.next节点
            node.pre=head;
            node.next=head.next;
            //下面位置不能互换，如果先让head指向node的话，就找不到原本head的下一个节点了
            head.next.pre=node;
            head.next=node;
            sum++;
            if(sum>capacity){//如果当前节点数量大于容量
                map.remove(tail.pre.key);//移除末尾的键值对
                tail.pre.pre.next=tail;//让尾指针的上上一位连接尾指针
                tail.pre=tail.pre.pre;//互相连接
                sum--;
            }
        }else{
            cc.value=value;
            moveToHead(cc);
        }
    }
    // 自己定义ListNode的类
    class ListNode{
        int key,value;
        ListNode next,pre;
        ListNode(){  //无参构造
        }
        ListNode (int key,int value){ //有参构造
            this.key=key;
            this.value=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