描述

题目描述

设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，并有如下两个功能

1. set(key, value)：将记录(key, value)插入该结构

2. get(key)：返回key对应的value值

提示:

1.某个key的set或get操作一旦发生，认为这个key的记录成了最常使用的，然后都会刷新缓存。

2.当缓存的大小超过k时，移除最不经常使用的记录。

3.输入一个二维数组与k，二维数组每一维有2个或者3个数字，第1个数字为opt，第2，3个数字为key，value

若opt=1，接下来两个整数key, value，表示set(key, value) 若opt=2，接下来一个整数key，表示get(key)，若key未出现过或已被移除，则返回-1 对于每个opt=2，输出一个答案

4.为了方便区分缓存里key与value，下面说明的缓存里key用""号包裹

要求：set和get操作复杂度均为 O(1)

示例

输入：
[[1,1,1],[1,2,2],[2,1],[1,3,3],[2,2],[1,4,4],[2,1],[2,3],[2,4]],2
返回值：
[1,-1,-1,3,4]

知识点：模拟、数据结构、LRU

难度：⭐⭐⭐

题解

图解：

方法一：哈希

解题思路：

Java 中 LinkedHashMap 能实现类似HashMap + 链表的结构

算法流程：

• 维护一个LinkedHashMap用来保存元素，LinkedList保存get结果
• put过程：
  • 小于容量，则不考虑淘汰
  • 否则，使用迭代器，删除改map的最久未使用的key，即LinkedHashMap最末端元素
  • 同时还需要删除掉链表头部的数据，添加到map中所载链表的尾节点，尾节点表示最近使用的
• get过程
  • 如果map包含该key，则收集结果后，把该key放到map中的尾部，表示最近使用
  • 收集get的结果， 将该节点放到尾部
  • 如果不包含，则返回-1

Java 版本代码如下：

import java.util.*;

public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // 维护一个LinkedHashMap
        Map<Integer, Integer> map = new LinkedHashMap<>();
        List<Integer> list = new LinkedList<>();
        for(int[] arr : operators) {
            int key = arr[1];
            // put
            if(arr[0] == 1) {
                int val = arr[2];
                // 小于容量，则不考虑淘汰
                if(map.size() < k) {
                    map.put(key, val);
                } else {
                    // 迭代器，用来需要删除最久未使用的key
                    Iterator iter = map.keySet().iterator();
                    // 删除掉链表头部的数据
                    map.remove(iter.next());
                    // 添加到map中所载链表的尾节点
                    map.put(key, val);
                }
            } else if(arr[0] == 2) {
                // get
                // 包含该key，则收集结果后，把该key放到map中的尾部
                if(map.containsKey(key)) {
                    int val = map.get(key);
                    // 收集get的结果
                    list.add(val);
                    // 将该节点放到尾部
                    map.remove(key);
                    map.put(key, val);
                } else {
                    // key不存在或已经被移除
                    list.add(-1);
                }
            }
        }
        // List转为int[]
        int[] res = new int[list.size()];
        int i = 0;
        for(int item : list) {
            res[i++] = item;
        }
        return res;
    }
}

复杂度分析：

时间复杂度 $O(1)O(1)$：get和set都是常量操作，属于空间换时间

空间复杂度 $O(N)O(N)$：用到Map、List等结构，N为元素数量

方法二：模拟

Java 版本代码如下：

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
     // 手写类似LinkedHashMap的结构
    public class Node{
        int key;
        int value;
        Node pre = null;
        Node next = null;
        
        public Node(int k, int v){
            key = k;
            value = v;
        }
    }
    
    HashMap<Integer, Node> hashMap = new HashMap<Integer, Node>();
    // 每个key上的元素，类似链表，用头尾指针保存头尾节点
    Node head = new Node(-1,-1);
    Node tail = new Node(-1,-1);
    int count = 0;
    
    public int[] LRU (int[][] operators, int k) {
        // write code here
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(operators.length == 0 || operators[0].length == 0){
            return new int[]{};
        }
        head.next = tail;
        tail.pre = head;
        for(int i = 0; i < operators.length; i++){
            if(operators[i][0] == 1){
                set(operators[i][1], operators[i][2], k);
            }else{
                res.add(get(operators[i][1]));
            }
        }
        
        int[] result = new int[res.size()];
        for(int i = 0 ; i < res.size(); i++){
            result[i] = res.get(i);
        }
        return result;
    }
    
    // put过程
    private void set(int key, int value, int k){
        if(get(key) != -1){
            hashMap.get(key).value = value;
        }else{
            Node node  = new Node(key, value);
            hashMap.put(key, node);
            // 放到头节点
            putHead(node);
            if(count < k){
                count++;
            }else{
                int deleteKey = tail.pre.key;
                tail.pre.pre.next = tail;
                tail.pre = tail.pre.pre;
                hashMap.remove(deleteKey);
            }
        }
    }
    
    private int get(int key){
        if(hashMap.containsKey(key)){
        	// 如果map包含该key，则收集结果后，把该key放到map中的头部，表示最近使用
            Node node = hashMap.get(key);
            Node pre = node.pre;
            Node next = node.next;
            pre.next = next;
            next.pre = pre;
            putHead(node);
            return node.value;
        }else{
            return -1;
        }
    }
    
    // 把该key放到map中的头部，表示最近使用
    private void putHead(Node cur){
        Node next = head.next;
        head.next = cur;
        cur.next = next;
        next.pre = cur;
        cur.pre = head;
    }
}

复杂度分析：

时间复杂度 $O(1)O(1)$：get和set都是常量操作，属于空间换时间

空间复杂度 $O(N)O(N)$：需要用到Node、Map等结构来维护元素