mzoe666888

V1

2022/05/25阅读:30主题:兰青

内卷大厂系列《LRU 缓存淘汰算法》

大厂高频算法面试题:《LRU 缓存淘汰算法》,您将学到 LRU 是什么?解决什么问题?现在的大厂必问的高频算法面试笔试题,要求手撸 LRU 的实现。

一、LRU 是什么?

LRU 是 Least Recently Used 的缩写,即最近最少使用,是一种常用的内存淘汰数据算法,即淘汰掉最近最少使用的缓存数据。

二、LRU 功能需求

请你设计并实现一个满足 LRU (最近最少使用) 缓存约束的数据结构。

实现 LRUCache 类:

  1. LRUCache(int capacity) 以 正整数 作为容量 capacity 初始化 LRU 缓存。
  2. int get(int key) 如果关键字 key 存在于缓存中,则返回关键字的值,否则返回 -1 。
  3. void put(int key, int value) 如果关键字 key 已经存在,则变更其数据值 value ;如果不存在,则向缓存中插入该组 key-value 。如果插入操作导致关键字数量超过 capacity ,则应该 逐出 最久未使用的关键字。
  4. 函数 get 和 put 必须以 O(1) 的平均时间复杂度运行。

示例

输入
["LRUCache""put""put""get""put""get""put""get""get""get"]
[[2], [11], [22], [1], [33], [2], [44], [1], [3], [4]]
输出
[nullnullnull1null, -1null, -134]

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

leetcode

三、实现

分析:要淘汰掉最近最少使用的内存数据,那么怎么区分哪些内存数据最近没有使用呢?

可以采用Map结构(查询操作O(1)) + 双向链表(头部记录旧的数据,尾部记录新的数据)

双向链表中,把数据按照尾部添加,离头近的代表时间点早的(早入队),离头远的代表时间点晚(后入队),按照尾部添加,头部删除原则,离头近的就代表最近最少使用的数据,即淘汰掉链表头部的数据代表最近最少使用的数据。

双向链表操作总结如下:

  1. 尾部添加节点
  2. 获取元素(get操作)即使用了元素,需要把元素移动到链表尾部(代表最近使用了该数据)
  3. 添加元素(put操作)即使用了元素,如果元素存在,则更新元素数据,同时也需要把该元素移动到链表尾部(代表最近使用了该数据),如果元素不存在,则直接添加到链表尾部。
  4. 添加元素时,需要考虑容量大小问题,如果超出当前容量,则移除掉链表头部元素(代表最近没操作的数据)
public class LRUCache {

    private MyCache<Integer, Integer> cache;

    public LRUCache(int capacity) {
        cache = new MyCache<>(capacity);
    }

    public int get(int key) {
        Integer ans = cache.get(key);
        return ans == null ? -1 : ans;
    }

    public void put(int key, int value) {
        cache.set(key, value);
    }

    // 节点结构
    public static class Node<KV{
        public K key;
        public V value;
        public Node<K, V> pre;
        public Node<K, V> next;

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

    // 双向链表结构
    public static class NodeDoubleLinkedList<KV{
        private Node<K, V> head;
        private Node<K, V> tail;

        public NodeDoubleLinkedList() {
            head = null;
            tail = null;
        }

        // 尾部添加节点
        public void addNode(Node<K, V> newNode) {
            if (newNode == null) {
                return;
            }
            if (head == null) {
                head = newNode;
                tail = newNode;
            } else {
                tail.next = newNode;
                newNode.pre = tail;
                tail = newNode;
            }
        }

        // 把链表上的节点移动到尾部
        public void moveNodeToTail(Node<K, V> node) {
            if (tail == node) {
                return;
            }
            // node 不是尾巴
            if (head == node) {
                head = node.next;
                head.pre = null;
            } else {
                node.pre.next = node.next;
                node.next.pre = node.pre;
            }
            node.pre = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }

        // 移除头部节点
        public Node<K, V> removeHead() {
            if (head == null) {
                return null;
            }
            Node<K, V> res = head;
            if (head == tail) { // 链表中只有一个节点的时候
                head = null;
                tail = null;
            } else {
                head = res.next;
                res.next = null;
                head.pre = null;
            }
            return res;
        }

    }

    public static class MyCache<KV{

        private HashMap<K, Node<K, V>> keyNodeMap;
        private NodeDoubleLinkedList<K, V> nodeList;
        private final int capacity;

        public MyCache(int cap) {
            if (cap < 1) {
                throw new RuntimeException("should be more than 0.");
            }
            keyNodeMap = new HashMap<>();
            nodeList = new NodeDoubleLinkedList<>();
            capacity = cap;
        }

        public V get(K key) {
            if (keyNodeMap.containsKey(key)) {
                Node<K, V> res = keyNodeMap.get(key);
                nodeList.moveNodeToTail(res);
                return res.value;
            }
            return null;
        }

        public void set(K key, V value) {
            if (keyNodeMap.containsKey(key)) {
                Node<K, V> node = keyNodeMap.get(key);
                node.value = value;
                nodeList.moveNodeToTail(node);
            } else {
                if (keyNodeMap.size() == capacity) {
                    removeMostUnusedCache();
                }
                Node<K, V> newNode = new Node<>(key, value);
                keyNodeMap.put(key, newNode);
                nodeList.addNode(newNode);
            }
        }

        private void removeMostUnusedCache() {
            Node<K, V> removeNode = nodeList.removeHead();
            keyNodeMap.remove(removeNode.key);
        }

    }
}

分类:

后端

标签:

数据结构与算法

作者介绍

mzoe666888
V1