首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数:38273 时间限制:C/C++ 2秒,其他语言4秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
设计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

输入

["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"        

解题思路

  1. 使用 HashMap:将 key 映射到对应的节点,这样可以在 O(1)O(1)O(1) 时间内查找元素。
  2. 使用双向链表:保存缓存的顺序,最久未使用的元素在链表的尾部,最近使用的在头部。
    • 每次访问 getset,将对应节点移动到链表头部。
    • 当缓存超出容量 capacity 时,移除链表尾部节点(最久未使用)。

实现细节

  • 构造函数 Solution(int capacity):初始化 capacity,以及 HashMap 和双向链表的头尾哨兵节点(dummy nodes),方便处理边界条件。
  • 方法 get(int key):如果 key 存在,则将该节点移动到链表头部并返回其 value;否则返回 -1
  • 方法 set(int key, int value):如果 key 已存在,则更新其 value 并移动到链表头部;否则,插入新节点到头部。若超过容量,则移除链表尾部节点。

代码实现

import java.util.HashMap;

public class Solution {

    // 定义双向链表节点
    private class Node {
        int key, value; // 键值对
        Node prev, next; // 前后指针指向前后节点

        Node(int k, int v) { // 构造方法
            this.key = k;
            this.value = v;
        }
    }

    private int capacity; // LRU 缓存的最大容量
    private HashMap<Integer, Node> map; // 存储键值对<key, Node> 的映射,用于O(1)访问
    private Node head, tail; // 双向链表的哨兵头节点和尾节点

    public Solution(int capacity) {
        this.capacity = capacity; // 初始化缓存的容量
        this.map = new HashMap<>(); // 初始化哈希表
        // 初始化双向链表的哨兵节点(不存储实际数据,方便边界操作)
        this.head = new Node(0, 0); // 头哨兵节点
        this.tail = new Node(0, 0); // 尾哨兵节点
        head.next = tail; // 初始化链表,将头尾哨兵节点相连
        tail.prev = head;
    }

    // 获取缓存中指定键的值
    public int get(int key) {
        if (map.containsKey(key)) { // 检查键是否存在
            Node node = map.get(key); // 获取对应节点
            moveToHead(node); // 将该节点移到链表头部,标记为最近使用
            return node.value; // 返回对应的值
        }
        return -1; // 不存在则返回 -1
    }

    // 插入或更新缓存中的键值对
    public void set(int key, int value) {
        if (map.containsKey(key)) { // 如果键已存在
            Node node = map.get(key); // 获取已有节点
            node.value = value; // 更新节点的值
            moveToHead(node); // 将节点移到链表头部,标记为最近使用
        } else {
            // 若键不存在,则创建新节点
            Node newNode = new Node(key, value);
            map.put(key, newNode); // 将新节点加入哈希表
            addNode(newNode); // 插入新节点到链表头部
            // 如果超过容量,移除最久未使用节点(链表尾部节点)
            if (map.size() > capacity) {
                Node tail = removeTail(); // 删除尾部节点
                map.remove(tail.key); // 从哈希表中移除对应的键
            }
        }
    }

    // 辅助方法:在链表头部添加节点
    private void addNode(Node node) {
        node.next = head.next; // 将新节点的 next 指向 head 的 next
        node.prev = head; // 新节点的 prev 指向 head
        head.next.prev = node; // 将 head 原来的 next 的 prev 指向新节点
        head.next = node; // head 的 next 指向新节点
    }

    // 辅助方法:从链表中移除节点
    private void removeNode(Node node) {
        node.prev.next = node.next; // 将 node 的前节点的 next 指向 node 的 next
        node.next.prev = node.prev; // 将 node 的后节点的 prev 指向 node 的 prev
    }

    // 辅助方法:将节点移动到链表头部(表示最近使用)
    private void moveToHead(Node node) {
        removeNode(node); // 先从链表中删除节点
        addNode(node); // 然后再添加到链表头部
    }

    // 辅助方法:移除链表尾部节点并返回该节点(最久未使用节点)
    private Node removeTail() {
        Node res = tail.prev; // 获取尾节点前的节点
        removeNode(res); // 从链表中删除
        return res; // 返回被移除的节点
    }
}

代码详解

  1. Node

    • Node 是双向链表的节点类,包含 keyvalue,以及 prevnext 指针用于双向链接。
  2. 构造方法 Solution(int capacity)

    • 初始化 capacitymap,并创建链表的 headtail 哨兵节点。
    • 通过将 head.next 指向 tailtail.prev 指向 head,形成一个空的双向链表(仅有哨兵节点)。
  3. 方法 get(int key)

    • 检查 key 是否在 map 中。
    • 如果在,则通过 moveToHead(node) 将对应节点移到链表头部,以标记该节点为最近使用。
    • 返回节点的 value
    • 如果 key 不在 map 中,则返回 -1
  4. 方法 set(int key, int value)

    • 检查 key 是否在 map 中。
      • 如果 key 已存在,更新其 value,并调用 moveToHead(node) 将节点移到链表头部。
      • 如果 key 不存在,创建新节点,并插入到链表头部。
      • 检查 map 的大小是否超过 capacity,若超过则调用 removeTail() 删除链表尾部节点,并从 map 中移除对应键。
  5. 辅助方法

    • addNode(Node node):将新节点插入到链表头部,链表更新顺序为 head <-> node <-> head.next
    • removeNode(Node node):从链表中删除指定节点。
    • moveToHead(Node node):将节点先删除,再插入链表头部,更新为最近使用。
    • removeTail():删除链表尾部节点(最久未使用节点),并返回该节点。

关键点总结

  • HashMap 作为缓存记录的快速查找结构,使得 getset 操作在 时间完成。
  • 双向链表 维护 LRU 顺序,头部表示最近使用,尾部表示最久未使用。
  • 容量管理:当超出容量时,通过 removeTail() 删除尾节点(最久未使用),并从 map 中移除。
发表于 2024-10-26 15:32:10 回复(0)
LinkedHashMap<Integer ,Integer> map;
int capacity;

public Solution(int capacity) {
    // write code here
    this.capacity=capacity;
    map=new LinkedHashMap<>(capacity);
}

public int get(int key) {
    // write code here
    if(map.containsKey(key)){
        int val=map.get(key);
        map.remove(key);
        map.put(key ,val);
        return val;
    }
    return -1;
}

public void set(int key, int value) {
    // write code here
    if(map.containsKey(key)){
        map.remove(key);
    }else if(map.size()==capacity){
        map.remove(map.keySet().iterator().next());
    }
    map.put(key ,value);
}

发表于 2024-07-13 16:26:29 回复(0)

调库

public class Solution {
    LinkedHashMap<Integer, Integer> lru;

    public Solution(int capacity) {
    // write code here
        lru = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
            @Override
            protected boolean removeEldestEntry(Map.Entry<Integer, Integer> eldest) {
                return this.size() > capacity;
            }
        };
    }

    public int get(int key) {
    // write code here
        return lru.getOrDefault(key, -1);
    }

    public void set(int key, int value) {
    // write code here
        lru.put(key, value);
    }
}
发表于 2024-07-05 15:33:25 回复(1)
import java.util.*;

public class Solution {
    private int capacity;
    private List<Integer> status;//使用频率
    private Map<Integer, Integer> map; //存数据

    public Solution(int capacity) {
        this.capacity = capacity;
        this.status = new ArrayList<Integer>();
        this.map = new HashMap<Integer, Integer>();
    }

    public int get(int key) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            return map.get(key);
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if (map.containsKey(key)) {
            status.removeIf(o->o.equals(key));
            status.add(key);
            map.put(key, value);
            return;
        } else {
            if (map.size() >= capacity) {
                map.remove(status.get(0));
                status.remove(0);
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            } else {
                status.removeIf(o->o.equals(key));
                status.add(key);
                map.put(key, value);
            }
        }
    }
}

发表于 2024-04-22 13:33:20 回复(0)
// 不想用链表,用队列可以嘛?
public class Solution {
    private Deque<Integer> queue;
    private Map<Integer, Integer> map;
    private int capacity;
    public Solution(int capacity) {
        // write code here
        queue = new ArrayDeque<>();
        map = new HashMap<>();
        this.capacity = capacity;
    }

    public int get(int key) {
        // write code here
        // 更新缓存
        if (map.containsKey(key)) {
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key); // 访问过的一律放到队头
            return map.get(key);
        }

        return -1;
    }


    public void set(int key, int value) {
        // write code here
        if (map.containsKey(key)) { // 存在就放到队头
            queue.remove(Integer.valueOf(key));
            queue.addFirst(key);
        } else { // 不存在就加入队头
            if (queue.size() == capacity) { // 容量满了,删一个
                int last = queue.getLast();
                // System.out.println(last+"-->"+map.get(key)+12);
                map.remove(last);
                queue.removeLast(); // 删掉最不常用的(队尾)
            }
            queue.addFirst(key);
        }
        map.put(key, value);
    }
}

编辑于 2024-04-19 21:52:20 回复(0)
import java.util.*;


public class Solution {
    // 缓存容量
    private int capacity;
    // 缓存链当前头节点
    private Node curHead;
    // 缓存链当前尾节点
    private Node curTail;
    // 缓存链当前长度
    private int curLen;
    // 存放缓存链的元素,便于查找,key是插入的数据的key,value是插入的数据所构成的节点Node
    private HashMap<Integer, Node> map;
    // 双向链表,记录当前缓存顺序
    class Node {
        // 需要存储的数据的key
        int key;
        // 需要存储的数据的value
        int val;
        Node pre;
        Node next;
        Node(int key, int value, Node pre, Node next) {
            this.key = key;
            this.val = value;
            this.pre = pre;
            this.next = next;
        }
    }

    public Solution(int capacity) {
// write code here
        this.capacity = capacity;
        this.curHead = null;
        this.curTail = null;
        this.curLen = 0;
        map = new HashMap<Integer, Node>();
    }

    public int get(int key) {
// write code here
        // 不存在返回-1
        if (!map.containsKey(key)) return -1;
        // 存在且该节点不是头结点,则将key对应的数据标记为最近使用,并返回数据值,
        // 通过map得到Node,再由Node得到数据值
        else {
            Node node = map.get(key);
            if (curHead != node) markRecently(node);
            return map.get(key).val;
        }
    }

    public void set(int key, int value) {
// write code here
        // 存在该节点
        if (map.containsKey(key)) {
            Node node = map.get(key);
            // 不是头结点,则更改当前节点值,将key对应的数据标记为最近使用
            if (node != curHead) {
                node.val = value;
                markRecently(node);
                // 是头结点,则更改当前节点值
            } else node.val = value;
            // 不存在该节点
        } else {
            // 如果头节点为空,则设置头结点和尾节点
            if (curHead == null) {
                // 设置头节点
                curHead = new Node(key, value, null, null);
                // 设置尾节点
                curTail = curHead;
                // 如果头节点不为空
            } else {
                // 创建该节点,并指向当前头结点
                Node node = new Node(key, value, null, curHead);
                // 将当前头节点指向该节点
                curHead.pre = node;
                // 将该节点置为当前头结点
                curHead = node;
            }
            // 当前链表长度+1
            curLen++;
            // 将当前节点加入map中
            map.put(key, curHead);
            // 如果当前链表超长,则进行末尾节点删除
            if (curLen > capacity) {
                // 删除map中的末尾节点
                map.remove(curTail.key);
                // 将链表中末尾节点的前序节点置为当前末尾节点
                curTail = curTail.pre;
                // 对末尾节点(此时的末尾节点为原末尾节点的前序节点)的后续节点置空
                curTail.next = null;
                // 当前长度-1
                curLen--;
            }
        }
    }
    // 将节点置为最近使用,即移到链表头部,已排除头部节点
    public void markRecently(Node node) {
        // 如果是末尾节点
        if (node == curTail) {
            // 将链表中末尾节点的前序节点置为当前末尾节点
            curTail = curTail.pre;
            // 对末尾节点(此时的末尾节点为原末尾节点的前序节点)的后序节点置空
            curTail.next = null;
        // 如果是中建节点
        } else {
            // 将该节点的后序节点置为该节点的前序节点的后序节点
            node.pre.next = node.next;
            // 将该节点的前序节点置为该节点的后序的前序节点
            node.next.pre = node.pre;
        }
        // 将该节点置为头结点的前序节点
        curHead.pre = node;
        // 将当前头节点置为该节点的后序节点
        node.next = curHead;
        // 当该节点置为当前头节点
        curHead = node;
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

发表于 2023-11-16 12:02:30 回复(0)
import java.util.*;

public class Solution {
    int capacity;
    // key -> Node
    Map<Integer, Node> cache;
    // lru 
    DeLinkedList lru;
    public Solution(int capacity) {
        this.capacity = capacity;
        this.cache = new HashMap<>();
        this.lru = new DeLinkedList();
    }

    public int get(int key) {
        if ( cache.containsKey(key) ) {
            Node node = cache.get(key);
            lru.remove(node);
            lru.addLast(node);
            return node.val;
        } else {
            return -1;
        }
    }

    public void set(int key, int value) {
        if ( cache.containsKey(key) ) {
            Node node = cache.get(key);
            node.val = value;
            lru.remove(node);
            lru.addLast(node);
        } else {
            Node node = new Node(key, value);
            cache.put(key, node);
            lru.addLast(node);
            // evict
            if ( cache.size() > this.capacity ) {
                Node evict = lru.removeFirst();
                cache.remove(evict.key);
            }
        }
    }
}

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

class DeLinkedList {
    // 虚拟节点
    Node head;
    Node tail;

    public DeLinkedList() {
        head = new Node();
        tail = new Node();
        head.next = tail;
        tail.pre = head;
    }

    public void addLast(Node node) {
        Node last = tail.pre;
        last.next = node;
        node.pre = last;
        node.next = tail;
        tail.pre = node;
    }

    public Node removeFirst() {
        Node remove = head.next;
        head.next = remove.next;
        remove.next.pre = head;
        return remove;
    }

    public Node remove(Node node) {
        node.pre.next = node.next;
        node.next.pre = node.pre;
        return node;
    }

}

发表于 2023-10-20 18:02:47 回复(0)
class Solution {
        int capacity = 0;
        List<Integer> list = new ArrayList<>();
        Map<Integer,Integer> mp = new HashMap<>();
        public Solution(int capacity) {
            // write code here
            this.capacity = capacity;
        }
        public int get(int key) {
            // write code here
            if(!mp.containsKey(key)){
                return -1;
            }
            list.remove(Integer.valueOf(key));
            list.add(0,key);
            return mp.get(key);
        }

        public void set(int key, int value) {
            // write code here
            if(mp.containsKey(key)){
                list.remove(Integer.valueOf(key));
                list.add(0,key);
                mp.remove(key);
                mp.put(key,value);
                return;
            }
            if(list.size() < capacity){
                list.add(0,key);
                mp.put(key,value);
            } else{
                mp.remove(list.get(capacity-1));
                list.remove(capacity - 1);
                list.add(0,key);
                mp.put(key,value);
            }
        }
    }

发表于 2023-08-22 15:32:26 回复(0)
Java语言解题明细,亲测通过
import java.util.*;

public class Solution {
   
    Map<Integer, Integer> map;

    int capacity;

    public Solution(int capacity) {
        this.capacity = capacity;
        this.map = new LinkedHashMap<>(capacity);
    }

    public int get(int key) {
      Integer value = map.get(key);
        if(value!=null){
            if(map.size()>1){
                map.remove(key); // 删除原有的key
                map.put(key, value); // 添加key到最后
            }
            return value;
        }
        return -1;
    }
   
    public void set(int key, int value) {
       // 添加key到最后
        if(map.containsKey(key)){
            map.remove(key);
        }else{
            if(map.size()+1>capacity){ // 容量达到最大
                Integer firstKey = map.keySet().iterator().next();
                map.remove(firstKey); // 删除最少使用的key
            }
        }
        map.put(key, value); // 添加key到最后
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int capacity;
        List<String> operationList = new ArrayList<>();
        List<String> dataList = new ArrayList<>();
        if(scanner.hasNext()){
            String inputLine = scanner.nextLine();
            int index = inputLine.indexOf("[[");
            if(index>-1){
                String operationStr = inputLine.substring(0, index-1);
                operationStr = operationStr.substring(1, operationStr.length()-1);
                String[] operationArray = operationStr.split(",");
                for(int i=0; i<operationArray.length; i++){
                    operationArray[i] = operationArray[i].replaceAll("\"", "");
                    operationList.add(operationArray[i]);
                }
                String dataStr = inputLine.substring(index);
                int endIndex = dataStr.lastIndexOf("]]");
                String dataNumStr = dataStr.substring(2, endIndex);
                String[] dataNumArray = dataNumStr.split("],\\[");
                for(int i=0; i<dataNumArray.length;i++){
                    System.out.println(dataNumArray[i]);
                    dataList.add(dataNumArray[i]);
                }
                String capacityStr = dataStr.substring(dataStr.length()-1);
                capacity = Integer.parseInt(capacityStr);
                StringBuilder builder = new StringBuilder();
                builder.append("[");
                Solution lruCache = new Solution(capacity);
                for(int i=0; i<operationList.size()-1; i++){
                    String operation = operationList.get(i);
                    String data = dataList.get(i);
                    if("set".equals(operation)){
                        String key = data.split(",")[0];
                        String value = data.split(",")[1];
                        lruCache.set(Integer.valueOf(key), Integer.valueOf(value));
                        builder.append("\"null\"").append(",");
                    } else {
                        Integer value = lruCache.get(Integer.valueOf(data));
                        builder.append("\"").append(value).append("\"").append(",");
                    }
                }
                String data = dataList.get(operationList.size()-1);
                if("set".equals(operationList.get(operationList.size()-1))){
                    String key = data.split(",")[0];
                    String value = data.split(",")[1];
                    lruCache.set(Integer.valueOf(key), Integer.valueOf(value));
                    builder.append("\"null\"");
                }else{
                    Integer value = lruCache.get(Integer.parseInt(data));
                    builder.append(value).append("]");
                }
                System.out.println(builder);
            }
        }
    }
}


发表于 2023-08-03 23:11:37 回复(0)
public static class BinaryNode {
        int x;
        int y;

        BinaryNode(int x, int y) {
            this.x = x;
            this.y = y;
        }

        BinaryNode next = null;
    }

    // 设计lru
    public static ArrayList<String> LRUCache(ArrayList<String> operators, ArrayList<ArrayList<Integer>> param, int capacity) {
        // write code here
        Map<Integer, BinaryNode> keyHashMap = new HashMap<Integer, BinaryNode>();
        ArrayList<String> resultList = new ArrayList<String>();
        BinaryNode firNode = new BinaryNode(-1, -1);
        for (int i = 0; i < operators.size(); i++) {
            if ("set".equals(operators.get(i))) {
                resultList.add(set(param.get(i),keyHashMap,firNode,capacity));
            } else if ("get".equals(operators.get(i))) {
                resultList.add(get(param.get(i),keyHashMap,firNode));
            }
        }
        return resultList;
    }

    public static String set(ArrayList<Integer> params, Map<Integer, BinaryNode> keyHashMap,BinaryNode firNode,int capacity) {
        Integer key = params.get(0);
        Integer value = params.get(1);
        BinaryNode node = new BinaryNode(key, value);
        // 存在 清除 队尾补齐
        if (keyHashMap.containsKey(key)) {
            removeTempNode(firNode,node);
            setBinaryNodeToLast(firNode,node);
        } else {
            // 不存在
            // 超过空间大小 清除头 队尾补齐
            if (keyHashMap.keySet().size() >= capacity) {
                keyHashMap.remove(firNode.next.x);
                removeFirNode(firNode);
                setBinaryNodeToLast(firNode,node);
            } else {
                // 未超过空间大小 队尾补齐
                setBinaryNodeToLast(firNode,node);
            }
        }
        keyHashMap.put(key,new BinaryNode(key, value));
        return "null";
    }

    public static String get(ArrayList<Integer> params, Map<Integer, BinaryNode> keyHashMap,BinaryNode firNode) {
        Integer key = params.get(0);
        // get也会默认为最常使用
        if (!keyHashMap.containsKey(key)) {
            return "-1";
        } else {
            BinaryNode node = keyHashMap.get(key);
            // 清除 放队尾
            removeTempNode(firNode,node);
            setBinaryNodeToLast(firNode,node);
            return String.valueOf(keyHashMap.get(key).y);
        }
    }

    private static void removeFirNode(BinaryNode firNode) {
        firNode.next = firNode.next.next;
    }

    public static void removeTempNode(BinaryNode firNode ,BinaryNode tempNode) {
        while (firNode.next != null) {
            if (firNode.next.x == tempNode.x) {
                firNode.next = firNode.next.next;
                return;
            }
            if (firNode.next.next == null) {
                firNode.next = null;
                return;
            }
        }
    }

    public static void setBinaryNodeToLast(BinaryNode firNode,BinaryNode lastNode) {
        while (firNode.next != null) {
            firNode = firNode.next;
        }
        firNode.next = lastNode;
    }

发表于 2023-06-30 14:03:32 回复(0)
public class Solution {
   
    //双向链表结点结构
    static class Node {
        int key;
        int val;
        Node pre;
        Node next;

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

    HashMap<Integer, Node> cache; //缓存结构
    int capacity;//最大容量
    Node head = null;//链表表头
    Node tail = null;//链表表尾

    public Solution(int capacity) {

        this.capacity = capacity;
        cache = new HashMap<>(capacity);
    }

    public int get(int key) {
        //判断缓存是否存在这个key
        if (cache.containsKey(key)) {
            //将访问的元素添加到双向链表的表头
            //添加表头元素
            Node cur = cache.get(key);
            //判断该元素是否是表头元素
            if (cur != head) {  //表头元素不移动
                cur.pre.next = cur.next;

                if (cur.next != null)//表尾元素移动需要修改尾部指针
                    cur.next.pre = cur.pre;
                else tail = cur.pre;//说明是表尾元素
                //将元素设为表头元素
                head.pre = cur;
                cur.next = head;
                cur.pre = null;
                head = cur;
            }
            return cache.get(key).val;
        }
        //没有就返回-1
        return -1;
    }

    public void set(int key, int value) {
        //如果是缓存里面的第一个元素
        if (head == tail && head == null) {

            Node cur = new Node(key, value); //构造链表结点
            cache.put(key, cur); //将结点加入缓存
            head = cur;//表头表尾指向该结点
            tail = cur;
        } else {
            //将新添加的元素加入表头
            Node cur = null;
            if (cache.containsKey(key)) {//如果缓存里有key,则更新该key的value值
                cur = cache.get(key);
                cur.val = value;
            } else {
                cur = new Node(key, value);
                if (capacity ==
                        cache.size()) { //如果缓存溢出,删除表尾元素,并将新元素添加进表头
                    //删除表尾元素
                    cache.remove(tail.key);
                    tail = tail.pre;
                    tail.next = null;

                }
            }
            cache.put(key, cur);//将新元素放入缓存
            //添加表头元素
            head.pre = cur;
            cur.next = head;
            head = cur;

        }
    }
}

发表于 2023-06-13 17:00:00 回复(0)
LinkedList<Integer> list = new LinkedList();
    HashMap<Integer,Integer> map = new HashMap();
    final int max ;
    public Solution(int capacity) {
         this.max = capacity;
    }

    public int get(int key) {
        if ( !map.containsKey(key) ){
            return -1;
        }
         list.remove(new Integer(key));
         list.add(key);
         return map.get(key);
    }

    public void set(int key, int value) {         
         if (map.get(key) !=null ){
            list.remove(new Integer(key));
         }
         if ( map.size() == max  ) {
            Integer rk = list.removeFirst();
            map.remove(rk);
         }
         list.add(key);
         map.put(key,value);
    }


发表于 2023-04-20 19:29:42 回复(0)
//标着困难没想到出奇的简单
import java.util.*;
class Node {
    int key = 0;
    int value = 0;
    Node next = null;
}

public class Solution {
    int n = 0;
    int capacity;
    LinkedList<Node> list = new LinkedList<>();
    public Solution(int capacity) {
        this.capacity = capacity;
    }

    public int get(int key) {
        int a;
        if (find(key) == -1) return -1;
        else {
            a = list.get(find(key)).value;
            Node node = list.get(find(key));
            list.remove(find(key));
            list.addFirst(node);
            return a;
        }
    }

    public void set(int key, int value) {
        n++;
        if (n > capacity) {
            list.removeLast();
        }
        if (find(key) == -1) {
            Node node = new Node();
            node.key = key;
            node.value = value;
            list.addFirst(node);
        } else {
            list.get(find(key)).value = value;
        }
    }
    public int find(int key) {
        for (int i = 0 ; i < list.size(); i++) {
            if (list.get(i).key == key) return i;
        }
        return -1;
    }
}

发表于 2023-03-20 23:24:28 回复(0)
这道题非常有意思,map 与 链表的组合之前都没有遇到过,值得深思
import java.util.*;


public class Solution {
    public static class Node {
        int key;
        int val;
        Node pre;
        Node next;
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
            this.pre = null;
            this.next = null;
        }
    }
    public Map<Integer, Node> mp = new HashMap<>();
    public Node head = new Node(-1, -1);
    public Node tail = new Node(-1, -1);
    public int size = 0;


    public Solution(int capacity) {
        // write code here
        size = capacity;
        head.next = tail;
        tail.pre = head;

    }
    public void removeLast() {
        mp.remove(tail.pre.key);
        tail.pre.pre.next = tail;
        tail.pre = tail.pre.pre;
    }
    public int get(int key) {
        // write code here
        int res = -1;
        if (mp.containsKey(key)) {
            Node node = mp.get(key);
            res = node.val;
            moTohead(node);
        }
        return res;
    }
    public void moTohead(Node node) {
        if (node.pre == head)return;
        Node pre = node.pre;
        Node next = node.next;
        Node first = head.next;
        pre.next = next;
        next.pre = pre;
        head.next = node;
        node.pre = head;
        node.next = first;
        first.pre = node;

    }

    public void set(int key, int value) {
        // write code here
        if (!mp.containsKey(key)) {
            Node node = new Node(key, value);
            mp.put(key, node);
            if (size <= 0) removeLast();
            else size--;
            Node first = head.next;
            head.next = node;
            node.pre = head;
            node.next = first;
            first.pre = node;
        } else {
            mp.get(key).val = value;
            //访问过后,移到表头
            moTohead(mp.get(key));

        }
    }
    
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */


发表于 2022-10-06 17:02:06 回复(0)
细节问题太多了
import java.util.*;


public class Solution {
 
    Map<Integer,Node> map;
    int size;
    Node head;
    Node tail;
    int now;
    public Solution(int capacity) {
        this.size=capacity;
        map=new HashMap<>();
        head=new Node();
        tail=head;
        this.now=0;
    }

    public int get(int key) {
        if(map.containsKey(key)){
            //更新
            Node node=map.get(key);
            int res=node.val;
            if(tail!=node){
                updateTail(node);
            }
      
            
            return res;
        }else{
            return -1;
        }
    }
    
    //添加到末尾
    public void updateTail(Node node  ){
        //更新链表
        Node pre=node.pre;
        //更新双向链表
        pre.next=pre.next.next;
        pre.next.pre=pre;
        

        tail.next=node;
        node.pre=tail;
        
        node.next=null;

        tail=tail.next;
    }

    public void set(int key, int value) {
   
        if(map.containsKey(key)){
            Node node=map.get(key);
            node.val=value;
            if(tail!=node){
                updateTail(node);
            }
            
        }else{
            if(now>=size){
              //需要移除
              int target=head.next.key;
              
              head.next=head.next.next;
              head.next.pre=head;
                
  
              map.remove(target);//移除hash节点
              now--;
            } 
            now++;
            Node node=new Node(key,value);
            tail.next=node;
            node.pre=tail;

            tail=tail.next;
            map.put(key,node);
        }
        
         
    }
    
    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 Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */


发表于 2022-09-04 21:11:23 回复(0)
import java.util.*;

public class Solution {
    class Node {
        public int key;
        public int val;
        public Node pre;
        public Node next;

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

    private HashMap<Integer, Integer> entity;
    private Node head;
    private Node tail;
    private int capacity;
    private int size;

    public Solution(int capacity) {
        // write code here
        this.capacity = capacity;
        this.size = 0;
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        this.head.next = this.tail;
        this.tail.pre = this.head;
        this.entity = new HashMap<>();
    }

    public int get(int key) {
        // write code here
        Integer val = entity.get(key);
        if (val == null) {
            return -1;
        }

        removeNode(key, val);
        insertHead(new Node(key, val));

        return val;
    }

    public void set(int key, int value) {
        // write code here
        Integer oldVal = entity.put(key, value);
        if (oldVal == null) {
            if (this.size == this.capacity) {
                removeLast();
            } else {
                this.size++;
            }
        }

        if (oldVal != null) {
            removeNode(key, oldVal);
            this.entity.remove(key, oldVal);
        }

        insertHead(new Node(key, value));
    }

    private void removeNode(int key, int val) {
        if (this.size == 0) {
            return;
        }

        Node node = this.head.next;
        while (node != null) {
            if (node.key == key && node.val == val) {
                Node pre = node.pre;
                Node next = node.next;
                pre.next = next;
                next.pre = pre;
                break;
            } else {
                node = node.next;
            }
        }
    }

    private void insertHead(Node node) {
        Node tmp = this.head.next;
        node.next = tmp;
        tmp.pre = node;
        node.pre = this.head;
        this.head.next = node;
    }

    private void removeLast() {
        if (this.size == 0) {
            return;
        }

        Node node = this.tail.pre;
        Node pre = node.pre;
        pre.next = this.tail;
        this.tail.pre = pre;
        node.next = null;
        node.pre = null;
        this.entity.remove(node.key, node.val);
    }
}
严格限制 size 的变动在 set 方法中进行,hashmap 中的元素删除操作,在 set 方法中进行,removeTail 删除尾节点方法允许删除 hashmap 的元素。
发表于 2022-09-01 21:55:29 回复(0)
在力扣那边学到的思路,和牛客上要求略有区别,但是思路应该是对的
import java.util.*;


public class Solution {
    class DLinkedNode{
        int key,value;
        DLinkedNode pre,next;
        public DLinkedNode(){}
        public DLinkedNode(int key1,int value1){
            key=key1;
            value=value1;
        }
    }
    int size,capacity;
    Map<Integer,DLinkedNode> map=new HashMap<Integer,DLinkedNode>();
    DLinkedNode dummyhead,dummytail;
    
    
    public Solution(int capacity) {
        this.size=size;
        this.capacity=capacity;
        dummyhead=new DLinkedNode();
        dummyhead=new DLinkedNode();
        dummyhead.next=dummytail;
        dummytail.pre=dummyhead;
         // write code here
    }

    public int get(int key) {
         // write code here
        if(map.containsKey(key)){
            DLinkedNode node=map.get(key);
            moveTohead(node);
            return node.value;
        }else{return -1;}
    }

    public void set(int key, int value) {
         // write code here
        if(map.containsKey(key)){
            DLinkedNode node=map.get(key);
            moveTohead(node);
            node.value=value;
        }else{
            DLinkedNode node=new DLinkedNode(key,value);
            addTohead(node);
            size=size+1;
            if(size>capacity){
                DLinkedNode tail=dummytail.pre;
                removeNode(tail);
                size=size-1;
                map.remove(tail.key);
            }
        }
    }
    public void addTohead(DLinkedNode node){
        node.pre=dummyhead;
        node.next=dummyhead.next;
        dummyhead.next.pre=node;
        dummyhead.next=node;
    }
    public void removeNode(DLinkedNode node){
        node.next.pre=node.pre;
        node.pre.next=node.next;
    }
    public void moveTohead(DLinkedNode node){
        removeNode(node);
        addTohead(node);
    }
}

/**
 * Your Solution object will be instantiated and called as such:
 * Solution solution = new Solution(capacity);
 * int output = solution.get(key);
 * solution.set(key,value);
 */

发表于 2022-08-26 19:50:48 回复(0)