LRU : 最近最久未使用算法，将最近使用的元素放在头部，最早使用的放在末尾。

着急的小伙伴直接滑下去看代码就行，不着急的可以从头开始读，看看我的一些想法

这道题就是让咱们写出 LRU 的效果，在 Java 中可以使用 LinkedHashMap 数据结构，但是面试中直接使用并不是达到面试官的期望，所以需要自己来从头开始写。

主要分为三步：功能与特性的确定、数据结构的确定、逻辑的实现。

思路

很多小伙伴刚拿到这道题的时候大多会一头雾水，心想，我知道啥是 LRU， 但是当我开始动手写的时候，确实不知道该写啥，从哪里写？其实我也一样，我也是去网上找资料，去学LRU特性，去看别的大佬的题解，看完虽然能写下来，但还是没有一个完善的思路。这里我就写一下我自己的看法：

1. 功能与特性的确定：不管是LRU还是啥，它本质都是一个缓存，既然是缓存，那么肯定要具备两个最基本的功能：设置元素，获取元素，还有缓存的一些特性，如：缓存的容量限制。这样咱们在写代码的时候，就需要将这些考虑到。

2. 数据结构的确定：缓存的功能和特性咱们知道了，那么到底用啥来存储缓存中的元素那？缓存存储数据都是通过 key，value 的形式，那么存储这种结构 首选必然是 哈希表。然后，这道题让实现 LRU 功能，这个需要元素是有序的，所以选择 双向链表 最为合适了。所以，数据选定为：哈希表+双向链表。

3. 逻辑的实现：这时候才开始关注 LRU 的特性：

   • 刚使用的元素（新插入的元素+最新查询的元素）要放到队列头部。
   • 每次新增元素时要检查是否超出容量，超出：移除队列尾端元素。

差不多就这些，接下来开始写代码吧。

import java.util.*;
import java.lang.*;


public class Solution {
    // 节点元素
    class LRUNode {
        private int key;
        private int value;
        private LRUNode prev;
        private LRUNode next;
        private LRUNode(){}
        private LRUNode(int key, int value) {
            this.key = key;
            this.value = value;
        }
    }

    private Map<Integer, LRUNode> lruCache = new HashMap<>();
    // 头节点
    private LRUNode head = new LRUNode();
    // 尾节点
    private LRUNode tail = new LRUNode();
    // 容量限制
    private int capacity;
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
         // write code here
        if (operators == null || operators.length < 1) {
            return new int[0];
        }
        // 初始化容量
        this.capacity = k;
        //设置虚拟头尾节点 
        head.next = tail; 
        tail.prev = head;
        // 答案的数据长度
        int len = 0;
        for(int i = 0; i < operators.length; i ++) {
            // 2 开头时 get 操作，每一次 get 操作都会有一个返回值
            if (operators[i][0] == 2) {
                len ++;
            }
        }
        int[] result = new int[len];
        int index = 0;
        for (int j = 0; j < operators.length; j ++) {
            // 如果开头是 1， 设置缓存
            if (operators[j][0] == 1) {
                put(operators[j][1], operators[j][2]);
            } else if (operators[j][0] == 2) {
                // 如果开头是 2，查询缓存，存储结果
                result[index++] = get(operators[j][1]);
            }
        }
        return result;



    }

    public void put(Integer key, Integer value) {
        LRUNode node = lruCache.get(key);
        // 如果链表中不存在这个节点
        if (node == null) {
            // 新创建一个节点
            LRUNode newNode = new LRUNode(key, value);
            // 将其添加进链表中
            addToHead(newNode);
            // 添加进缓存
            lruCache.put(key, newNode);
            // 如果超出容量限制
            if (lruCache.size() > capacity) {
                // 移除尾节点
                LRUNode removeNode = removeTail();
                // 从缓存中移除
                lruCache.remove(removeNode.key);
            }
        } else {
            // 当链表中存在此节点

            // 直接替换 value 值即可
            node.value = value;
            // 再将其移动到头部
            moveToHead(node);
        }
    }

    public Integer get(Integer key) {
        LRUNode node = lruCache.get(key);
        if (node == null) {
            return -1;
        }
        // 移动到头部
        moveToHead(node);
        return node.value;
    }

    // 将节点添加到头部
    public void addToHead(LRUNode targetNode) {
        head.next.prev = targetNode;
        targetNode.next = head.next;
        targetNode.prev = head;
        head.next = targetNode;
    }
    // 移除尾节点
    public LRUNode removeTail() {
        LRUNode removeNode = tail.prev;
        removeNode.prev.next = removeNode.next;
        removeNode.next.prev = removeNode.prev;
        return removeNode;
    }
    // 将链表中的节点移动到头部
    public void moveToHead(LRUNode targetNode) {
        // 先把节点从链表中移除
        targetNode.prev.next = targetNode.next;
        targetNode.next.prev = targetNode.prev;
        // 再将这个节点添加到头部
        addToHead(targetNode);
    }
}

时间复杂度：O(1),因为时 哈希表，时间复杂度都是 O(1)。
空间复杂度：O(缓存容量大小)

最后

该题来自【牛客网 - 题库 - 在线编程】，大家可以去试试~
关注我的公众号，一起学习。