手写LRU缓存算法

题目描述

链接：https://www.nowcoder.com/questionTerminal/3da4aeb1c76042f2bc70dbcb94513338来源：牛客网

 设计一个数据结构，实现LRU Cache的功能(Least Recently Used – 最近最少使用缓存)。它支持如下2个操作： get 和 put。

int get(int key) – 如果key已存在，则返回key对应的值value（始终大于0）；如果key不存在，则返回-1。
void put(int key, int value) – 如果key不存在，将value插入；如果key已存在，则使用value替换原先已经存在的值。如果容量达到了限制，LRU Cache需要在插入新元素之前，将最近最少使用的元素删除。

请特别注意“使用”的定义：新插入或获取key视为被使用一次；而将已经存在的值替换更新，不算被使用。

限制：请在O(1)的时间复杂度内完成上述2个操作。

题解和思路

维护一个双向链表，链表的元素即是键值对，使用一个元素就把他放到头部，这样当容量不够时，链表结尾的元素即是最近最久没使用过的元素，将其删除即可

链表的删除和添加是非常方便的，可以达到O(1)的复杂度，但是查询就比较慢了，为了弥补这个不足，我们再额外维护一个散列表，便于查询，双向链表和散列表一定要对照，如图

关键点

1. 一个最大的容量、get()和put()两个API
2. 必须保证都是O(1)的时间复杂度
3. 上一次访问的元素在第一个

代码

import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;

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

class DoubleList {
    private Node head;
    private Node tail;
    private int size;
    DoubleList(){
        this.head = new Node(0,0); //只做头,无意义
        this.tail = this.head;
        this.size = 0;
    }

    public void addFirst(Node node){
        Node temp = head.next;
        head.next = node;
        node.next = temp;
        node.pre = head;
        if(temp!=null){
            temp.pre = node;
        }
        this.size ++;
        if(size == 1){
            this.tail = node;
        }
    }

    public Node removeLast(){
        if(this.size==0){
            return null;
        }else{
            Node temp = this.tail;
            this.tail = tail.pre;
            tail.next = null;
            this.size --;
            return temp;
        }
    }
    public void remove(Node node){
        if(node==this.tail){
            removeLast();
        }else{
            node.pre.next = node.next;
            node.next.pre = node.pre;
            this.size --;
        }
    }
    public int size(){
        return this.size;
    }
}

class LRUCache {
    private DoubleList doubleList = new DoubleList();
    private Map<Integer,Node> map = new HashMap<>();
    private int capacity;

    LRUCache(int capacity){
        this.capacity = capacity;
    }

    public void put(int key,int val){
        if(this.capacity <= 0){
            return;
        }
        Node node = new Node(key,val);
        Node origin = map.get(key);
        if(origin != null){
            origin.val = val;
        }else if(doubleList.size() == capacity){
            Node last = doubleList.removeLast();
            map.remove(last.key);
            doubleList.addFirst(node);
            map.put(key,node);
        }else{
            map.put(key,node);
            doubleList.addFirst(node);
        }
    }

    public int get(int key){
        Node result = map.get(key);
        if(result==null) {
            return -1;
        }else{
            doubleList.remove(result);
            doubleList.addFirst(result);
            return result.val;
        }
    }
}

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int ca = sc.nextInt();
        LRUCache lruCache = new LRUCache(ca);
        while(sc.hasNext()){
            String order = sc.next();
            if("p".equals(order)){
                int key = sc.nextInt();
                int value = sc.nextInt();
                lruCache.put(key,value);
            }else if("g".equals(order)){
                int key = sc.nextInt();
                int res = lruCache.get(key);
                System.out.println(res);
            }
        }
    }
}

测试数据

输入

2
p 1 1
p 2 2
g 1
p 2 102
p 3 3
g 1
g 2
g 3

输出

1
1
-1
3

说明

2        //Cache容量为2
p 1 1    //put(1, 1)
p 2 2    //put(2, 2)
g 1      //get(1), 返回1
p 2 102  //put(2, 102)，更新已存在的key，不算被使用
p 3 3    //put(3, 3)，容量超过限制，将最近最少使用的key=2清除
g 1      //get(1), 返回1
g 2      //get(2), 返回-1
g 3      //get(3), 返回3