NC93 设计LRU缓存结构

题目链接：https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84

题目描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 capacity ，操作次数是 n ，并有如下功能:

1.Solution(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
2.get(key)：如果关键字 key 存在于缓存中，则返回key对应的value值，否则返回 -1 。
3.set(key, value)：将记录(key, value)插入该结构，如果关键字 key 已经存在，则变更其数据值 value，如果不存在，则向缓存中插入该组 key-value ，如果key-value的数量超过capacity，弹出最久未使用的key-value

提示:
1.某个key的set或get操作一旦发生，则认为这个key的记录成了最常使用的，然后都会刷新缓存。
2.当缓存的大小超过capacity时，移除最不经常使用的记录。
3.返回的value都以字符串形式表达，如果是set，则会输出"null"来表示(不需要用户返回，系统会自动输出)，方便观察
4.函数set和get必须以O(1)的方式运行
5.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

数据范围:

1 ≤ capacity ≤ 10^5
0 ≤ key,val ≤ 2×10^9
1≤ n ≤ 10^5

示例 1：

输入：["set","set","get","set","get","set","get","get","get"],[[1,1],[2,2],[1],[3,3],[2],[4,4],[1],[3],[4]],2
返回值：["null","null","1","null","-1","null","-1","3","4"]
说明：我们将缓存看成一个队列，最后一个参数为2代表capacity，所以
Solution s = new Solution(2);
s.set(1,1); //将(1,1)插入缓存，缓存是{"1"=1}，set操作返回"null"
s.set(2,2); //将(2,2)插入缓存，缓存是{"2"=2，"1"=1}，set操作返回"null"
output=s.get(1);// 因为get(1)操作，缓存更新，缓存是{"1"=1，"2"=2}，get操作返回"1"
s.set(3,3); //将(3,3)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"3"=3，"1"=1}，set操作返回"null" 
output=s.get(2);// 因为get(2)操作，不存在对应的key，故get操作返回"-1"
s.set(4,4); //将(4,4)插入缓存，缓存容量是2，故去掉某尾的key-value，缓存是{"4"=4，"3"=3}，set操作返回"null" 
output=s.get(1);// 因为get(1)操作，不存在对应的key，故get操作返回"-1"
output=s.get(3);//因为get(3)操作，缓存更新，缓存是{"3"=3，"4"=4}，get操作返回"3"
output=s.get(4);//因为get(4)操作，缓存更新，缓存是{"4"=4，"3"=3}，get操作返回"4"

解题代码

import java.util.*;

public class Solution {
    private int capacity;  //缓存剩余容量
    private Map<Integer, Node> map; //哈希表
    private Node head; //链表头
    private Node tail; //链表尾

    class Node {  //节点类
        int key;
        int value;
        Node pre;
        Node next;

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

    public Solution(int capacity) {//构造器初始化
        this.capacity = capacity;//剩余量
        this.map = new HashMap<>();
        head = new Node(-1, -1);  //创建出链表头
        tail = new Node(-1, -1); //创建出一个链表尾 头和尾都是为了插入和删除方便
        head.next = tail;  //双向链表，头尾相连
        tail.pre = head;
    }

    public int get(int key) {
        //get方法，步骤是先到hash表里找，有的话，就拿到这个节点，然后把这个节点移动到表头， 如果没有找到，就返回-1;
        int res = -1;
        if (map.containsKey(key)) {
            Node node = map.get(key);
            res = node.value;
            moveToHead(node);
        }
        return res;
    }

    public void set(int key, int value) {
        //set方法，步骤是先到hash表里找这个节点，如果有，就更新value值，然后把这个节点移到表头
        //如果没有找到，就新建一个节点，在插入之前判断capacity剩余量，如果没有剩余量就删除表尾节点，如果有就直接插到表头。
        if (map.containsKey(key)) { //只是更新，容量不会改变
            Node node = map.get(key);
            node.value = value;  //更新value
            map.put(key, node);  //哈希表里的值也要更新
            moveToHead(node);
        } else { //插入新节点，容量减一
            Node node = new Node(key, value);
            if (capacity <= 0) { //没有容量了，要先删除尾节点
                removeTail();  //执行一次删尾动作，腾出空间
            }
            insertFirst(node); //插入节点到表头
            map.put(key, node); //map也进行更新
            capacity--;  //容量减一
        }
    }

    public void insertFirst(Node node) {
        //插入节点到表头，单独写一个函数
        node.next = head.next;
        node.pre = head;
        head.next.pre = node;
        head.next = node;
    }

    public void moveToHead(Node node) {
        //移动节点到表头,先把节点从链表断开，然后插入到表头
        node.pre.next = node.next;
        node.next.pre = node.pre;
        insertFirst(node);
    }

    public void removeTail() {
        //删除尾节点，不用接收参数，map里也要删除这个节点
        map.remove(tail.pre.key);
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
        //删除一个节点，容量加一
        capacity++;
    }
}

本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名，转载请标明出处。
最后编辑时间为: 2022/09/09 09:05:09