首页 > 试题广场 >

设计LRU缓存结构

[编程题]设计LRU缓存结构
  • 热度指数：144640 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
设计LRU(最近最少使用)缓存结构，该结构在构造时确定大小，假设大小为 k ，操作次数是 n ，并有如下两个功能
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操作复杂度均为
数据范围： ，
示例1

输入

[[1,1,1],[1,2,2],[1,3,2],[2,1],[1,4,4],[2,2]],3

输出

[1,-1]

说明

[1,1,1]，第一个1表示opt=1，要set(1,1)，即将(1,1)插入缓存，缓存是{"1"=1}
[1,2,2]，第一个1表示opt=1，要set(2,2)，即将(2,2)插入缓存，缓存是{"1"=1,"2"=2}
[1,3,2]，第一个1表示opt=1，要set(3,2)，即将(3,2)插入缓存，缓存是{"1"=1,"2"=2,"3"=2}
[2,1]，第一个2表示opt=2，要get(1)，返回是[1]，因为get(1)操作，缓存更新，缓存是{"2"=2,"3"=2,"1"=1}
[1,4,4]，第一个1表示opt=1，要set(4,4)，即将(4,4)插入缓存，但是缓存已经达到最大容量3，移除最不经常使用的{"2"=2}，插入{"4"=4}，缓存是{"3"=2,"1"=1,"4"=4}
[2,2]，第一个2表示opt=2，要get(2)，查找不到，返回是[1,-1]
示例2

输入

[[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]
算法知识视频讲解
添加回答
Java
mee16头像 mee16 
没有使用双向链表，用了HashMap和一个linkedList实现，linkedList里面保存每次进来的key，
维护优先级，map只负责存取。


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) {
        // write code here
        HashMap<Integer, Integer> map = new HashMap<>(k);
        LinkedList<Integer> list = new LinkedList<>();
        
        ArrayList<Integer> res = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            if (operators[i].length == 3) {
                int key = operators[i][1];
                int value = operators[i][2];
                
                //如果小于数量K就只放入，否则删掉最不常使用的
                if (list.contains(key)) {
                    int index = 0;
                    for (int m = 0; m < list.size(); m++) {
                        if (list.get(m) == key) {
                            index = m;
                            break;
                        }
                    }
                    list.remove(index);
                    list.offerLast(key);
                } else {
                    if (list.size() < k) {
                    list.offerLast(key);
                } else {
                    list.offerLast(key);
                    map.remove(list.get(0));
                    list.removeFirst();
                }
                }
                map.put(key, value);
            }
            
            if (operators[i].length == 2) {
                if (map.get(operators[i][1]) != null) {
                    res.add(map.get(operators[i][1]));
                    int index = 0;
                    for (int m = 0; m < list.size(); m++) {
                        if (list.get(m) == operators[i][1]) {
                            index = m;
                            break;
                        }
                    }
                    list.remove(index);
                    list.offerLast(operators[i][1]);
                } else {
                    res.add(-1);
                }
            }
        }
        
        int[] result = new int[res.size()];
        for (int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
}

发表于 2022-03-17 17:05:05 回复(0)
Java
半桶响叮当头像 半桶响叮当 
import java.util.*;


public class Solution {
    Map<Integer, DeLinkedNode> cache = new HashMap<>();
    int size;
    int capacity;
    DeLinkedNode head = new DeLinkedNode();
    DeLinkedNode tail = new DeLinkedNode();
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.capacity = k;
        this.size = 0;
        head.next = tail;
        tail.prex = head;
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < operators.length;i++) {
            if (operators[i][0] == 1) {
                set(operators[i][1],operators[i][2]);
            }else {
                 list.add(get(operators[i][1]));
            }
        }
        int[] res = new int[list.size()];
        for (int j = 0; j < list.size();j++) {
            res[j] = list.get(j);
        }
        return res;
    }
   
    
    private int get(int key) {
        DeLinkedNode node =  cache.get(key);
        if (node == null) {
            return -1;
        }
        moveToHead(node);
        return node.val;
    }
    
    private void set (int key, int val) {
        DeLinkedNode node = cache.get(key);
        if (node != null) {
            node.val = val;
            moveToHead(node);
            return;
        }
        
        DeLinkedNode newNode = new DeLinkedNode(key,val);
        cache.put(key,newNode);
        addToHead(newNode);
        size++;
        if (size > capacity) {
            DeLinkedNode temp = removeTail();
            cache.remove(temp.key);
            size--;
        }
 
    }
    
    private void addToHead(DeLinkedNode node) {
        node.next = head.next;
        head.next.prex = node;
        node.prex = head;
        head.next = node;
    }
    
    private void removeNode(DeLinkedNode node) {
        node.next.prex = node.prex;
        node.prex.next = node.next;
    }
    
    private void moveToHead(DeLinkedNode node) {
        removeNode(node);
        addToHead(node);
    }
    
    private DeLinkedNode removeTail(){
        DeLinkedNode temp = tail.prex;
        removeNode(temp);
        return temp;
    }
        
        
        
    
   class DeLinkedNode{
       int key, val;
       DeLinkedNode prex, next;
       
       DeLinkedNode(){};
       DeLinkedNode(int key,int val) {
           this.key = key;
           this.val = val;
       }
   }
    
}

发表于 2022-03-15 20:36:37 回复(0)
Java
繁星四月份头像 繁星四月份 
import java.util.*;


public class Solution {
    private LinkedList<Entry> lru=new LinkedList<>();

    public int[] LRU (int[][] operators, int k) {
        // write code here
        int []res=new int[operators.length];
        int length=0;
        for(int i=0;i<operators.length;i++){
            switch (operators[i][0]){
                case 1:
                    set(operators[i][1],operators[i][2],k);
                    break;
                case 2:
                    int value=get(operators[i][1],k);
                    res[length++]=value;
                    break;
            }
        }
        res= Arrays.copyOf(res,length);
        return res;
    }
    private int get(int key,int k){
        // 这边得0是任意值，随便写啥都可以因为 equal是中只比较key
        int index=lru.indexOf(new Entry(key,0));
        if(index==-1) return -1;
        Entry entry=lru.remove(index);
        lru.push(entry);
        return entry.getValue();
    }
    private void set(int key,int value,int k){
        Entry entry=new Entry(key,value);
        if(lru.size()==k){
            int index=lru.indexOf(entry);
            if(index!=-1){
                lru.remove(index);
            }else {
                lru.removeLast();
            }
        }
        lru.push(entry);
    }
    static class Entry{
        private int key;
        private int value;

        public Entry(int key, int value) {
            this.key = key;
            this.value = value;
        }

        public int getKey() {
            return key;
        }

        public void setKey(int key) {
            this.key = key;
        }

        public int getValue() {
            return value;
        }

        public void setValue(int value) {
            this.value = value;
        }
        // 用来链表得查询比较
        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;

            Entry entry = (Entry) o;

            return getKey() == entry.getKey();
        }

        @Override
        public int hashCode() {
            return getKey();
        }
    }
}

发表于 2022-03-07 19:58:20 回复(0)
Java
牛客225887487号头像 牛客225887487号 
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) {
        // 存放要输出的数据
        ArrayList<Integer> resultList = new ArrayList();
        // 存放缓存
        Map<Integer, Integer> cache = new LinkedHashMap<>();
        // 存放临时数据
        Integer[] tempArray = new Integer[2];
        for (int i = 0; i < operators.length; i++) {
            if(operators[i][0] == 1){
                cache.put(operators[i][1],operators[i][2]);
            } else {
                if(cache.get(operators[i][1]) == null){
                    resultList.add(-1);
                } else {
                    tempArray[0] = operators[i][1];
                    tempArray[1] = cache.get(operators[i][1]);
                    cache.remove(operators[i][1]);
                    // 这步很关键，定义成int才能存放到末尾
                    int key = tempArray[0];
                    cache.put(key,tempArray[1]);
                    resultList.add(tempArray[1]);
                }
            }
            if(cache.size() > k){
                // 这步很关键，通过迭代器遍历，删除第一个元素
                cache.remove(cache.entrySet().iterator().next().getKey());
            }
        }
        int[] resultArray = new int[resultList.size()];
        for (int i = 0; i < resultList.size(); i++) {
            resultArray[i] = resultList.get(i);
        }
        System.out.println(Arrays.toString(resultArray));
        return resultArray;
    }
}

发表于 2022-02-22 23:37:59 回复(0)
Java
Sushine头像 Sushine 
 public int[] LRU (int[][] operators, int k) {
        LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>(k,0.75f,true);
        List<Integer> list = new ArrayList<>();
        for (int[] o : operators) {
            if (o[0] == 1) {
                if (map.size() == k) {
                    map.remove(map.keySet().iterator().next());
                }
                map.put(o[1], o[2]);
            } else {
                if (map.get(o[1]) == null) {
                    list.add(-1);
                } else {
                    list.add(map.get(o[1]));
                }
            }
        }
        return list.stream().mapToInt(v -> v).toArray();
    }

发表于 2022-02-15 22:42:39 回复(0)
Java
牛客251665384号头像 牛客251665384号
//各位大佬帮忙看看最后一个用例没通过，就是数据量很大的一组用例，不知道是什么原因 
public int[] LRU (int[][] operators, int k) {
        // write code here
        int[] keyArray = new int[k];
        int[] valueArray = new int[k];
        int[] array = new int[operators.length];
        int num = 0;

        for(int i=0;i<operators.length;i++){
            if(operators[i][0]==1){
                //i的值大于k的值
                if(i>k){
                    //将数组的列数往前移
                    int c=0;
                    for(int n=0;n<keyArray.length-1;n++){
                        keyArray[n] = keyArray[n+1];
                        valueArray[n] = valueArray[n+1];
                        if(keyArray[n]!=0){
                            c++;
                        }
                    }
                    keyArray[c] = operators[i][1];
                    valueArray[c] = operators[i][2];

                }else{

                    if(k==i){
                        keyArray[i-1] = operators[i][1];
                        valueArray[i-1] = operators[i][2];
                    }else{
                        keyArray[i] = operators[i][1];
                        valueArray[i] = operators[i][2];
                    }

                }

            }else if(operators[i][0]==2){
                //数组的每行的第二位是2的话
                for(int j=keyArray.length-1; j>=0; j--){
                    // for(int j=0; j<keyArray.length; j++){
                    //比较是否有相等的key值
                    if(operators[i][1] == keyArray[j]){
                        // 如果存在key，就返回对应的value值，如果不存在则返回-1，同时如果存在的话会重新刷新一遍
                        array[num] = valueArray[j];

                        // keyArray和valueArray会跟着变化，进行刷新
                        int a = keyArray[j];
                        int b = valueArray[j];
                        int c = 0;
                        for(int n=j; n<keyArray.length-1; n++){
                            // 从出现变化的位置开始进行刷新
                            keyArray[n] = keyArray[n+1];
                            valueArray[n] = valueArray[n+1];
                            if(keyArray[n]!=0){
                                c++;
                            }
                        }
                            keyArray[c+j] = a;
                            valueArray[c+j] = b;

                        //找到合适的就退出
                        break;
                    }else{
                        //如果j不在里面，返回一个数
                        array[num] = -1;
                    }
                }
                // 数值自增
                num++;
            }

        }
        int[] arr = new int[num];
        for(int i=0;i<num;i++){
            arr[i] = array[i];
        }
        return arr;
    }


发表于 2022-02-10 17:27:43 回复(0)
Java
胡不慌头像 胡不慌
跟各位大佬相比，觉得我写的代码有点多 

import java.util.*;


public class Solution {
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    private Node first, last;
    private HashMap<Integer, Node> map = new HashMap<Integer, Node>();;
    public int[] LRU (int[][] operators, int k) {        
        ArrayList<Integer> res = new ArrayList<Integer>();
        // write code here
        for(int[] action: operators) {
            if(action[0] == 1) {// 插入一个节点
                if(map.containsKey(action[1])) {
                    Node node = map.get(action[1]);
                    node.val = action[2];
                    this.remove(node);
                    this.addFirst(node);
                }else {
                    Node node = new Node(action[1], action[2]);
                    if(map.size() == k) {
                        Node t = this.removeLast();
                        map.remove(t.key);
                    }
                    this.addFirst(node);
                    this.map.put(node.key, node);
                }
                
            }else if(action[0] == 2) {// 查询一个节点
                if(map.containsKey(action[1])) {
                    Node node = map.get(action[1]);
                    this.remove(node);
                    this.addFirst(node);
                    res.add(node.val);
                }else {
                    res.add(-1);
                }
            }
        }
        
        int[] result = new int[res.size()];
        for(int i = 0; i < res.size(); i++) {
            result[i] = res.get(i);
        }
        return result;
    }
    
    /**
     * 如果没有节点，如果有一至多个节点
     */
    public void addFirst(Node node) {
        if(first == null) {
            first = node;
            last = node;
        }else {
            first.prev = node;
            node.next = first;
            first = node;
        }
    }
    
    // 要删除的这个节点可能在开头，中间，结尾
    public void remove(Node node) {
        if(node == null) return;
        else if(node.prev == null && node.next == null) {
            first = null;
            last = null;
        }else if(node.prev == null) {
            first = node.next;
            node.next.prev = null;
            node.next = null;
        }else if(node.next == null) {
            last = node.prev;
            node.prev.next = null;
            node.prev = null;
        }else {
            node.prev.next = node.next;
            node.next.prev = node.prev;
            node.prev = null;
            node.next = null;
        }
    }
    // 如果没有元素，如果只有一个，或有多个
    public Node removeLast() {
        if(last == null) {
            return null;
        }else if(first == last) {
            Node res = first;
            first = null;
            last = null;
            return res;
        }else{
            Node res = last;
            last.prev.next = null;
            last = last.prev;
            
            res.prev = null;
            return res;
        }
    }
    
    class Node {
        public int key;
        public int val;
        public Node prev;
        public Node next;
        
        public Node(int key, int val) {
            this.key = key;
            this.val = val;
        }
    }
}


发表于 2022-01-21 17:18:57 回复(0)
Java
hhffgukih头像 hhffgukih
顺便写个通用LRU工具类 
import java.util.*;

public class Solution {
    
    public int[] LRU (int[][] operators, int k) {
        LRUCache<Integer, Integer> lruCache = new LRUCache<>(k);
        int len = (int)Arrays.stream(operators).filter(x -> x[0] == 2).count();
        // 存储返回结果
        int[] res = new int[len];
        for(int i = 0, j = 0; i < operators.length; i++) {
            if(operators[i][0] == 1) {
                lruCache.set(operators[i][1], operators[i][2]);
            } else {
                res[j++] = lruCache.get(operators[i][1]) == null? -1: lruCache.get(operators[i][1]);
            }
        }
        return res;
    }

}

class LRUCache<K, V> {
    private final ListNode<K, V> head = new ListNode<>(null, null);
    private final ListNode<K, V> tail = new ListNode<>(null, null);

    private final Map<K, ListNode<K, V>> map = new HashMap<>();
    int lruMaxSize;

    public LRUCache(int size){
        head.next = tail;
        tail.pre = head;
        this.lruMaxSize = size;
    }

    public void set(K key, V val){
        if(map.get(key) != null){
            map.get(key).val = val;
        }else {
            if(map.size() >= lruMaxSize){
                K lastKey = tail.pre.key;
                map.remove(lastKey);
                tail.pre.pre.next = tail;
                tail.pre = tail.pre.pre;
            }
            ListNode<K, V> node = new ListNode<>(key, val);
            map.put(key, node);
            moveToHead(node);
        }
    }

    private void moveToHead(ListNode<K,V> node) {
        head.next.pre = node;
        node.next = head.next;
        head.next = node;
        node.pre = head;
    }

    public V get(K key){
        if(map.get(key) != null){
            ListNode<K, V> node = map.get(key);
            node.pre.next = node.next;
            node.next.pre = node.pre;
            moveToHead(node);
            return node.val;
        }else {
            return null;
        }
    }
    
    static class ListNode<K, V>{
        K key;
        V val;
        ListNode<K, V> next;
        ListNode<K, V> pre;
        public ListNode(K key, V val){
            this.key = key;
            this.val = val;
        }
    }
}


发表于 2022-01-15 15:04:29 回复(0)
Java
JohannLuis头像 JohannLuis 
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) {
        // write code here
        List<Integer> list = new ArrayList<>();
        Map<Integer, Integer> map = new LinkedHashMap<>();
        for(int[] arr :operators) {
            if(arr[0] == 1) {
                //插入数据
                //判断map中是否包含该数据
                if(map.containsKey(arr[1])) {
                    map.remove(arr[1]);
                }
                //判断map中的容量是否已满
                if(map.size() >= k) {
                    //移除第一个元素，可以使用迭代器
                    Iterator<Integer> iterator = map.keySet().iterator();
                    int firstKey = iterator.next();
                    map.remove(firstKey);
                } 
                map.put(arr[1], arr[2]);
            } else {
                //取数据
                int num = map.getOrDefault(arr[1], -1);
                //取完数据放至头部
                if(num != -1) {
                    map.remove(arr[1]);
                    map.put(arr[1], num);
                }
                list.add(num);
            }
        }
        int[] res = new int[list.size()];
        for(int i = 0; i < list.size(); i++) {
            res[i] = list.get(i);
        }
        return res;
    }
}

发表于 2022-01-08 12:30:36 回复(0)
Java
***头像 *** 
public static int[] LRU (int[][] operators, int k) {
        // write code here
        List<Integer> result=new ArrayList();
        Map<Integer,Integer> cach=new HashMap();
        Map<Integer,Integer>index=new HashMap();
        for(int i=0;i<operators.length;i++){
            if(cach.size()<k){
                if(operators[i][0]==1){
                    cach.put(operators[i][1],operators[i][2]);
                    index.put(operators[i][1],(index.get(operators[i][1])==null)?1:index.get(operators[i][1])+1);
                }
                if(operators[i][0]==2){
                    result.add(cach.get(operators[i][1])==null?-1:operators[i][1]);
                    index.put(operators[i][1],(index.get(operators[i][1])==null)?1:index.get(operators[i][1])+1);
                }
            }else{
                if(operators[i][0]==2){
                    index.put(operators[i][1],(index.get(operators[i][1])==null)?1:index.get(operators[i][1])+1);
                    int key=delCache(index);
                    cach.remove(key);
                    index.remove(key);
                    result.add(cach.get(operators[i][1])==null?-1:operators[i][1]);
                    index.put(operators[i][1],(index.get(operators[i][1])==null)?1:index.get(operators[i][1]));
                }

            }
        }
        int res[] = new int[result.size()];
        for(int i=0;i<result.size();i++){
            res[i]=result.get(i);
        }

        return res;

    }

    public static int delCache(Map<Integer,Integer> data){
        int flag=0;
        int minValue=Integer.MAX_VALUE;
        for(int key:data.keySet()){
            if(data.get(key)<minValue){
                flag=key;
                minValue=data.get(key);
            }
        }
        return flag;

    }

发表于 2022-01-05 15:59:29 回复(0)
Java
架构师123456号头像 架构师123456号
哈哈，小K时蛮好，大K时建议底层换二叉树，比如K大于8时 
public int[] LRU (int[][] operators, int k) { // write code here   int writeLength = 0; for (int[] opt : operators) { if (opt[0] == 2) {
                writeLength++;
            }
        } // init 如果k过大建议用map  fixedlink = new Fixedlink(k); int length = 0; int[] result = new int[writeLength]; for (int[] opt : operators) { //            System.out.println(Arrays.toString(opt));  if (opt[0] == 1) { // put  fixedlink.add(opt[1], opt[2]); //                System.out.println(fixedlink);  continue;
            } // get  result[length] = fixedlink.get(opt[1]); //            System.out.println(fixedlink);  length++;
        } return result;
    } Fixedlink fixedlink; class Fixedlink { int current, length; Node end; final Node head = new Node(); public Fixedlink(int length) { this.length = length;
        } public void add(int key, int value) { Node node = new Node(); node.key = key; node.value = value; if (fixedlink.head.next == null) { end = node;
            } else { fixedlink.head.next.pre = node;
            } node.next = fixedlink.head.next; node.pre = head; head.next = node; if (current + 1 > length) { end = end.pre; end.next = null; return;
            } current++;
        } private int get(int num) { Node node = head.next; while (node != null) { if (node.key == num) { if (end == node) { end = node.pre;
                    }
                    node.pre.next = node.next; if (node.next != null) {
                        node.next.pre = node.pre;
                    }
                    node.pre = head;
                    node.next = head.next; if (head.next != null) { head.next.pre = node;
                    } head.next = node; return node.value;
                }
                node = node.next;
            } return -1;
        } @Override  public String toString() { StringBuilder builder = new StringBuilder("{"); Node node = head.next; while (node != null) { builder.append("{").append(node.key).append(":").append(node.value).append("}");
                node = node.next;
            } builder.append("}"); return builder.toString();
        } class Node { int key; int value; Node pre; Node next;
        }
    }

发表于 2022-01-03 00:52:18 回复(0)
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) {
        List<Integer> list = new ArrayList<>();
        // write code here
        for (int i = 0; i < operators.length; i++) {
            int[] params = operators[i];
            if (params[0] == 1) {
                set(params[1], params[2], k);
                continue;
            }
            if (params[0] == 2) {
                list.add(get(params[1]));
            }
        }
        
        int[] r = new int[list.size()];
        int i = 0;
        for (Integer v : list) {
            r[i] = v;
            i++;
        }
        return r;
    }
    
    private final LinkedHashMap<Integer, Integer> map = new LinkedHashMap<>();

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Integer value = map.get(key);
        //重新放到队列最尾部
        map.remove(key);
        map.put(key, value);
        return value;
    }

    public int set(int key, int value, int capacity) {
        if (map.size() >= capacity) {
            Iterator<Map.Entry<Integer, Integer>> iterator = map.entrySet().iterator();
            //移除队列头
            if (iterator.hasNext()) {
                iterator.next();
                iterator.remove();
            }
        }
        map.put(key, value);
        return value;
    }
}

发表于 2021-12-26 10:24:26 回复(0)
Java
玄鉴头像 玄鉴 
import java.util.*;
public class Solution {
    static class Node{
        int key;
        int value;
        Node prev;
        Node next;
        public Node(){};
        public Node(int key,int value){
            this.key=key;
            this.value=value;
        }
    }
    List<Integer> res=new ArrayList();
    HashMap<Integer,Node>map=new HashMap<>();
    int capacity;//表示容量
    int size=0;//记录lru中元素个数
    //准备两个节点 头节点和尾节点
    Node head=null;
    Node tail=null;
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.capacity=k;
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.prev=head;
        for(int[]v:operators){
            if(v[0]==1){
                set(v[1],v[2]);
            }else{
                int val=get(v[1]);
                res.add(val);
            }
        }
        return res.stream().mapToInt(a->a.intValue()).toArray();
    }
    public int get(int key){
        if(!map.containsKey(key)) return -1;
        else{
            Node node=map.get(key);
            moveToHead(node);//对于get方法movetohead
            return node.value;
        }
    }
    public void set(int key,int value){
        if(!map.containsKey(key)){
            Node node=new Node(key,value);

            addToHead(node);
             map.put(key,node);
            size++;
            if(size>capacity){
                //找了半天

                map.remove(tail.prev.key);
                  removeTail();
                size--;
            }
        }else{
            //如果包含这个值
            Node node=map.get(key);
            //值是一个引用类型，不需要再次put
            node.value=value;
            moveToHead(node);

        }
    }
    public void moveToHead(Node node){
        deleteNode(node);
        addToHead(node);
    }
    public void deleteNode(Node node){
      node.prev.next=node.next;
      node.next.prev=node.prev;
      node.next=null;
      node.prev=null;
    }
    public void addToHead(Node node){
        node.next=head.next;
        int v=node.value;
        head.next.prev=node;
        node.prev=head;
        head.next=node;

    }
    public void removeTail(){
    Node realTail=tail.prev;
    tail.prev=realTail.prev;
    realTail.prev.next=tail;
    realTail.prev=null;
    realTail.next=null;
    }


}
发表于 2021-12-11 14:03:56 回复(0)
Java
许你清安L头像 许你清安L 
import java.util.*;


public class Solution {
    
    class Node{
        public int key;
        public int val;
        public Node prev;
        public Node next;
        
        public Node(){}
        
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    
    private Map<Integer,Node> cache;
    private int capacity;
    private Node head;
    private Node tail;
    /**
     * lru design
     * @param operators int整型二维数组 the ops
     * @param k int整型 the k
     * @return int整型一维数组
     */
    public int[] LRU (int[][] operators, int k) {
        // write code here
        this.capacity = k;
        cache = new HashMap<>();
        head = new Node(-1,-1);
        tail = new Node(-1,-1);
        head.next = tail;
        tail.prev = head;
        List<Integer> res = new ArrayList<>();
        for(int[] operator : operators ){
            if(operator[0] == 1){
                put(operator[1],operator[2]);
            }else{
                res.add(get(operator[1]));
            }
        }
        
        int[] ans = new int[res.size()];
        for(int i = 0; i < res.size(); i++){
            ans[i] = res.get(i);
        }
        return ans;
    }
    
    private int get(int key){
        if(cache.containsKey(key)){
            Node cur = cache.get(key);
            moveToTail(cur);
            return cur.val;
        }
        return -1;
    }
    
    private void put(int key,int val){
        if(cache.containsKey(key)){
            Node old = cache.get(key);
            old.val = val;
            moveToTail(old);
        }else{
            if(capacity == cache.size()){
                deleteHead();
            }
            Node newNode = new Node(key,val);
            addToTail(newNode);
        }
    }
    
    private void delete(Node deleted){
        deleted.next.prev = deleted.prev;
        deleted.prev.next = deleted.next;
        cache.remove(deleted.key);
    }
    
    private void deleteHead(){
        Node deleted = head.next;
        delete(deleted);
    }
    
    private void moveToTail(Node cur){
        delete(cur);
        addToTail(cur);
    }
    
    private void addToTail(Node cur){
        cur.prev = tail.prev;
        tail.prev.next = cur;
        cur.next = tail;
        tail.prev = cur;
        
        cache.put(cur.key,cur);
    }
}

发表于 2021-12-02 14:10:17 回复(0)
Java
牛客749206447号头像 牛客749206447号
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) {
        // write code here
        Map<Integer, Integer> m = new HashMap<>();//存放value用来保证查找时复杂度为O(1)
        LinkedList<Integer> keyArr = new LinkedList<>();//存放key淘汰的优先顺序，刷新的元素添加到表头，尾淘汰。
        List<Integer> resultList = new ArrayList<>();
        for (int i = 0; i < operators.length; i++) {
            if (operators[i][0] == 1) {
                m.put(operators[i][1], operators[i][2]);

                //刷新缓存,加入新元素，淘汰尾元素
                if(!keyArr.contains(operators[i][1])){
                    keyArr.addFirst(operators[i][1]);
                    if (keyArr.size() > k) {
                        Integer removeKey = keyArr.removeLast();
                        m.remove(removeKey);
                    }
                }
            } else {
                Integer value = m.get(operators[i][1]);
                if (value == null){
                    resultList.add(-1);
                    continue;
                }
                resultList.add(value);

                //刷新缓存,插入到列表最前面
                for (int j = 0; j < keyArr.size(); j++) {
                    if (keyArr.get(j) == operators[i][1]) {
                        Integer removeKey = keyArr.remove(j);
                        keyArr.addFirst(removeKey);
                    }
                }
            }
        }
        return resultList.stream().mapToInt(Integer::intValue).toArray();
    }
}
发表于 2021-11-24 14:30:37 回复(0)
提交观点

问题信息

模拟
难度：
113条回答 15227浏览

热门推荐

通过挑战的用户

相关试题

设计LRU缓存结构

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号